Home | History | Annotate | Download | only in src 
      1 // Copyright 2011 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 "compiler.h"
     32 #include "ic.h"
     33 #include "macro-assembler.h"
     34 #include "stub-cache.h"
     35 #include "type-info.h"
     36 
     37 #include "ic-inl.h"
     38 #include "objects-inl.h"
     39 
     40 namespace v8 {
     41 namespace internal {
     42 
     43 
     44 TypeInfo TypeInfo::TypeFromValue(Handle<Object> value) {
     45   TypeInfo info;
     46   if (value->IsSmi()) {
     47     info = TypeInfo::Smi();
     48   } else if (value->IsHeapNumber()) {
     49     info = TypeInfo::IsInt32Double(HeapNumber::cast(*value)->value())
     50         ? TypeInfo::Integer32()
     51         : TypeInfo::Double();
     52   } else if (value->IsString()) {
     53     info = TypeInfo::String();
     54   } else {
     55     info = TypeInfo::Unknown();
     56   }
     57   return info;
     58 }
     59 
     60 
     61 STATIC_ASSERT(DEFAULT_STRING_STUB == Code::kNoExtraICState);
     62 
     63 
     64 TypeFeedbackOracle::TypeFeedbackOracle(Handle<Code> code,
     65                                        Handle<Context> global_context) {
     66   global_context_ = global_context;
     67   PopulateMap(code);
     68   ASSERT(reinterpret_cast<Address>(*dictionary_.location()) != kHandleZapValue);
     69 }
     70 
     71 
     72 Handle<Object> TypeFeedbackOracle::GetInfo(int pos) {
     73   int entry = dictionary_->FindEntry(pos);
     74   return entry != NumberDictionary::kNotFound
     75       ? Handle<Object>(dictionary_->ValueAt(entry))
     76       : Isolate::Current()->factory()->undefined_value();
     77 }
     78 
     79 
     80 bool TypeFeedbackOracle::LoadIsMonomorphic(Property* expr) {
     81   Handle<Object> map_or_code(GetInfo(expr->position()));
     82   if (map_or_code->IsMap()) return true;
     83   if (map_or_code->IsCode()) {
     84     Handle<Code> code(Code::cast(*map_or_code));
     85     return code->kind() == Code::KEYED_EXTERNAL_ARRAY_LOAD_IC &&
     86         code->FindFirstMap() != NULL;
     87   }
     88   return false;
     89 }
     90 
     91 
     92 bool TypeFeedbackOracle::StoreIsMonomorphic(Expression* expr) {
     93   Handle<Object> map_or_code(GetInfo(expr->position()));
     94   if (map_or_code->IsMap()) return true;
     95   if (map_or_code->IsCode()) {
     96     Handle<Code> code(Code::cast(*map_or_code));
     97     return code->kind() == Code::KEYED_EXTERNAL_ARRAY_STORE_IC &&
     98         code->FindFirstMap() != NULL;
     99   }
    100   return false;
    101 }
    102 
    103 
    104 bool TypeFeedbackOracle::CallIsMonomorphic(Call* expr) {
    105   Handle<Object> value = GetInfo(expr->position());
    106   return value->IsMap() || value->IsSmi();
    107 }
    108 
    109 
    110 Handle<Map> TypeFeedbackOracle::LoadMonomorphicReceiverType(Property* expr) {
    111   ASSERT(LoadIsMonomorphic(expr));
    112   Handle<Object> map_or_code(
    113       Handle<HeapObject>::cast(GetInfo(expr->position())));
    114   if (map_or_code->IsCode()) {
    115     Handle<Code> code(Code::cast(*map_or_code));
    116     return Handle<Map>(code->FindFirstMap());
    117   }
    118   return Handle<Map>(Map::cast(*map_or_code));
    119 }
    120 
    121 
    122 Handle<Map> TypeFeedbackOracle::StoreMonomorphicReceiverType(Expression* expr) {
    123   ASSERT(StoreIsMonomorphic(expr));
    124   Handle<HeapObject> map_or_code(
    125       Handle<HeapObject>::cast(GetInfo(expr->position())));
    126   if (map_or_code->IsCode()) {
    127     Handle<Code> code(Code::cast(*map_or_code));
    128     return Handle<Map>(code->FindFirstMap());
    129   }
    130   return Handle<Map>(Map::cast(*map_or_code));
    131 }
    132 
    133 
    134 ZoneMapList* TypeFeedbackOracle::LoadReceiverTypes(Property* expr,
    135                                                    Handle<String> name) {
    136   Code::Flags flags = Code::ComputeMonomorphicFlags(Code::LOAD_IC, NORMAL);
    137   return CollectReceiverTypes(expr->position(), name, flags);
    138 }
    139 
    140 
    141 ZoneMapList* TypeFeedbackOracle::StoreReceiverTypes(Assignment* expr,
    142                                                     Handle<String> name) {
    143   Code::Flags flags = Code::ComputeMonomorphicFlags(Code::STORE_IC, NORMAL);
    144   return CollectReceiverTypes(expr->position(), name, flags);
    145 }
    146 
    147 
    148 ZoneMapList* TypeFeedbackOracle::CallReceiverTypes(Call* expr,
    149                                                    Handle<String> name) {
    150   int arity = expr->arguments()->length();
    151   // Note: these flags won't let us get maps from stubs with
    152   // non-default extra ic state in the megamorphic case. In the more
    153   // important monomorphic case the map is obtained directly, so it's
    154   // not a problem until we decide to emit more polymorphic code.
    155   Code::Flags flags = Code::ComputeMonomorphicFlags(Code::CALL_IC,
    156                                                     NORMAL,
    157                                                     Code::kNoExtraICState,
    158                                                     OWN_MAP,
    159                                                     NOT_IN_LOOP,
    160                                                     arity);
    161   return CollectReceiverTypes(expr->position(), name, flags);
    162 }
    163 
    164 
    165 CheckType TypeFeedbackOracle::GetCallCheckType(Call* expr) {
    166   Handle<Object> value = GetInfo(expr->position());
    167   if (!value->IsSmi()) return RECEIVER_MAP_CHECK;
    168   CheckType check = static_cast<CheckType>(Smi::cast(*value)->value());
    169   ASSERT(check != RECEIVER_MAP_CHECK);
    170   return check;
    171 }
    172 
    173 ExternalArrayType TypeFeedbackOracle::GetKeyedLoadExternalArrayType(
    174     Property* expr) {
    175   Handle<Object> stub = GetInfo(expr->position());
    176   ASSERT(stub->IsCode());
    177   return Code::cast(*stub)->external_array_type();
    178 }
    179 
    180 ExternalArrayType TypeFeedbackOracle::GetKeyedStoreExternalArrayType(
    181     Expression* expr) {
    182   Handle<Object> stub = GetInfo(expr->position());
    183   ASSERT(stub->IsCode());
    184   return Code::cast(*stub)->external_array_type();
    185 }
    186 
    187 Handle<JSObject> TypeFeedbackOracle::GetPrototypeForPrimitiveCheck(
    188     CheckType check) {
    189   JSFunction* function = NULL;
    190   switch (check) {
    191     case RECEIVER_MAP_CHECK:
    192       UNREACHABLE();
    193       break;
    194     case STRING_CHECK:
    195       function = global_context_->string_function();
    196       break;
    197     case NUMBER_CHECK:
    198       function = global_context_->number_function();
    199       break;
    200     case BOOLEAN_CHECK:
    201       function = global_context_->boolean_function();
    202       break;
    203   }
    204   ASSERT(function != NULL);
    205   return Handle<JSObject>(JSObject::cast(function->instance_prototype()));
    206 }
    207 
    208 
    209 bool TypeFeedbackOracle::LoadIsBuiltin(Property* expr, Builtins::Name id) {
    210   return *GetInfo(expr->position()) ==
    211       Isolate::Current()->builtins()->builtin(id);
    212 }
    213 
    214 
    215 TypeInfo TypeFeedbackOracle::CompareType(CompareOperation* expr) {
    216   Handle<Object> object = GetInfo(expr->position());
    217   TypeInfo unknown = TypeInfo::Unknown();
    218   if (!object->IsCode()) return unknown;
    219   Handle<Code> code = Handle<Code>::cast(object);
    220   if (!code->is_compare_ic_stub()) return unknown;
    221 
    222   CompareIC::State state = static_cast<CompareIC::State>(code->compare_state());
    223   switch (state) {
    224     case CompareIC::UNINITIALIZED:
    225       // Uninitialized means never executed.
    226       // TODO(fschneider): Introduce a separate value for never-executed ICs.
    227       return unknown;
    228     case CompareIC::SMIS:
    229       return TypeInfo::Smi();
    230     case CompareIC::HEAP_NUMBERS:
    231       return TypeInfo::Number();
    232     case CompareIC::OBJECTS:
    233       // TODO(kasperl): We really need a type for JS objects here.
    234       return TypeInfo::NonPrimitive();
    235     case CompareIC::GENERIC:
    236     default:
    237       return unknown;
    238   }
    239 }
    240 
    241 
    242 TypeInfo TypeFeedbackOracle::BinaryType(BinaryOperation* expr) {
    243   Handle<Object> object = GetInfo(expr->position());
    244   TypeInfo unknown = TypeInfo::Unknown();
    245   if (!object->IsCode()) return unknown;
    246   Handle<Code> code = Handle<Code>::cast(object);
    247   if (code->is_type_recording_binary_op_stub()) {
    248     TRBinaryOpIC::TypeInfo type = static_cast<TRBinaryOpIC::TypeInfo>(
    249         code->type_recording_binary_op_type());
    250     TRBinaryOpIC::TypeInfo result_type = static_cast<TRBinaryOpIC::TypeInfo>(
    251         code->type_recording_binary_op_result_type());
    252 
    253     switch (type) {
    254       case TRBinaryOpIC::UNINITIALIZED:
    255         // Uninitialized means never executed.
    256         // TODO(fschneider): Introduce a separate value for never-executed ICs
    257         return unknown;
    258       case TRBinaryOpIC::SMI:
    259         switch (result_type) {
    260           case TRBinaryOpIC::UNINITIALIZED:
    261           case TRBinaryOpIC::SMI:
    262             return TypeInfo::Smi();
    263           case TRBinaryOpIC::INT32:
    264             return TypeInfo::Integer32();
    265           case TRBinaryOpIC::HEAP_NUMBER:
    266             return TypeInfo::Double();
    267           default:
    268             return unknown;
    269         }
    270       case TRBinaryOpIC::INT32:
    271         if (expr->op() == Token::DIV ||
    272             result_type == TRBinaryOpIC::HEAP_NUMBER) {
    273           return TypeInfo::Double();
    274         }
    275         return TypeInfo::Integer32();
    276       case TRBinaryOpIC::HEAP_NUMBER:
    277         return TypeInfo::Double();
    278       case TRBinaryOpIC::STRING:
    279       case TRBinaryOpIC::GENERIC:
    280         return unknown;
    281      default:
    282         return unknown;
    283     }
    284   }
    285   return unknown;
    286 }
    287 
    288 
    289 TypeInfo TypeFeedbackOracle::SwitchType(CaseClause* clause) {
    290   Handle<Object> object = GetInfo(clause->position());
    291   TypeInfo unknown = TypeInfo::Unknown();
    292   if (!object->IsCode()) return unknown;
    293   Handle<Code> code = Handle<Code>::cast(object);
    294   if (!code->is_compare_ic_stub()) return unknown;
    295 
    296   CompareIC::State state = static_cast<CompareIC::State>(code->compare_state());
    297   switch (state) {
    298     case CompareIC::UNINITIALIZED:
    299       // Uninitialized means never executed.
    300       // TODO(fschneider): Introduce a separate value for never-executed ICs.
    301       return unknown;
    302     case CompareIC::SMIS:
    303       return TypeInfo::Smi();
    304     case CompareIC::HEAP_NUMBERS:
    305       return TypeInfo::Number();
    306     case CompareIC::OBJECTS:
    307       // TODO(kasperl): We really need a type for JS objects here.
    308       return TypeInfo::NonPrimitive();
    309     case CompareIC::GENERIC:
    310     default:
    311       return unknown;
    312   }
    313 }
    314 
    315 
    316 ZoneMapList* TypeFeedbackOracle::CollectReceiverTypes(int position,
    317                                                       Handle<String> name,
    318                                                       Code::Flags flags) {
    319   Isolate* isolate = Isolate::Current();
    320   Handle<Object> object = GetInfo(position);
    321   if (object->IsUndefined() || object->IsSmi()) return NULL;
    322 
    323   if (*object == isolate->builtins()->builtin(Builtins::kStoreIC_GlobalProxy)) {
    324     // TODO(fschneider): We could collect the maps and signal that
    325     // we need a generic store (or load) here.
    326     ASSERT(Handle<Code>::cast(object)->ic_state() == MEGAMORPHIC);
    327     return NULL;
    328   } else if (object->IsMap()) {
    329     ZoneMapList* types = new ZoneMapList(1);
    330     types->Add(Handle<Map>::cast(object));
    331     return types;
    332   } else if (Handle<Code>::cast(object)->ic_state() == MEGAMORPHIC) {
    333     ZoneMapList* types = new ZoneMapList(4);
    334     ASSERT(object->IsCode());
    335     isolate->stub_cache()->CollectMatchingMaps(types, *name, flags);
    336     return types->length() > 0 ? types : NULL;
    337   } else {
    338     return NULL;
    339   }
    340 }
    341 
    342 
    343 void TypeFeedbackOracle::SetInfo(int position, Object* target) {
    344   MaybeObject* maybe_result = dictionary_->AtNumberPut(position, target);
    345   USE(maybe_result);
    346 #ifdef DEBUG
    347   Object* result;
    348   // Dictionary has been allocated with sufficient size for all elements.
    349   ASSERT(maybe_result->ToObject(&result));
    350   ASSERT(*dictionary_ == result);
    351 #endif
    352 }
    353 
    354 
    355 void TypeFeedbackOracle::PopulateMap(Handle<Code> code) {
    356   Isolate* isolate = Isolate::Current();
    357   HandleScope scope(isolate);
    358 
    359   const int kInitialCapacity = 16;
    360   List<int> code_positions(kInitialCapacity);
    361   List<int> source_positions(kInitialCapacity);
    362   CollectPositions(*code, &code_positions, &source_positions);
    363 
    364   ASSERT(dictionary_.is_null());  // Only initialize once.
    365   dictionary_ = isolate->factory()->NewNumberDictionary(
    366       code_positions.length());
    367 
    368   int length = code_positions.length();
    369   ASSERT(source_positions.length() == length);
    370   for (int i = 0; i < length; i++) {
    371     AssertNoAllocation no_allocation;
    372     RelocInfo info(code->instruction_start() + code_positions[i],
    373                    RelocInfo::CODE_TARGET, 0);
    374     Code* target = Code::GetCodeFromTargetAddress(info.target_address());
    375     int position = source_positions[i];
    376     InlineCacheState state = target->ic_state();
    377     Code::Kind kind = target->kind();
    378 
    379     if (kind == Code::TYPE_RECORDING_BINARY_OP_IC ||
    380         kind == Code::COMPARE_IC) {
    381       // TODO(kasperl): Avoid having multiple ICs with the same
    382       // position by making sure that we have position information
    383       // recorded for all binary ICs.
    384       int entry = dictionary_->FindEntry(position);
    385       if (entry == NumberDictionary::kNotFound) {
    386         SetInfo(position, target);
    387       }
    388     } else if (state == MONOMORPHIC) {
    389       if (kind == Code::KEYED_EXTERNAL_ARRAY_LOAD_IC ||
    390           kind == Code::KEYED_EXTERNAL_ARRAY_STORE_IC) {
    391         SetInfo(position, target);
    392       } else if (target->kind() != Code::CALL_IC ||
    393           target->check_type() == RECEIVER_MAP_CHECK) {
    394         Map* map = target->FindFirstMap();
    395         if (map == NULL) {
    396           SetInfo(position, target);
    397         } else {
    398           SetInfo(position, map);
    399         }
    400       } else {
    401         ASSERT(target->kind() == Code::CALL_IC);
    402         CheckType check = target->check_type();
    403         ASSERT(check != RECEIVER_MAP_CHECK);
    404         SetInfo(position, Smi::FromInt(check));
    405       }
    406     } else if (state == MEGAMORPHIC) {
    407       SetInfo(position, target);
    408     }
    409   }
    410   // Allocate handle in the parent scope.
    411   dictionary_ = scope.CloseAndEscape(dictionary_);
    412 }
    413 
    414 
    415 void TypeFeedbackOracle::CollectPositions(Code* code,
    416                                           List<int>* code_positions,
    417                                           List<int>* source_positions) {
    418   AssertNoAllocation no_allocation;
    419   int position = 0;
    420   // Because the ICs we use for global variables access in the full
    421   // code generator do not have any meaningful positions, we avoid
    422   // collecting those by filtering out contextual code targets.
    423   int mask = RelocInfo::ModeMask(RelocInfo::CODE_TARGET) |
    424       RelocInfo::kPositionMask;
    425   for (RelocIterator it(code, mask); !it.done(); it.next()) {
    426     RelocInfo* info = it.rinfo();
    427     RelocInfo::Mode mode = info->rmode();
    428     if (RelocInfo::IsCodeTarget(mode)) {
    429       Code* target = Code::GetCodeFromTargetAddress(info->target_address());
    430       if (target->is_inline_cache_stub()) {
    431         InlineCacheState state = target->ic_state();
    432         Code::Kind kind = target->kind();
    433         if (kind == Code::TYPE_RECORDING_BINARY_OP_IC) {
    434           if (target->type_recording_binary_op_type() ==
    435               TRBinaryOpIC::GENERIC) {
    436             continue;
    437           }
    438         } else if (kind == Code::COMPARE_IC) {
    439           if (target->compare_state() == CompareIC::GENERIC) continue;
    440         } else {
    441           if (state != MONOMORPHIC && state != MEGAMORPHIC) continue;
    442         }
    443         code_positions->Add(
    444             static_cast<int>(info->pc() - code->instruction_start()));
    445         source_positions->Add(position);
    446       }
    447     } else {
    448       ASSERT(RelocInfo::IsPosition(mode));
    449       position = static_cast<int>(info->data());
    450     }
    451   }
    452 }
    453 
    454 } }  // namespace v8::internal
    455