src/v8/src/type-info.cc

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include "v8.h"
  29
  30 #include "ast.h"
  31 #include "code-stubs.h"
  32 #include "compiler.h"
  33 #include "ic.h"
  34 #include "macro-assembler.h"
  35 #include "stub-cache.h"
  36 #include "type-info.h"
  37
  38 #include "ic-inl.h"
  39 #include "objects-inl.h"
  40
  41 namespace v8 {
  42 namespace internal {
  43
  44
  45 TypeFeedbackOracle::TypeFeedbackOracle(Handle<Code> code,
  46                                        Handle<Context> native_context,
  47                                        Zone* zone)
  48     : native_context_(native_context),
  49       zone_(zone) {
  50   Object* raw_info = code->type_feedback_info();
  51   if (raw_info->IsTypeFeedbackInfo()) {
  52     feedback_vector_ = Handle<FixedArray>(TypeFeedbackInfo::cast(raw_info)->
  53                                           feedback_vector());
  54   }
  55
  56   BuildDictionary(code);
  57   ASSERT(dictionary_->IsDictionary());
  58 }
  59
  60
  61 static uint32_t IdToKey(TypeFeedbackId ast_id) {
  62   return static_cast<uint32_t>(ast_id.ToInt());
  63 }
  64
  65
  66 Handle<Object> TypeFeedbackOracle::GetInfo(TypeFeedbackId ast_id) {
  67   int entry = dictionary_->FindEntry(IdToKey(ast_id));
  68   if (entry != UnseededNumberDictionary::kNotFound) {
  69     Object* value = dictionary_->ValueAt(entry);
  70     if (value->IsCell()) {
  71       Cell* cell = Cell::cast(value);
  72       return Handle<Object>(cell->value(), isolate());
  73     } else {
  74       return Handle<Object>(value, isolate());
  75     }
  76   }
  77   return Handle<Object>::cast(isolate()->factory()->undefined_value());
  78 }
  79
  80
  81 Handle<Object> TypeFeedbackOracle::GetInfo(int slot) {
  82   ASSERT(slot >= 0 && slot < feedback_vector_->length());
  83   Object* obj = feedback_vector_->get(slot);
  84   if (!obj->IsJSFunction() ||
  85       !CanRetainOtherContext(JSFunction::cast(obj), *native_context_)) {
  86     return Handle<Object>(obj, isolate());
  87   }
  88   return Handle<Object>::cast(isolate()->factory()->undefined_value());
  89 }
  90
  91
  92 bool TypeFeedbackOracle::LoadIsUninitialized(TypeFeedbackId id) {
  93   Handle<Object> maybe_code = GetInfo(id);
  94   if (maybe_code->IsCode()) {
  95     Handle<Code> code = Handle<Code>::cast(maybe_code);
  96     return code->is_inline_cache_stub() && code->ic_state() == UNINITIALIZED;
  97   }
  98   return false;
  99 }
 100
 101
 102 bool TypeFeedbackOracle::StoreIsUninitialized(TypeFeedbackId ast_id) {
 103   Handle<Object> maybe_code = GetInfo(ast_id);
 104   if (!maybe_code->IsCode()) return false;
 105   Handle<Code> code = Handle<Code>::cast(maybe_code);
 106   return code->ic_state() == UNINITIALIZED;
 107 }
 108
 109
 110 bool TypeFeedbackOracle::StoreIsKeyedPolymorphic(TypeFeedbackId ast_id) {
 111   Handle<Object> maybe_code = GetInfo(ast_id);
 112   if (maybe_code->IsCode()) {
 113     Handle<Code> code = Handle<Code>::cast(maybe_code);
 114     return code->is_keyed_store_stub() &&
 115         code->ic_state() == POLYMORPHIC;
 116   }
 117   return false;
 118 }
 119
 120
 121 bool TypeFeedbackOracle::CallIsMonomorphic(int slot) {
 122   Handle<Object> value = GetInfo(slot);
 123   return FLAG_pretenuring_call_new
 124       ? value->IsJSFunction()
 125       : value->IsAllocationSite() || value->IsJSFunction();
 126 }
 127
 128
 129 bool TypeFeedbackOracle::CallNewIsMonomorphic(int slot) {
 130   Handle<Object> info = GetInfo(slot);
 131   return FLAG_pretenuring_call_new
 132       ? info->IsJSFunction()
 133       : info->IsAllocationSite() || info->IsJSFunction();
 134 }
 135
 136
 137 byte TypeFeedbackOracle::ForInType(int feedback_vector_slot) {
 138   Handle<Object> value = GetInfo(feedback_vector_slot);
 139   return value->IsSmi() &&
 140       Smi::cast(*value)->value() == TypeFeedbackInfo::kForInFastCaseMarker
 141           ? ForInStatement::FAST_FOR_IN : ForInStatement::SLOW_FOR_IN;
 142 }
 143
 144
 145 KeyedAccessStoreMode TypeFeedbackOracle::GetStoreMode(
 146     TypeFeedbackId ast_id) {
 147   Handle<Object> maybe_code = GetInfo(ast_id);
 148   if (maybe_code->IsCode()) {
 149     Handle<Code> code = Handle<Code>::cast(maybe_code);
 150     if (code->kind() == Code::KEYED_STORE_IC) {
 151       return KeyedStoreIC::GetKeyedAccessStoreMode(code->extra_ic_state());
 152     }
 153   }
 154   return STANDARD_STORE;
 155 }
 156
 157
 158 Handle<JSFunction> TypeFeedbackOracle::GetCallTarget(int slot) {
 159   Handle<Object> info = GetInfo(slot);
 160   if (FLAG_pretenuring_call_new || info->IsJSFunction()) {
 161     return Handle<JSFunction>::cast(info);
 162   }
 163
 164   ASSERT(info->IsAllocationSite());
 165   return Handle<JSFunction>(isolate()->native_context()->array_function());
 166 }
 167
 168
 169 Handle<JSFunction> TypeFeedbackOracle::GetCallNewTarget(int slot) {
 170   Handle<Object> info = GetInfo(slot);
 171   if (FLAG_pretenuring_call_new || info->IsJSFunction()) {
 172     return Handle<JSFunction>::cast(info);
 173   }
 174
 175   ASSERT(info->IsAllocationSite());
 176   return Handle<JSFunction>(isolate()->native_context()->array_function());
 177 }
 178
 179
 180 Handle<AllocationSite> TypeFeedbackOracle::GetCallNewAllocationSite(int slot) {
 181   Handle<Object> info = GetInfo(slot);
 182   if (FLAG_pretenuring_call_new || info->IsAllocationSite()) {
 183     return Handle<AllocationSite>::cast(info);
 184   }
 185   return Handle<AllocationSite>::null();
 186 }
 187
 188
 189 bool TypeFeedbackOracle::LoadIsBuiltin(
 190     TypeFeedbackId id, Builtins::Name builtin) {
 191   return *GetInfo(id) == isolate()->builtins()->builtin(builtin);
 192 }
 193
 194
 195 bool TypeFeedbackOracle::LoadIsStub(TypeFeedbackId id, ICStub* stub) {
 196   Handle<Object> object = GetInfo(id);
 197   if (!object->IsCode()) return false;
 198   Handle<Code> code = Handle<Code>::cast(object);
 199   if (!code->is_load_stub()) return false;
 200   if (code->ic_state() != MONOMORPHIC) return false;
 201   return stub->Describes(*code);
 202 }
 203
 204
 205 void TypeFeedbackOracle::CompareType(TypeFeedbackId id,
 206                                      Type** left_type,
 207                                      Type** right_type,
 208                                      Type** combined_type) {
 209   Handle<Object> info = GetInfo(id);
 210   if (!info->IsCode()) {
 211     // For some comparisons we don't have ICs, e.g. LiteralCompareTypeof.
 212     *left_type = *right_type = *combined_type = Type::None(zone());
 213     return;
 214   }
 215   Handle<Code> code = Handle<Code>::cast(info);
 216
 217   Handle<Map> map;
 218   Map* raw_map = code->FindFirstMap();
 219   if (raw_map != NULL) {
 220     map = Map::CurrentMapForDeprecated(handle(raw_map));
 221     if (!map.is_null() && CanRetainOtherContext(*map, *native_context_)) {
 222       map = Handle<Map>::null();
 223     }
 224   }
 225
 226   if (code->is_compare_ic_stub()) {
 227     int stub_minor_key = code->stub_info();
 228     CompareIC::StubInfoToType(
 229         stub_minor_key, left_type, right_type, combined_type, map, zone());
 230   } else if (code->is_compare_nil_ic_stub()) {
 231     CompareNilICStub stub(code->extra_ic_state());
 232     *combined_type = stub.GetType(zone(), map);
 233     *left_type = *right_type = stub.GetInputType(zone(), map);
 234   }
 235 }
 236
 237
 238 void TypeFeedbackOracle::BinaryType(TypeFeedbackId id,
 239                                     Type** left,
 240                                     Type** right,
 241                                     Type** result,
 242                                     Maybe<int>* fixed_right_arg,
 243                                     Handle<AllocationSite>* allocation_site,
 244                                     Token::Value op) {
 245   Handle<Object> object = GetInfo(id);
 246   if (!object->IsCode()) {
 247     // For some binary ops we don't have ICs, e.g. Token::COMMA, but for the
 248     // operations covered by the BinaryOpIC we should always have them.
 249     ASSERT(op < BinaryOpIC::State::FIRST_TOKEN ||
 250            op > BinaryOpIC::State::LAST_TOKEN);
 251     *left = *right = *result = Type::None(zone());
 252     *fixed_right_arg = Maybe<int>();
 253     *allocation_site = Handle<AllocationSite>::null();
 254     return;
 255   }
 256   Handle<Code> code = Handle<Code>::cast(object);
 257   ASSERT_EQ(Code::BINARY_OP_IC, code->kind());
 258   BinaryOpIC::State state(code->extra_ic_state());
 259   ASSERT_EQ(op, state.op());
 260
 261   *left = state.GetLeftType(zone());
 262   *right = state.GetRightType(zone());
 263   *result = state.GetResultType(zone());
 264   *fixed_right_arg = state.fixed_right_arg();
 265
 266   AllocationSite* first_allocation_site = code->FindFirstAllocationSite();
 267   if (first_allocation_site != NULL) {
 268     *allocation_site = handle(first_allocation_site);
 269   } else {
 270     *allocation_site = Handle<AllocationSite>::null();
 271   }
 272 }
 273
 274
 275 Type* TypeFeedbackOracle::CountType(TypeFeedbackId id) {
 276   Handle<Object> object = GetInfo(id);
 277   if (!object->IsCode()) return Type::None(zone());
 278   Handle<Code> code = Handle<Code>::cast(object);
 279   ASSERT_EQ(Code::BINARY_OP_IC, code->kind());
 280   BinaryOpIC::State state(code->extra_ic_state());
 281   return state.GetLeftType(zone());
 282 }
 283
 284
 285 void TypeFeedbackOracle::PropertyReceiverTypes(
 286     TypeFeedbackId id, Handle<String> name,
 287     SmallMapList* receiver_types, bool* is_prototype) {
 288   receiver_types->Clear();
 289   FunctionPrototypeStub proto_stub(Code::LOAD_IC);
 290   *is_prototype = LoadIsStub(id, &proto_stub);
 291   if (!*is_prototype) {
 292     Code::Flags flags = Code::ComputeHandlerFlags(Code::LOAD_IC);
 293     CollectReceiverTypes(id, name, flags, receiver_types);
 294   }
 295 }
 296
 297
 298 void TypeFeedbackOracle::KeyedPropertyReceiverTypes(
 299     TypeFeedbackId id, SmallMapList* receiver_types, bool* is_string) {
 300   receiver_types->Clear();
 301   *is_string = false;
 302   if (LoadIsBuiltin(id, Builtins::kKeyedLoadIC_String)) {
 303     *is_string = true;
 304   } else {
 305     CollectReceiverTypes(id, receiver_types);
 306   }
 307 }
 308
 309
 310 void TypeFeedbackOracle::AssignmentReceiverTypes(
 311     TypeFeedbackId id, Handle<String> name, SmallMapList* receiver_types) {
 312   receiver_types->Clear();
 313   Code::Flags flags = Code::ComputeHandlerFlags(Code::STORE_IC);
 314   CollectReceiverTypes(id, name, flags, receiver_types);
 315 }
 316
 317
 318 void TypeFeedbackOracle::KeyedAssignmentReceiverTypes(
 319     TypeFeedbackId id, SmallMapList* receiver_types,
 320     KeyedAccessStoreMode* store_mode) {
 321   receiver_types->Clear();
 322   CollectReceiverTypes(id, receiver_types);
 323   *store_mode = GetStoreMode(id);
 324 }
 325
 326
 327 void TypeFeedbackOracle::CountReceiverTypes(TypeFeedbackId id,
 328                                             SmallMapList* receiver_types) {
 329   receiver_types->Clear();
 330   CollectReceiverTypes(id, receiver_types);
 331 }
 332
 333
 334 void TypeFeedbackOracle::CollectReceiverTypes(TypeFeedbackId ast_id,
 335                                               Handle<String> name,
 336                                               Code::Flags flags,
 337                                               SmallMapList* types) {
 338   Handle<Object> object = GetInfo(ast_id);
 339   if (object->IsUndefined() || object->IsSmi()) return;
 340
 341   ASSERT(object->IsCode());
 342   Handle<Code> code(Handle<Code>::cast(object));
 343
 344   if (FLAG_collect_megamorphic_maps_from_stub_cache &&
 345       code->ic_state() == MEGAMORPHIC) {
 346     types->Reserve(4, zone());
 347     isolate()->stub_cache()->CollectMatchingMaps(
 348         types, name, flags, native_context_, zone());
 349   } else {
 350     CollectReceiverTypes(ast_id, types);
 351   }
 352 }
 353
 354
 355 // Check if a map originates from a given native context. We use this
 356 // information to filter out maps from different context to avoid
 357 // retaining objects from different tabs in Chrome via optimized code.
 358 bool TypeFeedbackOracle::CanRetainOtherContext(Map* map,
 359                                                Context* native_context) {
 360   Object* constructor = NULL;
 361   while (!map->prototype()->IsNull()) {
 362     constructor = map->constructor();
 363     if (!constructor->IsNull()) {
 364       // If the constructor is not null or a JSFunction, we have to
 365       // conservatively assume that it may retain a native context.
 366       if (!constructor->IsJSFunction()) return true;
 367       // Check if the constructor directly references a foreign context.
 368       if (CanRetainOtherContext(JSFunction::cast(constructor),
 369                                 native_context)) {
 370         return true;
 371       }
 372     }
 373     map = HeapObject::cast(map->prototype())->map();
 374   }
 375   constructor = map->constructor();
 376   if (constructor->IsNull()) return false;
 377   JSFunction* function = JSFunction::cast(constructor);
 378   return CanRetainOtherContext(function, native_context);
 379 }
 380
 381
 382 bool TypeFeedbackOracle::CanRetainOtherContext(JSFunction* function,
 383                                                Context* native_context) {
 384   return function->context()->global_object() != native_context->global_object()
 385       && function->context()->global_object() != native_context->builtins();
 386 }
 387
 388
 389 void TypeFeedbackOracle::CollectReceiverTypes(TypeFeedbackId ast_id,
 390                                               SmallMapList* types) {
 391   Handle<Object> object = GetInfo(ast_id);
 392   if (!object->IsCode()) return;
 393   Handle<Code> code = Handle<Code>::cast(object);
 394   MapHandleList maps;
 395   if (code->ic_state() == MONOMORPHIC) {
 396     Map* map = code->FindFirstMap();
 397     if (map != NULL) maps.Add(handle(map));
 398   } else if (code->ic_state() == POLYMORPHIC) {
 399     code->FindAllMaps(&maps);
 400   } else {
 401     return;
 402   }
 403   types->Reserve(maps.length(), zone());
 404   for (int i = 0; i < maps.length(); i++) {
 405     Handle<Map> map(maps.at(i));
 406     if (!CanRetainOtherContext(*map, *native_context_)) {
 407       types->AddMapIfMissing(map, zone());
 408     }
 409   }
 410 }
 411
 412
 413 byte TypeFeedbackOracle::ToBooleanTypes(TypeFeedbackId id) {
 414   Handle<Object> object = GetInfo(id);
 415   return object->IsCode() ? Handle<Code>::cast(object)->to_boolean_state() : 0;
 416 }
 417
 418
 419 // Things are a bit tricky here: The iterator for the RelocInfos and the infos
 420 // themselves are not GC-safe, so we first get all infos, then we create the
 421 // dictionary (possibly triggering GC), and finally we relocate the collected
 422 // infos before we process them.
 423 void TypeFeedbackOracle::BuildDictionary(Handle<Code> code) {
 424   DisallowHeapAllocation no_allocation;
 425   ZoneList<RelocInfo> infos(16, zone());
 426   HandleScope scope(isolate());
 427   GetRelocInfos(code, &infos);
 428   CreateDictionary(code, &infos);
 429   ProcessRelocInfos(&infos);
 430   // Allocate handle in the parent scope.
 431   dictionary_ = scope.CloseAndEscape(dictionary_);
 432 }
 433
 434
 435 void TypeFeedbackOracle::GetRelocInfos(Handle<Code> code,
 436                                        ZoneList<RelocInfo>* infos) {
 437   int mask = RelocInfo::ModeMask(RelocInfo::CODE_TARGET_WITH_ID);
 438   for (RelocIterator it(*code, mask); !it.done(); it.next()) {
 439     infos->Add(*it.rinfo(), zone());
 440   }
 441 }
 442
 443
 444 void TypeFeedbackOracle::CreateDictionary(Handle<Code> code,
 445                                           ZoneList<RelocInfo>* infos) {
 446   AllowHeapAllocation allocation_allowed;
 447   Code* old_code = *code;
 448   dictionary_ =
 449       isolate()->factory()->NewUnseededNumberDictionary(infos->length());
 450   RelocateRelocInfos(infos, old_code, *code);
 451 }
 452
 453
 454 void TypeFeedbackOracle::RelocateRelocInfos(ZoneList<RelocInfo>* infos,
 455                                             Code* old_code,
 456                                             Code* new_code) {
 457   for (int i = 0; i < infos->length(); i++) {
 458     RelocInfo* info = &(*infos)[i];
 459     info->set_host(new_code);
 460     info->set_pc(new_code->instruction_start() +
 461                  (info->pc() - old_code->instruction_start()));
 462   }
 463 }
 464
 465
 466 void TypeFeedbackOracle::ProcessRelocInfos(ZoneList<RelocInfo>* infos) {
 467   for (int i = 0; i < infos->length(); i++) {
 468     RelocInfo reloc_entry = (*infos)[i];
 469     Address target_address = reloc_entry.target_address();
 470     TypeFeedbackId ast_id =
 471         TypeFeedbackId(static_cast<unsigned>((*infos)[i].data()));
 472     Code* target = Code::GetCodeFromTargetAddress(target_address);
 473     switch (target->kind()) {
 474       case Code::LOAD_IC:
 475       case Code::STORE_IC:
 476       case Code::KEYED_LOAD_IC:
 477       case Code::KEYED_STORE_IC:
 478       case Code::BINARY_OP_IC:
 479       case Code::COMPARE_IC:
 480       case Code::TO_BOOLEAN_IC:
 481       case Code::COMPARE_NIL_IC:
 482         SetInfo(ast_id, target);
 483         break;
 484
 485       default:
 486         break;
 487     }
 488   }
 489 }
 490
 491
 492 void TypeFeedbackOracle::SetInfo(TypeFeedbackId ast_id, Object* target) {
 493   ASSERT(dictionary_->FindEntry(IdToKey(ast_id)) ==
 494          UnseededNumberDictionary::kNotFound);
 495   MaybeObject* maybe_result = dictionary_->AtNumberPut(IdToKey(ast_id), target);
 496   USE(maybe_result);
 497 #ifdef DEBUG
 498   Object* result = NULL;
 499   // Dictionary has been allocated with sufficient size for all elements.
 500   ASSERT(maybe_result->ToObject(&result));
 501   ASSERT(*dictionary_ == result);
 502 #endif
 503 }
 504
 505
 506 } }  // namespace v8::internal