Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : /* Inline members for javascript type inference. */
8 :
9 : #ifndef vm_TypeInference_inl_h
10 : #define vm_TypeInference_inl_h
11 :
12 : #include "vm/TypeInference.h"
13 :
14 : #include "mozilla/BinarySearch.h"
15 : #include "mozilla/Casting.h"
16 : #include "mozilla/PodOperations.h"
17 :
18 : #include "builtin/SymbolObject.h"
19 : #include "jit/BaselineJIT.h"
20 : #include "vm/ArrayObject.h"
21 : #include "vm/BooleanObject.h"
22 : #include "vm/NumberObject.h"
23 : #include "vm/SharedArrayObject.h"
24 : #include "vm/StringObject.h"
25 : #include "vm/TypedArrayObject.h"
26 : #include "vm/UnboxedObject.h"
27 :
28 : #include "jscntxtinlines.h"
29 :
30 : #include "vm/ObjectGroup-inl.h"
31 :
32 : namespace js {
33 :
34 : /////////////////////////////////////////////////////////////////////
35 : // CompilerOutput & RecompileInfo
36 : /////////////////////////////////////////////////////////////////////
37 :
38 : inline jit::IonScript*
39 0 : CompilerOutput::ion() const
40 : {
41 : // Note: If type constraints are generated before compilation has finished
42 : // (i.e. after IonBuilder but before CodeGenerator::link) then a valid
43 : // CompilerOutput may not yet have an associated IonScript.
44 0 : MOZ_ASSERT(isValid());
45 0 : jit::IonScript* ion = script()->maybeIonScript();
46 0 : MOZ_ASSERT(ion != ION_COMPILING_SCRIPT);
47 0 : return ion;
48 : }
49 :
50 : inline CompilerOutput*
51 5 : RecompileInfo::compilerOutput(TypeZone& types) const
52 : {
53 5 : if (generation != types.generation) {
54 0 : if (!types.sweepCompilerOutputs || outputIndex >= types.sweepCompilerOutputs->length())
55 0 : return nullptr;
56 0 : CompilerOutput* output = &(*types.sweepCompilerOutputs)[outputIndex];
57 0 : if (!output->isValid())
58 0 : return nullptr;
59 0 : output = &(*types.compilerOutputs)[output->sweepIndex()];
60 0 : return output->isValid() ? output : nullptr;
61 : }
62 :
63 5 : if (!types.compilerOutputs || outputIndex >= types.compilerOutputs->length())
64 0 : return nullptr;
65 5 : CompilerOutput* output = &(*types.compilerOutputs)[outputIndex];
66 5 : return output->isValid() ? output : nullptr;
67 : }
68 :
69 : inline CompilerOutput*
70 0 : RecompileInfo::compilerOutput(JSContext* cx) const
71 : {
72 0 : return compilerOutput(cx->zone()->types);
73 : }
74 :
75 : inline bool
76 0 : RecompileInfo::shouldSweep(TypeZone& types)
77 : {
78 0 : CompilerOutput* output = compilerOutput(types);
79 0 : if (!output || !output->isValid())
80 0 : return true;
81 :
82 : // If this info is for a compilation that occurred after sweeping started,
83 : // the index is already correct.
84 0 : MOZ_ASSERT_IF(generation == types.generation,
85 : outputIndex == output - types.compilerOutputs->begin());
86 :
87 : // Update this info for the output's index in the zone's compiler outputs.
88 0 : outputIndex = output - types.compilerOutputs->begin();
89 0 : generation = types.generation;
90 0 : return false;
91 : }
92 :
93 : /////////////////////////////////////////////////////////////////////
94 : // Types
95 : /////////////////////////////////////////////////////////////////////
96 :
97 : /* static */ inline TypeSet::ObjectKey*
98 857 : TypeSet::ObjectKey::get(JSObject* obj)
99 : {
100 857 : MOZ_ASSERT(obj);
101 857 : if (obj->isSingleton())
102 800 : return (ObjectKey*) (uintptr_t(obj) | 1);
103 57 : return (ObjectKey*) obj->group();
104 : }
105 :
106 : /* static */ inline TypeSet::ObjectKey*
107 64 : TypeSet::ObjectKey::get(ObjectGroup* group)
108 : {
109 64 : MOZ_ASSERT(group);
110 64 : if (group->singleton())
111 0 : return (ObjectKey*) (uintptr_t(group->singleton()) | 1);
112 64 : return (ObjectKey*) group;
113 : }
114 :
115 : inline ObjectGroup*
116 32040 : TypeSet::ObjectKey::groupNoBarrier()
117 : {
118 32040 : MOZ_ASSERT(isGroup());
119 32040 : return (ObjectGroup*) this;
120 : }
121 :
122 : inline JSObject*
123 22640 : TypeSet::ObjectKey::singletonNoBarrier()
124 : {
125 22640 : MOZ_ASSERT(isSingleton());
126 22640 : return (JSObject*) (uintptr_t(this) & ~1);
127 : }
128 :
129 : inline ObjectGroup*
130 18895 : TypeSet::ObjectKey::group()
131 : {
132 18895 : ObjectGroup* res = groupNoBarrier();
133 18895 : ObjectGroup::readBarrier(res);
134 18895 : return res;
135 : }
136 :
137 : inline JSObject*
138 9448 : TypeSet::ObjectKey::singleton()
139 : {
140 9448 : JSObject* res = singletonNoBarrier();
141 9448 : JSObject::readBarrier(res);
142 9448 : return res;
143 : }
144 :
145 : inline JSCompartment*
146 2117 : TypeSet::ObjectKey::maybeCompartment()
147 : {
148 2117 : if (isSingleton())
149 883 : return singleton()->compartment();
150 :
151 1234 : return group()->compartment();
152 : }
153 :
154 : /* static */ inline TypeSet::Type
155 104857 : TypeSet::ObjectType(JSObject* obj)
156 : {
157 104857 : if (obj->isSingleton())
158 65113 : return Type(uintptr_t(obj) | 1);
159 39744 : return Type(uintptr_t(obj->group()));
160 : }
161 :
162 : /* static */ inline TypeSet::Type
163 7 : TypeSet::ObjectType(ObjectGroup* group)
164 : {
165 7 : if (group->singleton())
166 0 : return Type(uintptr_t(group->singleton()) | 1);
167 7 : return Type(uintptr_t(group));
168 : }
169 :
170 : /* static */ inline TypeSet::Type
171 1397 : TypeSet::ObjectType(ObjectKey* obj)
172 : {
173 1397 : return Type(uintptr_t(obj));
174 : }
175 :
176 : inline TypeSet::Type
177 188545 : TypeSet::GetValueType(const Value& val)
178 : {
179 188545 : if (val.isDouble())
180 696 : return TypeSet::DoubleType();
181 187847 : if (val.isObject())
182 104365 : return TypeSet::ObjectType(&val.toObject());
183 83485 : return TypeSet::PrimitiveType(val.extractNonDoubleType());
184 : }
185 :
186 : inline bool
187 2010 : TypeSet::IsUntrackedValue(const Value& val)
188 : {
189 2011 : return val.isMagic() && (val.whyMagic() == JS_OPTIMIZED_OUT ||
190 2011 : val.whyMagic() == JS_UNINITIALIZED_LEXICAL);
191 : }
192 :
193 : inline TypeSet::Type
194 102 : TypeSet::GetMaybeUntrackedValueType(const Value& val)
195 : {
196 102 : return IsUntrackedValue(val) ? UnknownType() : GetValueType(val);
197 : }
198 :
199 : inline TypeFlags
200 104978 : PrimitiveTypeFlag(JSValueType type)
201 : {
202 104978 : switch (type) {
203 : case JSVAL_TYPE_UNDEFINED:
204 54045 : return TYPE_FLAG_UNDEFINED;
205 : case JSVAL_TYPE_NULL:
206 2653 : return TYPE_FLAG_NULL;
207 : case JSVAL_TYPE_BOOLEAN:
208 19817 : return TYPE_FLAG_BOOLEAN;
209 : case JSVAL_TYPE_INT32:
210 8311 : return TYPE_FLAG_INT32;
211 : case JSVAL_TYPE_DOUBLE:
212 1234 : return TYPE_FLAG_DOUBLE;
213 : case JSVAL_TYPE_STRING:
214 17760 : return TYPE_FLAG_STRING;
215 : case JSVAL_TYPE_SYMBOL:
216 304 : return TYPE_FLAG_SYMBOL;
217 : case JSVAL_TYPE_MAGIC:
218 854 : return TYPE_FLAG_LAZYARGS;
219 : default:
220 0 : MOZ_CRASH("Bad JSValueType");
221 : }
222 : }
223 :
224 : inline JSValueType
225 26 : TypeFlagPrimitive(TypeFlags flags)
226 : {
227 26 : switch (flags) {
228 : case TYPE_FLAG_UNDEFINED:
229 5 : return JSVAL_TYPE_UNDEFINED;
230 : case TYPE_FLAG_NULL:
231 2 : return JSVAL_TYPE_NULL;
232 : case TYPE_FLAG_BOOLEAN:
233 8 : return JSVAL_TYPE_BOOLEAN;
234 : case TYPE_FLAG_INT32:
235 2 : return JSVAL_TYPE_INT32;
236 : case TYPE_FLAG_DOUBLE:
237 2 : return JSVAL_TYPE_DOUBLE;
238 : case TYPE_FLAG_STRING:
239 3 : return JSVAL_TYPE_STRING;
240 : case TYPE_FLAG_SYMBOL:
241 2 : return JSVAL_TYPE_SYMBOL;
242 : case TYPE_FLAG_LAZYARGS:
243 2 : return JSVAL_TYPE_MAGIC;
244 : default:
245 0 : MOZ_CRASH("Bad TypeFlags");
246 : }
247 : }
248 :
249 : /*
250 : * Get the canonical representation of an id to use when doing inference. This
251 : * maintains the constraint that if two different jsids map to the same property
252 : * in JS (e.g. 3 and "3"), they have the same type representation.
253 : */
254 : inline jsid
255 441469 : IdToTypeId(jsid id)
256 : {
257 441469 : MOZ_ASSERT(!JSID_IS_EMPTY(id));
258 :
259 : // All properties which can be stored in an object's dense elements must
260 : // map to the aggregate property for index types.
261 441470 : return JSID_IS_INT(id) ? JSID_VOID : id;
262 : }
263 :
264 : const char * TypeIdStringImpl(jsid id);
265 :
266 : /* Convert an id for printing during debug. */
267 : static inline const char*
268 0 : TypeIdString(jsid id)
269 : {
270 : #ifdef DEBUG
271 0 : return TypeIdStringImpl(id);
272 : #else
273 : return "(missing)";
274 : #endif
275 : }
276 :
277 : /*
278 : * Structure for type inference entry point functions. All functions which can
279 : * change type information must use this, and functions which depend on
280 : * intermediate types (i.e. JITs) can use this to ensure that intermediate
281 : * information is not collected and does not change.
282 : *
283 : * Ensures that GC cannot occur. Does additional sanity checking that inference
284 : * is not reentrant and that recompilations occur properly.
285 : */
286 : struct AutoEnterAnalysis
287 : {
288 : // For use when initializing an UnboxedLayout. The UniquePtr's destructor
289 : // must run when GC is not suppressed.
290 : UniquePtr<UnboxedLayout> unboxedLayoutToCleanUp;
291 :
292 : // Prevent GC activity in the middle of analysis.
293 : gc::AutoSuppressGC suppressGC;
294 :
295 : // Allow clearing inference info on OOM during incremental sweeping.
296 : mozilla::Maybe<AutoClearTypeInferenceStateOnOOM> oom;
297 :
298 : // Pending recompilations to perform before execution of JIT code can resume.
299 : RecompileInfoVector pendingRecompiles;
300 :
301 : // Prevent us from calling the objectMetadataCallback.
302 : js::AutoSuppressAllocationMetadataBuilder suppressMetadata;
303 :
304 : FreeOp* freeOp;
305 : Zone* zone;
306 :
307 121137 : explicit AutoEnterAnalysis(JSContext* cx)
308 121137 : : suppressGC(cx), suppressMetadata(cx)
309 : {
310 121139 : init(cx->defaultFreeOp(), cx->zone());
311 121140 : }
312 :
313 0 : AutoEnterAnalysis(FreeOp* fop, Zone* zone)
314 0 : : suppressGC(TlsContext.get()),
315 0 : suppressMetadata(zone)
316 : {
317 0 : init(fop, zone);
318 0 : }
319 :
320 121140 : ~AutoEnterAnalysis()
321 121139 : {
322 121140 : if (this != zone->types.activeAnalysis)
323 1121 : return;
324 :
325 120015 : zone->types.activeAnalysis = nullptr;
326 :
327 120018 : if (!pendingRecompiles.empty())
328 0 : zone->types.processPendingRecompiles(freeOp, pendingRecompiles);
329 121138 : }
330 :
331 : private:
332 121138 : void init(FreeOp* fop, Zone* zone) {
333 : #ifdef JS_CRASH_DIAGNOSTICS
334 121138 : MOZ_RELEASE_ASSERT(CurrentThreadCanAccessZone(zone));
335 : #endif
336 121138 : this->freeOp = fop;
337 121138 : this->zone = zone;
338 :
339 121138 : if (!zone->types.activeAnalysis) {
340 120019 : MOZ_RELEASE_ASSERT(!zone->types.sweepingTypes);
341 120018 : zone->types.activeAnalysis = this;
342 : }
343 121140 : }
344 : };
345 :
346 : /////////////////////////////////////////////////////////////////////
347 : // Interface functions
348 : /////////////////////////////////////////////////////////////////////
349 :
350 : void MarkIteratorUnknownSlow(JSContext* cx);
351 :
352 : void TypeMonitorCallSlow(JSContext* cx, JSObject* callee, const CallArgs& args,
353 : bool constructing);
354 :
355 : /*
356 : * Monitor a javascript call, either on entry to the interpreter or made
357 : * from within the interpreter.
358 : */
359 : inline void
360 12175 : TypeMonitorCall(JSContext* cx, const js::CallArgs& args, bool constructing)
361 : {
362 12175 : if (args.callee().is<JSFunction>()) {
363 12175 : JSFunction* fun = &args.callee().as<JSFunction>();
364 12175 : if (fun->isInterpreted() && fun->nonLazyScript()->types())
365 1053 : TypeMonitorCallSlow(cx, &args.callee(), args, constructing);
366 : }
367 12175 : }
368 :
369 : MOZ_ALWAYS_INLINE bool
370 191830 : TrackPropertyTypes(JSObject* obj, jsid id)
371 : {
372 191830 : if (obj->hasLazyGroup() || obj->group()->unknownProperties())
373 86616 : return false;
374 :
375 105217 : if (obj->isSingleton() && !obj->group()->maybeGetProperty(id))
376 29374 : return false;
377 :
378 75843 : return true;
379 : }
380 :
381 : void
382 : EnsureTrackPropertyTypes(JSContext* cx, JSObject* obj, jsid id);
383 :
384 : inline bool
385 150 : CanHaveEmptyPropertyTypesForOwnProperty(JSObject* obj)
386 : {
387 : // Per the comment on TypeSet::propertySet, property type sets for global
388 : // objects may be empty for 'own' properties if the global property still
389 : // has its initial undefined value.
390 150 : return obj->is<GlobalObject>();
391 : }
392 :
393 : inline bool
394 446 : PropertyHasBeenMarkedNonConstant(JSObject* obj, jsid id)
395 : {
396 : // Non-constant properties are only relevant for singleton objects.
397 446 : if (!obj->isSingleton())
398 401 : return true;
399 :
400 : // EnsureTrackPropertyTypes must have been called on this object.
401 45 : if (obj->group()->unknownProperties())
402 0 : return true;
403 45 : HeapTypeSet* types = obj->group()->maybeGetProperty(IdToTypeId(id));
404 45 : return types->nonConstantProperty();
405 : }
406 :
407 : MOZ_ALWAYS_INLINE bool
408 32205 : HasTrackedPropertyType(JSObject* obj, jsid id, TypeSet::Type type)
409 : {
410 32205 : MOZ_ASSERT(id == IdToTypeId(id));
411 32205 : MOZ_ASSERT(TrackPropertyTypes(obj, id));
412 :
413 32204 : if (HeapTypeSet* types = obj->group()->maybeGetProperty(id)) {
414 10374 : if (!types->hasType(type))
415 1158 : return false;
416 : // Non-constant properties are only relevant for singleton objects.
417 9216 : if (obj->isSingleton() && !types->nonConstantProperty())
418 22 : return false;
419 9194 : return true;
420 : }
421 :
422 21831 : return false;
423 : }
424 :
425 : MOZ_ALWAYS_INLINE bool
426 0 : HasTypePropertyId(JSObject* obj, jsid id, TypeSet::Type type)
427 : {
428 0 : id = IdToTypeId(id);
429 0 : if (!TrackPropertyTypes(obj, id))
430 0 : return true;
431 :
432 0 : return HasTrackedPropertyType(obj, id, type);
433 : }
434 :
435 : MOZ_ALWAYS_INLINE bool
436 0 : HasTypePropertyId(JSObject* obj, jsid id, const Value& value)
437 : {
438 0 : return HasTypePropertyId(obj, id, TypeSet::GetValueType(value));
439 : }
440 :
441 : void AddTypePropertyId(JSContext* cx, ObjectGroup* group, JSObject* obj, jsid id, TypeSet::Type type);
442 : void AddTypePropertyId(JSContext* cx, ObjectGroup* group, JSObject* obj, jsid id, const Value& value);
443 :
444 : /* Add a possible type for a property of obj. */
445 : MOZ_ALWAYS_INLINE void
446 119423 : AddTypePropertyId(JSContext* cx, JSObject* obj, jsid id, TypeSet::Type type)
447 : {
448 119423 : id = IdToTypeId(id);
449 119423 : if (TrackPropertyTypes(obj, id) && !HasTrackedPropertyType(obj, id, type))
450 23011 : AddTypePropertyId(cx, obj->group(), obj, id, type);
451 119424 : }
452 :
453 : MOZ_ALWAYS_INLINE void
454 115577 : AddTypePropertyId(JSContext* cx, JSObject* obj, jsid id, const Value& value)
455 : {
456 115577 : return AddTypePropertyId(cx, obj, id, TypeSet::GetValueType(value));
457 : }
458 :
459 : inline void
460 286 : MarkObjectGroupFlags(JSContext* cx, JSObject* obj, ObjectGroupFlags flags)
461 : {
462 286 : if (!obj->hasLazyGroup() && !obj->group()->hasAllFlags(flags))
463 100 : obj->group()->setFlags(cx, flags);
464 286 : }
465 :
466 : inline void
467 10072 : MarkObjectGroupUnknownProperties(JSContext* cx, ObjectGroup* obj)
468 : {
469 10072 : if (!obj->unknownProperties())
470 128 : obj->markUnknown(cx);
471 10072 : }
472 :
473 : inline void
474 17211 : MarkTypePropertyNonData(JSContext* cx, JSObject* obj, jsid id)
475 : {
476 17211 : id = IdToTypeId(id);
477 17211 : if (TrackPropertyTypes(obj, id))
478 2229 : obj->group()->markPropertyNonData(cx, obj, id);
479 17211 : }
480 :
481 : inline void
482 17561 : MarkTypePropertyNonWritable(JSContext* cx, JSObject* obj, jsid id)
483 : {
484 17561 : id = IdToTypeId(id);
485 17561 : if (TrackPropertyTypes(obj, id))
486 3776 : obj->group()->markPropertyNonWritable(cx, obj, id);
487 17561 : }
488 :
489 : /* Mark a state change on a particular object. */
490 : inline void
491 0 : MarkObjectStateChange(JSContext* cx, JSObject* obj)
492 : {
493 0 : if (!obj->hasLazyGroup() && !obj->group()->unknownProperties())
494 0 : obj->group()->markStateChange(cx);
495 0 : }
496 :
497 : /* Interface helpers for JSScript*. */
498 : extern void TypeMonitorResult(JSContext* cx, JSScript* script, jsbytecode* pc, TypeSet::Type type);
499 : extern void TypeMonitorResult(JSContext* cx, JSScript* script, jsbytecode* pc, StackTypeSet* types,
500 : TypeSet::Type type);
501 : extern void TypeMonitorResult(JSContext* cx, JSScript* script, jsbytecode* pc, const Value& rval);
502 :
503 : /////////////////////////////////////////////////////////////////////
504 : // Script interface functions
505 : /////////////////////////////////////////////////////////////////////
506 :
507 : /* static */ inline unsigned
508 896 : TypeScript::NumTypeSets(JSScript* script)
509 : {
510 896 : size_t num = script->nTypeSets() + 1 /* this */;
511 896 : if (JSFunction* fun = script->functionNonDelazifying())
512 891 : num += fun->nargs();
513 896 : return num;
514 : }
515 :
516 : /* static */ inline StackTypeSet*
517 3979 : TypeScript::ThisTypes(JSScript* script)
518 : {
519 3979 : TypeScript* types = script->types();
520 3979 : return types ? types->typeArray() + script->nTypeSets() : nullptr;
521 : }
522 :
523 : /*
524 : * Note: for non-escaping arguments, argTypes reflect only the initial type of
525 : * the variable (e.g. passed values for argTypes, or undefined for localTypes)
526 : * and not types from subsequent assignments.
527 : */
528 :
529 : /* static */ inline StackTypeSet*
530 5016 : TypeScript::ArgTypes(JSScript* script, unsigned i)
531 : {
532 5016 : MOZ_ASSERT(i < script->functionNonDelazifying()->nargs());
533 5016 : TypeScript* types = script->types();
534 5016 : return types ? types->typeArray() + script->nTypeSets() + 1 + i : nullptr;
535 : }
536 :
537 : template <typename TYPESET>
538 : /* static */ inline TYPESET*
539 27146 : TypeScript::BytecodeTypes(JSScript* script, jsbytecode* pc, uint32_t* bytecodeMap,
540 : uint32_t* hint, TYPESET* typeArray)
541 : {
542 27146 : MOZ_ASSERT(CodeSpec[*pc].format & JOF_TYPESET);
543 27146 : uint32_t offset = script->pcToOffset(pc);
544 :
545 : // See if this pc is the next typeset opcode after the last one looked up.
546 27146 : if ((*hint + 1) < script->nTypeSets() && bytecodeMap[*hint + 1] == offset) {
547 10583 : (*hint)++;
548 10583 : return typeArray + *hint;
549 : }
550 :
551 : // See if this pc is the same as the last one looked up.
552 16563 : if (bytecodeMap[*hint] == offset)
553 11148 : return typeArray + *hint;
554 :
555 : // Fall back to a binary search. We'll either find the exact offset, or
556 : // there are more JOF_TYPESET opcodes than nTypeSets in the script (as can
557 : // happen if the script is very long) and we'll use the last location.
558 : size_t loc;
559 : #ifdef DEBUG
560 : bool found =
561 : #endif
562 5415 : mozilla::BinarySearch(bytecodeMap, 0, script->nTypeSets() - 1, offset, &loc);
563 :
564 5415 : MOZ_ASSERT_IF(found, bytecodeMap[loc] == offset);
565 5415 : *hint = mozilla::AssertedCast<uint32_t>(loc);
566 5415 : return typeArray + *hint;
567 : }
568 :
569 : /* static */ inline StackTypeSet*
570 21232 : TypeScript::BytecodeTypes(JSScript* script, jsbytecode* pc)
571 : {
572 21232 : MOZ_ASSERT(CurrentThreadCanAccessZone(script->zone()));
573 21232 : TypeScript* types = script->types();
574 21232 : if (!types)
575 0 : return nullptr;
576 21232 : uint32_t* hint = script->baselineScript()->bytecodeTypeMap() + script->nTypeSets();
577 21232 : return BytecodeTypes(script, pc, script->baselineScript()->bytecodeTypeMap(),
578 21232 : hint, types->typeArray());
579 : }
580 :
581 : /* static */ inline void
582 108765 : TypeScript::Monitor(JSContext* cx, JSScript* script, jsbytecode* pc, const js::Value& rval)
583 : {
584 108765 : TypeMonitorResult(cx, script, pc, rval);
585 108765 : }
586 :
587 : /* static */ inline void
588 0 : TypeScript::Monitor(JSContext* cx, JSScript* script, jsbytecode* pc, TypeSet::Type type)
589 : {
590 0 : TypeMonitorResult(cx, script, pc, type);
591 0 : }
592 :
593 : /* static */ inline void
594 0 : TypeScript::Monitor(JSContext* cx, const js::Value& rval)
595 : {
596 : jsbytecode* pc;
597 0 : RootedScript script(cx, cx->currentScript(&pc));
598 0 : Monitor(cx, script, pc, rval);
599 0 : }
600 :
601 : /* static */ inline void
602 13652 : TypeScript::Monitor(JSContext* cx, JSScript* script, jsbytecode* pc, StackTypeSet* types,
603 : const js::Value& rval)
604 : {
605 13652 : TypeSet::Type type = TypeSet::GetValueType(rval);
606 13652 : if (!types->hasType(type))
607 6400 : TypeMonitorResult(cx, script, pc, types, type);
608 13652 : }
609 :
610 : /* static */ inline void
611 1850 : TypeScript::MonitorAssign(JSContext* cx, HandleObject obj, jsid id)
612 : {
613 1850 : if (!obj->isSingleton()) {
614 : /*
615 : * Mark as unknown any object which has had dynamic assignments to
616 : * non-integer properties at SETELEM opcodes. This avoids making large
617 : * numbers of type properties for hashmap-style objects. We don't need
618 : * to do this for objects with singleton type, because type properties
619 : * are only constructed for them when analyzed scripts depend on those
620 : * specific properties.
621 : */
622 : uint32_t i;
623 1429 : if (IdIsIndex(id, &i))
624 1717 : return;
625 :
626 : // But if we don't have too many properties yet, don't do anything. The
627 : // idea here is that normal object initialization should not trigger
628 : // deoptimization in most cases, while actual usage as a hashmap should.
629 1141 : ObjectGroup* group = obj->group();
630 1141 : if (group->basePropertyCount() < 128)
631 1141 : return;
632 0 : MarkObjectGroupUnknownProperties(cx, group);
633 : }
634 : }
635 :
636 : /* static */ inline void
637 2249 : TypeScript::SetThis(JSContext* cx, JSScript* script, TypeSet::Type type)
638 : {
639 2249 : assertSameCompartment(cx, script, type);
640 :
641 2249 : StackTypeSet* types = ThisTypes(script);
642 2249 : if (!types)
643 402 : return;
644 :
645 1847 : if (!types->hasType(type)) {
646 1524 : AutoEnterAnalysis enter(cx);
647 :
648 762 : InferSpew(ISpewOps, "externalType: setThis %p: %s",
649 : script, TypeSet::TypeString(type));
650 762 : types->addType(cx, type);
651 : }
652 : }
653 :
654 : /* static */ inline void
655 1755 : TypeScript::SetThis(JSContext* cx, JSScript* script, const js::Value& value)
656 : {
657 1755 : SetThis(cx, script, TypeSet::GetValueType(value));
658 1755 : }
659 :
660 : /* static */ inline void
661 2741 : TypeScript::SetArgument(JSContext* cx, JSScript* script, unsigned arg, TypeSet::Type type)
662 : {
663 2741 : assertSameCompartment(cx, script, type);
664 :
665 2741 : StackTypeSet* types = ArgTypes(script, arg);
666 2741 : if (!types)
667 0 : return;
668 :
669 2741 : if (!types->hasType(type)) {
670 2370 : AutoEnterAnalysis enter(cx);
671 :
672 1185 : InferSpew(ISpewOps, "externalType: setArg %p %u: %s",
673 : script, arg, TypeSet::TypeString(type));
674 1185 : types->addType(cx, type);
675 : }
676 : }
677 :
678 : /* static */ inline void
679 2741 : TypeScript::SetArgument(JSContext* cx, JSScript* script, unsigned arg, const js::Value& value)
680 : {
681 2741 : SetArgument(cx, script, arg, TypeSet::GetValueType(value));
682 2741 : }
683 :
684 : /////////////////////////////////////////////////////////////////////
685 : // TypeHashSet
686 : /////////////////////////////////////////////////////////////////////
687 :
688 : // Hashing code shared by objects in TypeSets and properties in ObjectGroups.
689 : struct TypeHashSet
690 : {
691 : // The sets of objects in a type set grow monotonically, are usually empty,
692 : // almost always small, and sometimes big. For empty or singleton sets, the
693 : // the pointer refers directly to the value. For sets fitting into
694 : // SET_ARRAY_SIZE, an array of this length is used to store the elements.
695 : // For larger sets, a hash table filled to 25%-50% of capacity is used,
696 : // with collisions resolved by linear probing.
697 : static const unsigned SET_ARRAY_SIZE = 8;
698 : static const unsigned SET_CAPACITY_OVERFLOW = 1u << 30;
699 :
700 : // Get the capacity of a set with the given element count.
701 : static inline unsigned
702 32863 : Capacity(unsigned count)
703 : {
704 32863 : MOZ_ASSERT(count >= 2);
705 32863 : MOZ_ASSERT(count < SET_CAPACITY_OVERFLOW);
706 :
707 32863 : if (count <= SET_ARRAY_SIZE)
708 771 : return SET_ARRAY_SIZE;
709 :
710 32092 : return 1u << (mozilla::FloorLog2(count) + 2);
711 : }
712 :
713 : // Compute the FNV hash for the low 32 bits of v.
714 : template <class T, class KEY>
715 : static inline uint32_t
716 38845 : HashKey(T v)
717 : {
718 38845 : uint32_t nv = KEY::keyBits(v);
719 :
720 38845 : uint32_t hash = 84696351 ^ (nv & 0xff);
721 38845 : hash = (hash * 16777619) ^ ((nv >> 8) & 0xff);
722 38845 : hash = (hash * 16777619) ^ ((nv >> 16) & 0xff);
723 38845 : return (hash * 16777619) ^ ((nv >> 24) & 0xff);
724 : }
725 :
726 : // Insert space for an element into the specified set and grow its capacity
727 : // if needed. returned value is an existing or new entry (nullptr if new).
728 : template <class T, class U, class KEY>
729 : static U**
730 5119 : InsertTry(LifoAlloc& alloc, U**& values, unsigned& count, T key)
731 : {
732 5119 : unsigned capacity = Capacity(count);
733 5119 : unsigned insertpos = HashKey<T,KEY>(key) & (capacity - 1);
734 :
735 5119 : MOZ_RELEASE_ASSERT(uintptr_t(values[-1]) == capacity);
736 :
737 : // Whether we are converting from a fixed array to hashtable.
738 5119 : bool converting = (count == SET_ARRAY_SIZE);
739 :
740 5119 : if (!converting) {
741 15771 : while (values[insertpos] != nullptr) {
742 5697 : if (KEY::getKey(values[insertpos]) == key)
743 0 : return &values[insertpos];
744 5697 : insertpos = (insertpos + 1) & (capacity - 1);
745 : }
746 : }
747 :
748 5119 : if (count >= SET_CAPACITY_OVERFLOW)
749 0 : return nullptr;
750 :
751 5119 : count++;
752 5119 : unsigned newCapacity = Capacity(count);
753 :
754 5119 : if (newCapacity == capacity) {
755 4138 : MOZ_ASSERT(!converting);
756 4138 : return &values[insertpos];
757 : }
758 :
759 : // Allocate an extra word right before the array storing the capacity,
760 : // for sanity checks.
761 981 : U** newValues = alloc.newArray<U*>(newCapacity + 1);
762 981 : if (!newValues)
763 0 : return nullptr;
764 981 : mozilla::PodZero(newValues, newCapacity + 1);
765 :
766 981 : newValues[0] = (U*)uintptr_t(newCapacity);
767 981 : newValues++;
768 :
769 17541 : for (unsigned i = 0; i < capacity; i++) {
770 16560 : if (values[i]) {
771 11009 : unsigned pos = HashKey<T,KEY>(KEY::getKey(values[i])) & (newCapacity - 1);
772 19177 : while (newValues[pos] != nullptr)
773 4084 : pos = (pos + 1) & (newCapacity - 1);
774 11009 : newValues[pos] = values[i];
775 : }
776 : }
777 :
778 981 : values = newValues;
779 :
780 981 : insertpos = HashKey<T,KEY>(key) & (newCapacity - 1);
781 3125 : while (values[insertpos] != nullptr)
782 1072 : insertpos = (insertpos + 1) & (newCapacity - 1);
783 981 : return &values[insertpos];
784 : }
785 :
786 : // Insert an element into the specified set if it is not already there,
787 : // returning an entry which is nullptr if the element was not there.
788 : template <class T, class U, class KEY>
789 : static inline U**
790 37872 : Insert(LifoAlloc& alloc, U**& values, unsigned& count, T key)
791 : {
792 37872 : if (count == 0) {
793 18504 : MOZ_ASSERT(values == nullptr);
794 18504 : count++;
795 18504 : return (U**) &values;
796 : }
797 :
798 19368 : if (count == 1) {
799 4683 : U* oldData = (U*) values;
800 4683 : if (KEY::getKey(oldData) == key)
801 0 : return (U**) &values;
802 :
803 : // Allocate an extra word right before the array storing the
804 : // capacity, for sanity checks.
805 4683 : values = alloc.newArray<U*>(SET_ARRAY_SIZE + 1);
806 4683 : if (!values) {
807 0 : values = (U**) oldData;
808 0 : return nullptr;
809 : }
810 4683 : mozilla::PodZero(values, SET_ARRAY_SIZE + 1);
811 :
812 4683 : values[0] = (U*)uintptr_t(SET_ARRAY_SIZE);
813 4683 : values++;
814 :
815 4683 : count++;
816 :
817 4683 : values[0] = oldData;
818 4683 : return &values[1];
819 : }
820 :
821 14685 : if (count <= SET_ARRAY_SIZE) {
822 10308 : MOZ_RELEASE_ASSERT(uintptr_t(values[-1]) == SET_ARRAY_SIZE);
823 :
824 52559 : for (unsigned i = 0; i < count; i++) {
825 42263 : if (KEY::getKey(values[i]) == key)
826 12 : return &values[i];
827 : }
828 :
829 10296 : if (count < SET_ARRAY_SIZE) {
830 9554 : count++;
831 9554 : return &values[count - 1];
832 : }
833 : }
834 :
835 5119 : return InsertTry<T,U,KEY>(alloc, values, count, key);
836 : }
837 :
838 : // Lookup an entry in a hash set, return nullptr if it does not exist.
839 : template <class T, class U, class KEY>
840 : static MOZ_ALWAYS_INLINE U*
841 174591 : Lookup(U** values, unsigned count, T key)
842 : {
843 174591 : if (count == 0)
844 64809 : return nullptr;
845 :
846 109782 : if (count == 1)
847 37517 : return (KEY::getKey((U*) values) == key) ? (U*) values : nullptr;
848 :
849 72265 : if (count <= SET_ARRAY_SIZE) {
850 50579 : MOZ_RELEASE_ASSERT(uintptr_t(values[-1]) == SET_ARRAY_SIZE);
851 179317 : for (unsigned i = 0; i < count; i++) {
852 157848 : if (KEY::getKey(values[i]) == key)
853 29110 : return values[i];
854 : }
855 21469 : return nullptr;
856 : }
857 :
858 21686 : unsigned capacity = Capacity(count);
859 21686 : unsigned pos = HashKey<T,KEY>(key) & (capacity - 1);
860 :
861 21686 : MOZ_RELEASE_ASSERT(uintptr_t(values[-1]) == capacity);
862 :
863 59210 : while (values[pos] != nullptr) {
864 32136 : if (KEY::getKey(values[pos]) == key)
865 13374 : return values[pos];
866 18762 : pos = (pos + 1) & (capacity - 1);
867 : }
868 :
869 8312 : return nullptr;
870 : }
871 : };
872 :
873 : /////////////////////////////////////////////////////////////////////
874 : // TypeSet
875 : /////////////////////////////////////////////////////////////////////
876 :
877 : inline TypeSet::ObjectKey*
878 91291 : TypeSet::Type::objectKey() const
879 : {
880 91291 : MOZ_ASSERT(isObject());
881 91291 : return (ObjectKey*) data;
882 : }
883 :
884 : inline JSObject*
885 0 : TypeSet::Type::singleton() const
886 : {
887 0 : return objectKey()->singleton();
888 : }
889 :
890 : inline ObjectGroup*
891 7626 : TypeSet::Type::group() const
892 : {
893 7626 : return objectKey()->group();
894 : }
895 :
896 : inline JSObject*
897 13115 : TypeSet::Type::singletonNoBarrier() const
898 : {
899 13115 : return objectKey()->singletonNoBarrier();
900 : }
901 :
902 : inline ObjectGroup*
903 12788 : TypeSet::Type::groupNoBarrier() const
904 : {
905 12788 : return objectKey()->groupNoBarrier();
906 : }
907 :
908 : inline void
909 0 : TypeSet::Type::trace(JSTracer* trc)
910 : {
911 0 : if (isSingletonUnchecked()) {
912 0 : JSObject* obj = singletonNoBarrier();
913 0 : TraceManuallyBarrieredEdge(trc, &obj, "TypeSet::Object");
914 0 : *this = TypeSet::ObjectType(obj);
915 0 : } else if (isGroupUnchecked()) {
916 0 : ObjectGroup* group = groupNoBarrier();
917 0 : TraceManuallyBarrieredEdge(trc, &group, "TypeSet::Group");
918 0 : *this = TypeSet::ObjectType(group);
919 : }
920 0 : }
921 :
922 : inline JSCompartment*
923 53493 : TypeSet::Type::maybeCompartment()
924 : {
925 53493 : if (isSingletonUnchecked())
926 7959 : return singletonNoBarrier()->compartment();
927 :
928 45534 : if (isGroupUnchecked())
929 12788 : return groupNoBarrier()->compartment();
930 :
931 32746 : return nullptr;
932 : }
933 :
934 : MOZ_ALWAYS_INLINE bool
935 125495 : TypeSet::hasType(Type type) const
936 : {
937 125495 : if (unknown())
938 1601 : return true;
939 :
940 123894 : if (type.isUnknown()) {
941 305 : return false;
942 123589 : } else if (type.isPrimitive()) {
943 75912 : return !!(flags & PrimitiveTypeFlag(type.primitive()));
944 47678 : } else if (type.isAnyObject()) {
945 482 : return !!(flags & TYPE_FLAG_ANYOBJECT);
946 : } else {
947 91313 : return !!(flags & TYPE_FLAG_ANYOBJECT) ||
948 : TypeHashSet::Lookup<ObjectKey*, ObjectKey, ObjectKey>
949 91313 : (objectSet, baseObjectCount(), type.objectKey()) != nullptr;
950 : }
951 : }
952 :
953 : inline void
954 16910 : TypeSet::setBaseObjectCount(uint32_t count)
955 : {
956 16910 : MOZ_ASSERT(count <= TYPE_FLAG_DOMOBJECT_COUNT_LIMIT);
957 33820 : flags = (flags & ~TYPE_FLAG_OBJECT_COUNT_MASK)
958 16910 : | (count << TYPE_FLAG_OBJECT_COUNT_SHIFT);
959 16910 : }
960 :
961 : inline void
962 29144 : HeapTypeSet::newPropertyState(JSContext* cx)
963 : {
964 29144 : checkMagic();
965 :
966 : /* Propagate the change to all constraints. */
967 29144 : if (!cx->helperThread()) {
968 25182 : TypeConstraint* constraint = constraintList();
969 25182 : while (constraint) {
970 0 : constraint->newPropertyState(cx, this);
971 0 : constraint = constraint->next();
972 : }
973 : } else {
974 3962 : MOZ_ASSERT(!constraintList());
975 : }
976 29144 : }
977 :
978 : inline void
979 2391 : HeapTypeSet::setNonDataProperty(JSContext* cx)
980 : {
981 2391 : checkMagic();
982 :
983 2391 : if (flags & TYPE_FLAG_NON_DATA_PROPERTY)
984 255 : return;
985 :
986 2136 : flags |= TYPE_FLAG_NON_DATA_PROPERTY;
987 2136 : newPropertyState(cx);
988 : }
989 :
990 : inline void
991 3927 : HeapTypeSet::setNonWritableProperty(JSContext* cx)
992 : {
993 3927 : checkMagic();
994 :
995 3927 : if (flags & TYPE_FLAG_NON_WRITABLE_PROPERTY)
996 577 : return;
997 :
998 3350 : flags |= TYPE_FLAG_NON_WRITABLE_PROPERTY;
999 3350 : newPropertyState(cx);
1000 : }
1001 :
1002 : inline void
1003 23658 : HeapTypeSet::setNonConstantProperty(JSContext* cx)
1004 : {
1005 23658 : checkMagic();
1006 :
1007 23658 : if (flags & TYPE_FLAG_NON_CONSTANT_PROPERTY)
1008 0 : return;
1009 :
1010 23658 : flags |= TYPE_FLAG_NON_CONSTANT_PROPERTY;
1011 23658 : newPropertyState(cx);
1012 : }
1013 :
1014 : inline unsigned
1015 85351 : TypeSet::getObjectCount() const
1016 : {
1017 85351 : MOZ_ASSERT(!unknownObject());
1018 85351 : uint32_t count = baseObjectCount();
1019 85351 : if (count > TypeHashSet::SET_ARRAY_SIZE)
1020 0 : return TypeHashSet::Capacity(count);
1021 85351 : return count;
1022 : }
1023 :
1024 : inline TypeSet::ObjectKey*
1025 14123 : TypeSet::getObject(unsigned i) const
1026 : {
1027 14123 : MOZ_ASSERT(i < getObjectCount());
1028 14123 : if (baseObjectCount() == 1) {
1029 10685 : MOZ_ASSERT(i == 0);
1030 10685 : return (ObjectKey*) objectSet;
1031 : }
1032 3438 : return objectSet[i];
1033 : }
1034 :
1035 : inline JSObject*
1036 698 : TypeSet::getSingleton(unsigned i) const
1037 : {
1038 698 : ObjectKey* key = getObject(i);
1039 698 : return (key && key->isSingleton()) ? key->singleton() : nullptr;
1040 : }
1041 :
1042 : inline ObjectGroup*
1043 239 : TypeSet::getGroup(unsigned i) const
1044 : {
1045 239 : ObjectKey* key = getObject(i);
1046 239 : return (key && key->isGroup()) ? key->group() : nullptr;
1047 : }
1048 :
1049 : inline JSObject*
1050 160 : TypeSet::getSingletonNoBarrier(unsigned i) const
1051 : {
1052 160 : ObjectKey* key = getObject(i);
1053 160 : return (key && key->isSingleton()) ? key->singletonNoBarrier() : nullptr;
1054 : }
1055 :
1056 : inline ObjectGroup*
1057 321 : TypeSet::getGroupNoBarrier(unsigned i) const
1058 : {
1059 321 : ObjectKey* key = getObject(i);
1060 321 : return (key && key->isGroup()) ? key->groupNoBarrier() : nullptr;
1061 : }
1062 :
1063 : inline const Class*
1064 169 : TypeSet::getObjectClass(unsigned i) const
1065 : {
1066 169 : if (JSObject* object = getSingleton(i))
1067 44 : return object->getClass();
1068 125 : if (ObjectGroup* group = getGroup(i))
1069 125 : return group->clasp();
1070 0 : return nullptr;
1071 : }
1072 :
1073 : /////////////////////////////////////////////////////////////////////
1074 : // ObjectGroup
1075 : /////////////////////////////////////////////////////////////////////
1076 :
1077 : inline uint32_t
1078 159381 : ObjectGroup::basePropertyCount()
1079 : {
1080 159381 : return (flags() & OBJECT_FLAG_PROPERTY_COUNT_MASK) >> OBJECT_FLAG_PROPERTY_COUNT_SHIFT;
1081 : }
1082 :
1083 : inline void
1084 24801 : ObjectGroup::setBasePropertyCount(uint32_t count)
1085 : {
1086 : // Note: Callers must ensure they are performing threadsafe operations.
1087 24801 : MOZ_ASSERT(count <= OBJECT_FLAG_PROPERTY_COUNT_LIMIT);
1088 49602 : flags_ = (flags() & ~OBJECT_FLAG_PROPERTY_COUNT_MASK)
1089 24801 : | (count << OBJECT_FLAG_PROPERTY_COUNT_SHIFT);
1090 24801 : }
1091 :
1092 : inline HeapTypeSet*
1093 46919 : ObjectGroup::getProperty(JSContext* cx, JSObject* obj, jsid id)
1094 : {
1095 46919 : MOZ_ASSERT(JSID_IS_VOID(id) || JSID_IS_EMPTY(id) || JSID_IS_STRING(id) || JSID_IS_SYMBOL(id));
1096 46919 : MOZ_ASSERT_IF(!JSID_IS_EMPTY(id), id == IdToTypeId(id));
1097 46919 : MOZ_ASSERT(!unknownProperties());
1098 46919 : MOZ_ASSERT_IF(obj, obj->group() == this);
1099 46919 : MOZ_ASSERT_IF(singleton(), obj);
1100 :
1101 46918 : if (HeapTypeSet* types = maybeGetProperty(id))
1102 22117 : return types;
1103 :
1104 24801 : Property* base = cx->typeLifoAlloc().new_<Property>(id);
1105 24801 : if (!base) {
1106 0 : markUnknown(cx);
1107 0 : return nullptr;
1108 : }
1109 :
1110 24801 : uint32_t propertyCount = basePropertyCount();
1111 : Property** pprop = TypeHashSet::Insert<jsid, Property, Property>
1112 24801 : (cx->typeLifoAlloc(), propertySet, propertyCount, id);
1113 24801 : if (!pprop) {
1114 0 : markUnknown(cx);
1115 0 : return nullptr;
1116 : }
1117 :
1118 24801 : MOZ_ASSERT(!*pprop);
1119 :
1120 24801 : setBasePropertyCount(propertyCount);
1121 24801 : *pprop = base;
1122 :
1123 24801 : updateNewPropertyTypes(cx, obj, id, &base->types);
1124 :
1125 24801 : if (propertyCount == OBJECT_FLAG_PROPERTY_COUNT_LIMIT) {
1126 : // We hit the maximum number of properties the object can have, mark
1127 : // the object unknown so that new properties will not be added in the
1128 : // future.
1129 0 : markUnknown(cx);
1130 : }
1131 :
1132 24801 : base->types.checkMagic();
1133 24801 : return &base->types;
1134 : }
1135 :
1136 : MOZ_ALWAYS_INLINE HeapTypeSet*
1137 130469 : ObjectGroup::maybeGetProperty(jsid id)
1138 : {
1139 130469 : MOZ_ASSERT(JSID_IS_VOID(id) || JSID_IS_EMPTY(id) || JSID_IS_STRING(id) || JSID_IS_SYMBOL(id));
1140 130469 : MOZ_ASSERT_IF(!JSID_IS_EMPTY(id), id == IdToTypeId(id));
1141 130469 : MOZ_ASSERT(!unknownProperties());
1142 :
1143 : Property* prop = TypeHashSet::Lookup<jsid, Property, Property>
1144 130475 : (propertySet, basePropertyCount(), id);
1145 :
1146 130475 : if (!prop)
1147 76657 : return nullptr;
1148 :
1149 53818 : prop->types.checkMagic();
1150 53818 : return &prop->types;
1151 : }
1152 :
1153 : inline unsigned
1154 1736 : ObjectGroup::getPropertyCount()
1155 : {
1156 1736 : uint32_t count = basePropertyCount();
1157 1736 : if (count > TypeHashSet::SET_ARRAY_SIZE)
1158 880 : return TypeHashSet::Capacity(count);
1159 856 : return count;
1160 : }
1161 :
1162 : inline ObjectGroup::Property*
1163 1143 : ObjectGroup::getProperty(unsigned i)
1164 : {
1165 1143 : MOZ_ASSERT(i < getPropertyCount());
1166 : Property* result;
1167 1143 : if (basePropertyCount() == 1) {
1168 31 : MOZ_ASSERT(i == 0);
1169 31 : result = (Property*) propertySet;
1170 : } else {
1171 1112 : result = propertySet[i];
1172 : }
1173 1143 : if (result)
1174 580 : result->types.checkMagic();
1175 1143 : return result;
1176 : }
1177 :
1178 : } // namespace js
1179 :
1180 : inline js::TypeScript*
1181 43879 : JSScript::types()
1182 : {
1183 43879 : maybeSweepTypes(nullptr);
1184 43879 : return types_;
1185 : }
1186 :
1187 : inline bool
1188 787 : JSScript::ensureHasTypes(JSContext* cx)
1189 : {
1190 787 : return types() || makeTypes(cx);
1191 : }
1192 :
1193 : #endif /* vm_TypeInference_inl_h */
|