• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
TypeFromValue(Handle<Object> value)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 
TypeFeedbackOracle(Handle<Code> code,Handle<Context> global_context)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 
GetInfo(int pos)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 
LoadIsMonomorphic(Property * expr)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 
StoreIsMonomorphic(Expression * expr)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 
CallIsMonomorphic(Call * expr)104 bool TypeFeedbackOracle::CallIsMonomorphic(Call* expr) {
105   Handle<Object> value = GetInfo(expr->position());
106   return value->IsMap() || value->IsSmi();
107 }
108 
109 
LoadMonomorphicReceiverType(Property * expr)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 
StoreMonomorphicReceiverType(Expression * expr)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 
LoadReceiverTypes(Property * expr,Handle<String> name)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 
StoreReceiverTypes(Assignment * expr,Handle<String> name)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 
CallReceiverTypes(Call * expr,Handle<String> name)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 
GetCallCheckType(Call * expr)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 
GetKeyedLoadExternalArrayType(Property * expr)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 
GetKeyedStoreExternalArrayType(Expression * expr)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 
GetPrototypeForPrimitiveCheck(CheckType check)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 
LoadIsBuiltin(Property * expr,Builtins::Name id)209 bool TypeFeedbackOracle::LoadIsBuiltin(Property* expr, Builtins::Name id) {
210   return *GetInfo(expr->position()) ==
211       Isolate::Current()->builtins()->builtin(id);
212 }
213 
214 
CompareType(CompareOperation * expr)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 
BinaryType(BinaryOperation * expr)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 
SwitchType(CaseClause * clause)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 
CollectReceiverTypes(int position,Handle<String> name,Code::Flags flags)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 
SetInfo(int position,Object * target)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 
PopulateMap(Handle<Code> code)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 
CollectPositions(Code * code,List<int> * code_positions,List<int> * source_positions)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