src/3rdparty/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 TypeInfo TypeInfo::TypeFromValue(Handle<Object> value) {
  46   TypeInfo info;
  47   if (value->IsSmi()) {
  48     info = TypeInfo::Smi();
  49   } else if (value->IsHeapNumber()) {
  50     info = TypeInfo::IsInt32Double(HeapNumber::cast(*value)->value())
  51         ? TypeInfo::Integer32()
  52         : TypeInfo::Double();
  53   } else if (value->IsString()) {
  54     info = TypeInfo::String();
  55   } else {
  56     info = TypeInfo::Unknown();
  57   }
  58   return info;
  59 }
  60
  61
  62 TypeFeedbackOracle::TypeFeedbackOracle(Handle<Code> code,
  63                                        Handle<Context> global_context,
  64                                        Isolate* isolate) {
  65   global_context_ = global_context;
  66   isolate_ = isolate;
  67   BuildDictionary(code);
  68   ASSERT(reinterpret_cast<Address>(*dictionary_.location()) != kHandleZapValue);
  69 }
  70
  71
  72 Handle<Object> TypeFeedbackOracle::GetInfo(unsigned ast_id) {
  73   int entry = dictionary_->FindEntry(ast_id);
  74   return entry != UnseededNumberDictionary::kNotFound
  75       ? Handle<Object>(dictionary_->ValueAt(entry))
  76       : Handle<Object>::cast(isolate_->factory()->undefined_value());
  77 }
  78
  79
  80 bool TypeFeedbackOracle::LoadIsUninitialized(Property* expr) {
  81   Handle<Object> map_or_code = GetInfo(expr->id());
  82   if (map_or_code->IsMap()) return false;
  83   if (map_or_code->IsCode()) {
  84     Handle<Code> code = Handle<Code>::cast(map_or_code);
  85     return code->is_inline_cache_stub() && code->ic_state() == UNINITIALIZED;
  86   }
  87   return false;
  88 }
  89
  90
  91 bool TypeFeedbackOracle::LoadIsMonomorphicNormal(Property* expr) {
  92   Handle<Object> map_or_code = GetInfo(expr->id());
  93   if (map_or_code->IsMap()) return true;
  94   if (map_or_code->IsCode()) {
  95     Handle<Code> code = Handle<Code>::cast(map_or_code);
  96     return code->is_keyed_load_stub() &&
  97         code->ic_state() == MONOMORPHIC &&
  98         Code::ExtractTypeFromFlags(code->flags()) == NORMAL &&
  99         code->FindFirstMap() != NULL &&
 100         !CanRetainOtherContext(code->FindFirstMap(), *global_context_);
 101   }
 102   return false;
 103 }
 104
 105
 106 bool TypeFeedbackOracle::LoadIsMegamorphicWithTypeInfo(Property* expr) {
 107   Handle<Object> map_or_code = GetInfo(expr->id());
 108   if (map_or_code->IsCode()) {
 109     Handle<Code> code = Handle<Code>::cast(map_or_code);
 110     Builtins* builtins = isolate_->builtins();
 111     return code->is_keyed_load_stub() &&
 112         *code != builtins->builtin(Builtins::kKeyedLoadIC_Generic) &&
 113         code->ic_state() == MEGAMORPHIC;
 114   }
 115   return false;
 116 }
 117
 118
 119 bool TypeFeedbackOracle::StoreIsMonomorphicNormal(Expression* expr) {
 120   Handle<Object> map_or_code = GetInfo(expr->id());
 121   if (map_or_code->IsMap()) return true;
 122   if (map_or_code->IsCode()) {
 123     Handle<Code> code = Handle<Code>::cast(map_or_code);
 124     bool allow_growth =
 125         Code::GetKeyedAccessGrowMode(code->extra_ic_state()) ==
 126         ALLOW_JSARRAY_GROWTH;
 127     return code->is_keyed_store_stub() &&
 128         !allow_growth &&
 129         code->ic_state() == MONOMORPHIC &&
 130         Code::ExtractTypeFromFlags(code->flags()) == NORMAL &&
 131         code->FindFirstMap() != NULL &&
 132         !CanRetainOtherContext(code->FindFirstMap(), *global_context_);
 133   }
 134   return false;
 135 }
 136
 137
 138 bool TypeFeedbackOracle::StoreIsMegamorphicWithTypeInfo(Expression* expr) {
 139   Handle<Object> map_or_code = GetInfo(expr->id());
 140   if (map_or_code->IsCode()) {
 141     Handle<Code> code = Handle<Code>::cast(map_or_code);
 142     Builtins* builtins = isolate_->builtins();
 143     bool allow_growth =
 144         Code::GetKeyedAccessGrowMode(code->extra_ic_state()) ==
 145         ALLOW_JSARRAY_GROWTH;
 146     return code->is_keyed_store_stub() &&
 147         !allow_growth &&
 148         *code != builtins->builtin(Builtins::kKeyedStoreIC_Generic) &&
 149         *code != builtins->builtin(Builtins::kKeyedStoreIC_Generic_Strict) &&
 150         code->ic_state() == MEGAMORPHIC;
 151   }
 152   return false;
 153 }
 154
 155
 156 bool TypeFeedbackOracle::CallIsMonomorphic(Call* expr) {
 157   Handle<Object> value = GetInfo(expr->id());
 158   return value->IsMap() || value->IsSmi() || value->IsJSFunction();
 159 }
 160
 161
 162 bool TypeFeedbackOracle::CallNewIsMonomorphic(CallNew* expr) {
 163   Handle<Object> value = GetInfo(expr->id());
 164   return value->IsJSFunction();
 165 }
 166
 167
 168 bool TypeFeedbackOracle::ObjectLiteralStoreIsMonomorphic(
 169     ObjectLiteral::Property* prop) {
 170   Handle<Object> map_or_code = GetInfo(prop->key()->id());
 171   return map_or_code->IsMap();
 172 }
 173
 174
 175 bool TypeFeedbackOracle::IsForInFastCase(ForInStatement* stmt) {
 176   Handle<Object> value = GetInfo(stmt->PrepareId());
 177   return value->IsSmi() &&
 178       Smi::cast(*value)->value() == TypeFeedbackCells::kForInFastCaseMarker;
 179 }
 180
 181
 182 Handle<Map> TypeFeedbackOracle::LoadMonomorphicReceiverType(Property* expr) {
 183   ASSERT(LoadIsMonomorphicNormal(expr));
 184   Handle<Object> map_or_code = GetInfo(expr->id());
 185   if (map_or_code->IsCode()) {
 186     Handle<Code> code = Handle<Code>::cast(map_or_code);
 187     Map* first_map = code->FindFirstMap();
 188     ASSERT(first_map != NULL);
 189     return CanRetainOtherContext(first_map, *global_context_)
 190         ? Handle<Map>::null()
 191         : Handle<Map>(first_map);
 192   }
 193   return Handle<Map>::cast(map_or_code);
 194 }
 195
 196
 197 Handle<Map> TypeFeedbackOracle::StoreMonomorphicReceiverType(Expression* expr) {
 198   ASSERT(StoreIsMonomorphicNormal(expr));
 199   Handle<Object> map_or_code = GetInfo(expr->id());
 200   if (map_or_code->IsCode()) {
 201     Handle<Code> code = Handle<Code>::cast(map_or_code);
 202     Map* first_map = code->FindFirstMap();
 203     ASSERT(first_map != NULL);
 204     return CanRetainOtherContext(first_map, *global_context_)
 205         ? Handle<Map>::null()
 206         : Handle<Map>(first_map);
 207   }
 208   return Handle<Map>::cast(map_or_code);
 209 }
 210
 211
 212 void TypeFeedbackOracle::LoadReceiverTypes(Property* expr,
 213                                            Handle<String> name,
 214                                            SmallMapList* types) {
 215   Code::Flags flags = Code::ComputeMonomorphicFlags(Code::LOAD_IC, NORMAL);
 216   CollectReceiverTypes(expr->id(), name, flags, types);
 217 }
 218
 219
 220 void TypeFeedbackOracle::StoreReceiverTypes(Assignment* expr,
 221                                             Handle<String> name,
 222                                             SmallMapList* types) {
 223   Code::Flags flags = Code::ComputeMonomorphicFlags(Code::STORE_IC, NORMAL);
 224   CollectReceiverTypes(expr->id(), name, flags, types);
 225 }
 226
 227
 228 void TypeFeedbackOracle::CallReceiverTypes(Call* expr,
 229                                            Handle<String> name,
 230                                            CallKind call_kind,
 231                                            SmallMapList* types) {
 232   int arity = expr->arguments()->length();
 233
 234   // Note: Currently we do not take string extra ic data into account
 235   // here.
 236   Code::ExtraICState extra_ic_state =
 237       CallIC::Contextual::encode(call_kind == CALL_AS_FUNCTION);
 238
 239   Code::Flags flags = Code::ComputeMonomorphicFlags(Code::CALL_IC,
 240                                                     NORMAL,
 241                                                     extra_ic_state,
 242                                                     OWN_MAP,
 243                                                     arity);
 244   CollectReceiverTypes(expr->id(), name, flags, types);
 245 }
 246
 247
 248 CheckType TypeFeedbackOracle::GetCallCheckType(Call* expr) {
 249   Handle<Object> value = GetInfo(expr->id());
 250   if (!value->IsSmi()) return RECEIVER_MAP_CHECK;
 251   CheckType check = static_cast<CheckType>(Smi::cast(*value)->value());
 252   ASSERT(check != RECEIVER_MAP_CHECK);
 253   return check;
 254 }
 255
 256
 257 Handle<JSObject> TypeFeedbackOracle::GetPrototypeForPrimitiveCheck(
 258     CheckType check) {
 259   JSFunction* function = NULL;
 260   switch (check) {
 261     case RECEIVER_MAP_CHECK:
 262       UNREACHABLE();
 263       break;
 264     case STRING_CHECK:
 265       function = global_context_->string_function();
 266       break;
 267     case NUMBER_CHECK:
 268       function = global_context_->number_function();
 269       break;
 270     case BOOLEAN_CHECK:
 271       function = global_context_->boolean_function();
 272       break;
 273   }
 274   ASSERT(function != NULL);
 275   return Handle<JSObject>(JSObject::cast(function->instance_prototype()));
 276 }
 277
 278
 279 Handle<JSFunction> TypeFeedbackOracle::GetCallTarget(Call* expr) {
 280   return Handle<JSFunction>::cast(GetInfo(expr->id()));
 281 }
 282
 283
 284 Handle<JSFunction> TypeFeedbackOracle::GetCallNewTarget(CallNew* expr) {
 285   return Handle<JSFunction>::cast(GetInfo(expr->id()));
 286 }
 287
 288
 289 Handle<Map> TypeFeedbackOracle::GetObjectLiteralStoreMap(
 290     ObjectLiteral::Property* prop) {
 291   ASSERT(ObjectLiteralStoreIsMonomorphic(prop));
 292   return Handle<Map>::cast(GetInfo(prop->key()->id()));
 293 }
 294
 295
 296 bool TypeFeedbackOracle::LoadIsBuiltin(Property* expr, Builtins::Name id) {
 297   return *GetInfo(expr->id()) ==
 298       isolate_->builtins()->builtin(id);
 299 }
 300
 301
 302 TypeInfo TypeFeedbackOracle::CompareType(CompareOperation* expr) {
 303   Handle<Object> object = GetInfo(expr->id());
 304   TypeInfo unknown = TypeInfo::Unknown();
 305   if (!object->IsCode()) return unknown;
 306   Handle<Code> code = Handle<Code>::cast(object);
 307   if (!code->is_compare_ic_stub()) return unknown;
 308
 309   CompareIC::State state = static_cast<CompareIC::State>(code->compare_state());
 310   switch (state) {
 311     case CompareIC::UNINITIALIZED:
 312       // Uninitialized means never executed.
 313       return TypeInfo::Uninitialized();
 314     case CompareIC::SMIS:
 315       return TypeInfo::Smi();
 316     case CompareIC::HEAP_NUMBERS:
 317       return TypeInfo::Number();
 318     case CompareIC::SYMBOLS:
 319     case CompareIC::STRINGS:
 320       return TypeInfo::String();
 321     case CompareIC::OBJECTS:
 322     case CompareIC::KNOWN_OBJECTS:
 323       // TODO(kasperl): We really need a type for JS objects here.
 324       return TypeInfo::NonPrimitive();
 325     case CompareIC::GENERIC:
 326     default:
 327       return unknown;
 328   }
 329 }
 330
 331
 332 bool TypeFeedbackOracle::IsSymbolCompare(CompareOperation* expr) {
 333   Handle<Object> object = GetInfo(expr->id());
 334   if (!object->IsCode()) return false;
 335   Handle<Code> code = Handle<Code>::cast(object);
 336   if (!code->is_compare_ic_stub()) return false;
 337   CompareIC::State state = static_cast<CompareIC::State>(code->compare_state());
 338   return state == CompareIC::SYMBOLS;
 339 }
 340
 341
 342 Handle<Map> TypeFeedbackOracle::GetCompareMap(CompareOperation* expr) {
 343   Handle<Object> object = GetInfo(expr->id());
 344   if (!object->IsCode()) return Handle<Map>::null();
 345   Handle<Code> code = Handle<Code>::cast(object);
 346   if (!code->is_compare_ic_stub()) return Handle<Map>::null();
 347   CompareIC::State state = static_cast<CompareIC::State>(code->compare_state());
 348   if (state != CompareIC::KNOWN_OBJECTS) {
 349     return Handle<Map>::null();
 350   }
 351   Map* first_map = code->FindFirstMap();
 352   ASSERT(first_map != NULL);
 353   return CanRetainOtherContext(first_map, *global_context_)
 354       ? Handle<Map>::null()
 355       : Handle<Map>(first_map);
 356 }
 357
 358
 359 TypeInfo TypeFeedbackOracle::UnaryType(UnaryOperation* expr) {
 360   Handle<Object> object = GetInfo(expr->id());
 361   TypeInfo unknown = TypeInfo::Unknown();
 362   if (!object->IsCode()) return unknown;
 363   Handle<Code> code = Handle<Code>::cast(object);
 364   ASSERT(code->is_unary_op_stub());
 365   UnaryOpIC::TypeInfo type = static_cast<UnaryOpIC::TypeInfo>(
 366       code->unary_op_type());
 367   switch (type) {
 368     case UnaryOpIC::SMI:
 369       return TypeInfo::Smi();
 370     case UnaryOpIC::HEAP_NUMBER:
 371       return TypeInfo::Double();
 372     default:
 373       return unknown;
 374   }
 375 }
 376
 377
 378 TypeInfo TypeFeedbackOracle::BinaryType(BinaryOperation* expr) {
 379   Handle<Object> object = GetInfo(expr->id());
 380   TypeInfo unknown = TypeInfo::Unknown();
 381   if (!object->IsCode()) return unknown;
 382   Handle<Code> code = Handle<Code>::cast(object);
 383   if (code->is_binary_op_stub()) {
 384     BinaryOpIC::TypeInfo type = static_cast<BinaryOpIC::TypeInfo>(
 385         code->binary_op_type());
 386     BinaryOpIC::TypeInfo result_type = static_cast<BinaryOpIC::TypeInfo>(
 387         code->binary_op_result_type());
 388
 389     switch (type) {
 390       case BinaryOpIC::UNINITIALIZED:
 391         // Uninitialized means never executed.
 392         return TypeInfo::Uninitialized();
 393       case BinaryOpIC::SMI:
 394         switch (result_type) {
 395           case BinaryOpIC::UNINITIALIZED:
 396             if (expr->op() == Token::DIV) {
 397               return TypeInfo::Double();
 398             }
 399             return TypeInfo::Smi();
 400           case BinaryOpIC::SMI:
 401             return TypeInfo::Smi();
 402           case BinaryOpIC::INT32:
 403             return TypeInfo::Integer32();
 404           case BinaryOpIC::HEAP_NUMBER:
 405             return TypeInfo::Double();
 406           default:
 407             return unknown;
 408         }
 409       case BinaryOpIC::INT32:
 410         if (expr->op() == Token::DIV ||
 411             result_type == BinaryOpIC::HEAP_NUMBER) {
 412           return TypeInfo::Double();
 413         }
 414         return TypeInfo::Integer32();
 415       case BinaryOpIC::HEAP_NUMBER:
 416         return TypeInfo::Double();
 417       case BinaryOpIC::BOTH_STRING:
 418         return TypeInfo::String();
 419       case BinaryOpIC::STRING:
 420       case BinaryOpIC::GENERIC:
 421         return unknown;
 422      default:
 423         return unknown;
 424     }
 425   }
 426   return unknown;
 427 }
 428
 429
 430 TypeInfo TypeFeedbackOracle::SwitchType(CaseClause* clause) {
 431   Handle<Object> object = GetInfo(clause->CompareId());
 432   TypeInfo unknown = TypeInfo::Unknown();
 433   if (!object->IsCode()) return unknown;
 434   Handle<Code> code = Handle<Code>::cast(object);
 435   if (!code->is_compare_ic_stub()) return unknown;
 436
 437   CompareIC::State state = static_cast<CompareIC::State>(code->compare_state());
 438   switch (state) {
 439     case CompareIC::UNINITIALIZED:
 440       // Uninitialized means never executed.
 441       // TODO(fschneider): Introduce a separate value for never-executed ICs.
 442       return unknown;
 443     case CompareIC::SMIS:
 444       return TypeInfo::Smi();
 445     case CompareIC::STRINGS:
 446       return TypeInfo::String();
 447     case CompareIC::SYMBOLS:
 448       return TypeInfo::Symbol();
 449     case CompareIC::HEAP_NUMBERS:
 450       return TypeInfo::Number();
 451     case CompareIC::OBJECTS:
 452     case CompareIC::KNOWN_OBJECTS:
 453       // TODO(kasperl): We really need a type for JS objects here.
 454       return TypeInfo::NonPrimitive();
 455     case CompareIC::GENERIC:
 456     default:
 457       return unknown;
 458   }
 459 }
 460
 461
 462 TypeInfo TypeFeedbackOracle::IncrementType(CountOperation* expr) {
 463   Handle<Object> object = GetInfo(expr->CountId());
 464   TypeInfo unknown = TypeInfo::Unknown();
 465   if (!object->IsCode()) return unknown;
 466   Handle<Code> code = Handle<Code>::cast(object);
 467   if (!code->is_binary_op_stub()) return unknown;
 468
 469   BinaryOpIC::TypeInfo type = static_cast<BinaryOpIC::TypeInfo>(
 470       code->binary_op_type());
 471   switch (type) {
 472     case BinaryOpIC::UNINITIALIZED:
 473     case BinaryOpIC::SMI:
 474       return TypeInfo::Smi();
 475     case BinaryOpIC::INT32:
 476       return TypeInfo::Integer32();
 477     case BinaryOpIC::HEAP_NUMBER:
 478       return TypeInfo::Double();
 479     case BinaryOpIC::BOTH_STRING:
 480     case BinaryOpIC::STRING:
 481     case BinaryOpIC::GENERIC:
 482       return unknown;
 483     default:
 484       return unknown;
 485   }
 486   UNREACHABLE();
 487   return unknown;
 488 }
 489
 490
 491 void TypeFeedbackOracle::CollectReceiverTypes(unsigned ast_id,
 492                                               Handle<String> name,
 493                                               Code::Flags flags,
 494                                               SmallMapList* types) {
 495   Handle<Object> object = GetInfo(ast_id);
 496   if (object->IsUndefined() || object->IsSmi()) return;
 497
 498   if (*object ==
 499       isolate_->builtins()->builtin(Builtins::kStoreIC_GlobalProxy)) {
 500     // TODO(fschneider): We could collect the maps and signal that
 501     // we need a generic store (or load) here.
 502     ASSERT(Handle<Code>::cast(object)->ic_state() == MEGAMORPHIC);
 503   } else if (object->IsMap()) {
 504     types->Add(Handle<Map>::cast(object));
 505   } else if (FLAG_collect_megamorphic_maps_from_stub_cache &&
 506       Handle<Code>::cast(object)->ic_state() == MEGAMORPHIC) {
 507     types->Reserve(4);
 508     ASSERT(object->IsCode());
 509     isolate_->stub_cache()->CollectMatchingMaps(types,
 510                                                 *name,
 511                                                 flags,
 512                                                 global_context_);
 513   }
 514 }
 515
 516
 517 // Check if a map originates from a given global context. We use this
 518 // information to filter out maps from different context to avoid
 519 // retaining objects from different tabs in Chrome via optimized code.
 520 bool TypeFeedbackOracle::CanRetainOtherContext(Map* map,
 521                                                Context* global_context) {
 522   Object* constructor = NULL;
 523   while (!map->prototype()->IsNull()) {
 524     constructor = map->constructor();
 525     if (!constructor->IsNull()) {
 526       // If the constructor is not null or a JSFunction, we have to
 527       // conservatively assume that it may retain a global context.
 528       if (!constructor->IsJSFunction()) return true;
 529       // Check if the constructor directly references a foreign context.
 530       if (CanRetainOtherContext(JSFunction::cast(constructor),
 531                                 global_context)) {
 532         return true;
 533       }
 534     }
 535     map = HeapObject::cast(map->prototype())->map();
 536   }
 537   constructor = map->constructor();
 538   if (constructor->IsNull()) return false;
 539   JSFunction* function = JSFunction::cast(constructor);
 540   return CanRetainOtherContext(function, global_context);
 541 }
 542
 543
 544 bool TypeFeedbackOracle::CanRetainOtherContext(JSFunction* function,
 545                                                Context* global_context) {
 546   return function->context()->global() != global_context->global()
 547       && function->context()->global() != global_context->builtins();
 548 }
 549
 550
 551 static void AddMapIfMissing(Handle<Map> map, SmallMapList* list) {
 552   for (int i = 0; i < list->length(); ++i) {
 553     if (list->at(i).is_identical_to(map)) return;
 554   }
 555   list->Add(map);
 556 }
 557
 558
 559 void TypeFeedbackOracle::CollectKeyedReceiverTypes(unsigned ast_id,
 560                                                    SmallMapList* types) {
 561   Handle<Object> object = GetInfo(ast_id);
 562   if (!object->IsCode()) return;
 563   Handle<Code> code = Handle<Code>::cast(object);
 564   if (code->kind() == Code::KEYED_LOAD_IC ||
 565       code->kind() == Code::KEYED_STORE_IC) {
 566     AssertNoAllocation no_allocation;
 567     int mask = RelocInfo::ModeMask(RelocInfo::EMBEDDED_OBJECT);
 568     for (RelocIterator it(*code, mask); !it.done(); it.next()) {
 569       RelocInfo* info = it.rinfo();
 570       Object* object = info->target_object();
 571       if (object->IsMap()) {
 572         Map* map = Map::cast(object);
 573         if (!CanRetainOtherContext(map, *global_context_)) {
 574           AddMapIfMissing(Handle<Map>(map), types);
 575         }
 576       }
 577     }
 578   }
 579 }
 580
 581
 582 byte TypeFeedbackOracle::ToBooleanTypes(unsigned ast_id) {
 583   Handle<Object> object = GetInfo(ast_id);
 584   return object->IsCode() ? Handle<Code>::cast(object)->to_boolean_state() : 0;
 585 }
 586
 587
 588 // Things are a bit tricky here: The iterator for the RelocInfos and the infos
 589 // themselves are not GC-safe, so we first get all infos, then we create the
 590 // dictionary (possibly triggering GC), and finally we relocate the collected
 591 // infos before we process them.
 592 void TypeFeedbackOracle::BuildDictionary(Handle<Code> code) {
 593   AssertNoAllocation no_allocation;
 594   ZoneList<RelocInfo> infos(16);
 595   HandleScope scope;
 596   GetRelocInfos(code, &infos);
 597   CreateDictionary(code, &infos);
 598   ProcessRelocInfos(&infos);
 599   ProcessTypeFeedbackCells(code);
 600   // Allocate handle in the parent scope.
 601   dictionary_ = scope.CloseAndEscape(dictionary_);
 602 }
 603
 604
 605 void TypeFeedbackOracle::GetRelocInfos(Handle<Code> code,
 606                                        ZoneList<RelocInfo>* infos) {
 607   int mask = RelocInfo::ModeMask(RelocInfo::CODE_TARGET_WITH_ID);
 608   for (RelocIterator it(*code, mask); !it.done(); it.next()) {
 609     infos->Add(*it.rinfo());
 610   }
 611 }
 612
 613
 614 void TypeFeedbackOracle::CreateDictionary(Handle<Code> code,
 615                                           ZoneList<RelocInfo>* infos) {
 616   DisableAssertNoAllocation allocation_allowed;
 617   int cell_count = code->type_feedback_info()->IsTypeFeedbackInfo()
 618       ? TypeFeedbackInfo::cast(code->type_feedback_info())->
 619           type_feedback_cells()->CellCount()
 620       : 0;
 621   int length = infos->length() + cell_count;
 622   byte* old_start = code->instruction_start();
 623   dictionary_ = FACTORY->NewUnseededNumberDictionary(length);
 624   byte* new_start = code->instruction_start();
 625   RelocateRelocInfos(infos, old_start, new_start);
 626 }
 627
 628
 629 void TypeFeedbackOracle::RelocateRelocInfos(ZoneList<RelocInfo>* infos,
 630                                             byte* old_start,
 631                                             byte* new_start) {
 632   for (int i = 0; i < infos->length(); i++) {
 633     RelocInfo* info = &(*infos)[i];
 634     info->set_pc(new_start + (info->pc() - old_start));
 635   }
 636 }
 637
 638
 639 void TypeFeedbackOracle::ProcessRelocInfos(ZoneList<RelocInfo>* infos) {
 640   for (int i = 0; i < infos->length(); i++) {
 641     RelocInfo reloc_entry = (*infos)[i];
 642     Address target_address = reloc_entry.target_address();
 643     unsigned ast_id = static_cast<unsigned>((*infos)[i].data());
 644     Code* target = Code::GetCodeFromTargetAddress(target_address);
 645     switch (target->kind()) {
 646       case Code::LOAD_IC:
 647       case Code::STORE_IC:
 648       case Code::CALL_IC:
 649       case Code::KEYED_CALL_IC:
 650         if (target->ic_state() == MONOMORPHIC) {
 651           if (target->kind() == Code::CALL_IC &&
 652               target->check_type() != RECEIVER_MAP_CHECK) {
 653             SetInfo(ast_id, Smi::FromInt(target->check_type()));
 654           } else {
 655             Object* map = target->FindFirstMap();
 656             if (map == NULL) {
 657               SetInfo(ast_id, static_cast<Object*>(target));
 658             } else if (!CanRetainOtherContext(Map::cast(map),
 659                                               *global_context_)) {
 660               SetInfo(ast_id, map);
 661             }
 662           }
 663         } else {
 664           SetInfo(ast_id, target);
 665         }
 666         break;
 667
 668       case Code::KEYED_LOAD_IC:
 669       case Code::KEYED_STORE_IC:
 670         if (target->ic_state() == MONOMORPHIC ||
 671             target->ic_state() == MEGAMORPHIC) {
 672           SetInfo(ast_id, target);
 673         }
 674         break;
 675
 676       case Code::UNARY_OP_IC:
 677       case Code::BINARY_OP_IC:
 678       case Code::COMPARE_IC:
 679       case Code::TO_BOOLEAN_IC:
 680         SetInfo(ast_id, target);
 681         break;
 682
 683       default:
 684         break;
 685     }
 686   }
 687 }
 688
 689
 690 void TypeFeedbackOracle::ProcessTypeFeedbackCells(Handle<Code> code) {
 691   Object* raw_info = code->type_feedback_info();
 692   if (!raw_info->IsTypeFeedbackInfo()) return;
 693   Handle<TypeFeedbackCells> cache(
 694       TypeFeedbackInfo::cast(raw_info)->type_feedback_cells());
 695   for (int i = 0; i < cache->CellCount(); i++) {
 696     unsigned ast_id = cache->AstId(i)->value();
 697     Object* value = cache->Cell(i)->value();
 698     if (value->IsSmi() ||
 699         (value->IsJSFunction() &&
 700          !CanRetainOtherContext(JSFunction::cast(value),
 701                                 *global_context_))) {
 702       SetInfo(ast_id, value);
 703     }
 704   }
 705 }
 706
 707
 708 void TypeFeedbackOracle::SetInfo(unsigned ast_id, Object* target) {
 709   ASSERT(dictionary_->FindEntry(ast_id) == UnseededNumberDictionary::kNotFound);
 710   MaybeObject* maybe_result = dictionary_->AtNumberPut(ast_id, target);
 711   USE(maybe_result);
 712 #ifdef DEBUG
 713   Object* result = NULL;
 714   // Dictionary has been allocated with sufficient size for all elements.
 715   ASSERT(maybe_result->ToObject(&result));
 716   ASSERT(*dictionary_ == result);
 717 #endif
 718 }
 719
 720 } }  // namespace v8::internal