1
//* -*- Mode: c++; c-basic-offset: 4; tab-width: 40; indent-tabs-mode: nil -*- */
2
/* vim: set ts=40 sw=4 et 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/. */
7
/* Definitions related to javascript type inference. */
12
#include "mozilla/Attributes.h"
15
#include "jsfriendapi.h"
18
#include "ds/LifoAlloc.h"
19
#include "gc/Barrier.h"
21
#include "js/HashTable.h"
22
#include "js/Vector.h"
25
struct TypeInferenceSizes;
38
/* Type set entry for either a JSObject with singleton type or a non-singleton TypeObject. */
39
struct TypeObjectKey {
40
static intptr_t keyBits(TypeObjectKey *obj) { return (intptr_t) obj; }
41
static TypeObjectKey *getKey(TypeObjectKey *obj) { return obj; }
45
* Information about a single concrete type. We pack this into a single word,
46
* where small values are particular primitive or other singleton types, and
47
* larger values are either specific JS objects or type objects.
52
Type(uintptr_t data) : data(data) {}
56
uintptr_t raw() const { return data; }
58
bool isPrimitive() const {
59
return data < JSVAL_TYPE_OBJECT;
62
bool isPrimitive(JSValueType type) const {
63
JS_ASSERT(type < JSVAL_TYPE_OBJECT);
64
return (uintptr_t) type == data;
67
JSValueType primitive() const {
68
JS_ASSERT(isPrimitive());
69
return (JSValueType) data;
72
bool isAnyObject() const {
73
return data == JSVAL_TYPE_OBJECT;
76
bool isUnknown() const {
77
return data == JSVAL_TYPE_UNKNOWN;
80
/* Accessors for types that are either JSObject or TypeObject. */
82
bool isObject() const {
83
JS_ASSERT(!isAnyObject() && !isUnknown());
84
return data > JSVAL_TYPE_UNKNOWN;
87
inline TypeObjectKey *objectKey() const;
89
/* Accessors for JSObject types */
91
bool isSingleObject() const {
92
return isObject() && !!(data & 1);
95
inline JSObject *singleObject() const;
97
/* Accessors for TypeObject types */
99
bool isTypeObject() const {
100
return isObject() && !(data & 1);
103
inline TypeObject *typeObject() const;
105
bool operator == (Type o) const { return data == o.data; }
106
bool operator != (Type o) const { return data != o.data; }
108
static inline Type UndefinedType() { return Type(JSVAL_TYPE_UNDEFINED); }
109
static inline Type NullType() { return Type(JSVAL_TYPE_NULL); }
110
static inline Type BooleanType() { return Type(JSVAL_TYPE_BOOLEAN); }
111
static inline Type Int32Type() { return Type(JSVAL_TYPE_INT32); }
112
static inline Type DoubleType() { return Type(JSVAL_TYPE_DOUBLE); }
113
static inline Type StringType() { return Type(JSVAL_TYPE_STRING); }
114
static inline Type MagicArgType() { return Type(JSVAL_TYPE_MAGIC); }
115
static inline Type AnyObjectType() { return Type(JSVAL_TYPE_OBJECT); }
116
static inline Type UnknownType() { return Type(JSVAL_TYPE_UNKNOWN); }
118
static inline Type PrimitiveType(JSValueType type) {
119
JS_ASSERT(type < JSVAL_TYPE_UNKNOWN);
123
static inline Type ObjectType(JSObject *obj);
124
static inline Type ObjectType(TypeObject *obj);
125
static inline Type ObjectType(TypeObjectKey *obj);
128
/* Get the type of a jsval, or zero for an unknown special value. */
129
inline Type GetValueType(JSContext *cx, const Value &val);
132
* Type inference memory management overview.
134
* Inference constructs a global web of constraints relating the contents of
135
* type sets particular to various scripts and type objects within a
136
* compartment. This data can consume a significant amount of memory, and to
137
* avoid this building up we try to clear it with some regularity.
139
* There are two operations which can clear inference and analysis data.
141
* - Analysis purges clear analysis information while retaining jitcode.
143
* - GCs may clear both analysis information and jitcode. Sometimes GCs will
144
* preserve all information and code, and will not collect any scripts,
145
* type objects or singleton JS objects.
147
* There are several categories of data affected differently by the above
150
* - Data cleared by every analysis purge and non-preserving GC. This includes
151
* the ScriptAnalysis for each analyzed script and data from each analysis
152
* pass performed, type sets for stack values, and all type constraints for
153
* such type sets and for observed/argument/local type sets on scripts
154
* (TypeSet::constraintsPurged, aka StackTypeSet). This is exactly the data
155
* allocated using compartment->analysisLifoAlloc.
157
* - Data cleared by non-preserving GCs. This includes property type sets for
158
* singleton JS objects, property read input type sets, type constraints on
159
* all type sets, and dead references in all type sets. This data is all
160
* allocated using compartment->typeLifoAlloc; the GC copies live data into a
161
* new allocator and clears the old one.
163
* - Data cleared occasionally by non-preserving GCs. TypeScripts and the data
164
* in their sets are occasionally destroyed during GC. When a JSScript or
165
* TypeObject is swept, type information for its contents is destroyed.
169
* A constraint which listens to additions to a type set and propagates those
170
* changes to other type sets.
175
/* Next constraint listening to the same type set. */
176
TypeConstraint *next;
182
/* Debugging name for this kind of constraint. */
183
virtual const char *kind() = 0;
185
/* Register a new type for the set this constraint is listening to. */
186
virtual void newType(JSContext *cx, TypeSet *source, Type type) = 0;
189
* For constraints attached to an object property's type set, mark the
190
* property as having been configured or received an own property.
192
virtual void newPropertyState(JSContext *cx, TypeSet *source) {}
195
* For constraints attached to the JSID_EMPTY type set on an object, mark a
196
* change in one of the object's dynamic property flags. If force is set,
197
* recompilation is always triggered.
199
virtual void newObjectState(JSContext *cx, TypeObject *object, bool force) {}
202
/* Flags and other state stored in TypeSet::flags */
204
TYPE_FLAG_UNDEFINED = 0x1,
205
TYPE_FLAG_NULL = 0x2,
206
TYPE_FLAG_BOOLEAN = 0x4,
207
TYPE_FLAG_INT32 = 0x8,
208
TYPE_FLAG_DOUBLE = 0x10,
209
TYPE_FLAG_STRING = 0x20,
210
TYPE_FLAG_LAZYARGS = 0x40,
211
TYPE_FLAG_ANYOBJECT = 0x80,
213
/* Mask/shift for the number of objects in objectSet */
214
TYPE_FLAG_OBJECT_COUNT_MASK = 0xff00,
215
TYPE_FLAG_OBJECT_COUNT_SHIFT = 8,
216
TYPE_FLAG_OBJECT_COUNT_LIMIT =
217
TYPE_FLAG_OBJECT_COUNT_MASK >> TYPE_FLAG_OBJECT_COUNT_SHIFT,
219
/* Whether the contents of this type set are totally unknown. */
220
TYPE_FLAG_UNKNOWN = 0x00010000,
222
/* Mask of normal type flags on a type set. */
223
TYPE_FLAG_BASE_MASK = 0x000100ff,
225
/* Flags describing the kind of type set this is. */
228
* Flag for type sets which describe stack values and are cleared on
231
TYPE_FLAG_PURGED = 0x00020000,
234
* Flag for type sets whose constraints are cleared on analysis purges.
235
* This includes all temporary type sets, as well as sets in TypeScript
236
* which propagate into temporary type sets.
238
TYPE_FLAG_CONSTRAINTS_PURGED = 0x00040000,
240
/* Flags for type sets which are on object properties. */
243
* Whether there are subset constraints propagating the possible types
244
* for this property inherited from the object's prototypes. Reset on GC.
246
TYPE_FLAG_PROPAGATED_PROPERTY = 0x00080000,
248
/* Whether this property has ever been directly written. */
249
TYPE_FLAG_OWN_PROPERTY = 0x00100000,
252
* Whether the property has ever been deleted or reconfigured to behave
253
* differently from a normal native property (e.g. made non-writable or
254
* given a scripted getter or setter).
256
TYPE_FLAG_CONFIGURED_PROPERTY = 0x00200000,
259
* Whether the property is definitely in a particular inline slot on all
260
* objects from which it has not been deleted or reconfigured. Implies
261
* OWN_PROPERTY and unlike OWN/CONFIGURED property, this cannot change.
263
TYPE_FLAG_DEFINITE_PROPERTY = 0x00400000,
265
/* If the property is definite, mask and shift storing the slot. */
266
TYPE_FLAG_DEFINITE_MASK = 0x0f000000,
267
TYPE_FLAG_DEFINITE_SHIFT = 24
269
typedef uint32_t TypeFlags;
271
/* Flags and other state stored in TypeObject::flags */
273
/* Objects with this type are functions. */
274
OBJECT_FLAG_FUNCTION = 0x1,
276
/* If set, newScript information should not be installed on this object. */
277
OBJECT_FLAG_NEW_SCRIPT_CLEARED = 0x2,
280
* If set, type constraints covering the correctness of the newScript
281
* definite properties need to be regenerated before compiling any jitcode
282
* which depends on this information.
284
OBJECT_FLAG_NEW_SCRIPT_REGENERATE = 0x4,
287
* Whether we have ensured all type sets in the compartment contain
288
* ANYOBJECT instead of this object.
290
OBJECT_FLAG_SETS_MARKED_UNKNOWN = 0x8,
292
/* Mask/shift for the number of properties in propertySet */
293
OBJECT_FLAG_PROPERTY_COUNT_MASK = 0xfff0,
294
OBJECT_FLAG_PROPERTY_COUNT_SHIFT = 4,
295
OBJECT_FLAG_PROPERTY_COUNT_LIMIT =
296
OBJECT_FLAG_PROPERTY_COUNT_MASK >> OBJECT_FLAG_PROPERTY_COUNT_SHIFT,
299
* Some objects are not dense arrays, or are dense arrays whose length
300
* property does not fit in an int32_t.
302
OBJECT_FLAG_NON_DENSE_ARRAY = 0x00010000,
304
/* Whether any objects this represents are not packed arrays. */
305
OBJECT_FLAG_NON_PACKED_ARRAY = 0x00020000,
307
/* Whether any objects this represents are not typed arrays. */
308
OBJECT_FLAG_NON_TYPED_ARRAY = 0x00040000,
310
/* Whether any objects this represents are not DOM objects. */
311
OBJECT_FLAG_NON_DOM = 0x00080000,
313
/* Whether any represented script is considered uninlineable. */
314
OBJECT_FLAG_UNINLINEABLE = 0x00100000,
316
/* Whether any objects have an equality hook. */
317
OBJECT_FLAG_SPECIAL_EQUALITY = 0x00200000,
319
/* Whether any objects have been iterated over. */
320
OBJECT_FLAG_ITERATED = 0x00400000,
322
/* For a global object, whether flags were set on the RegExpStatics. */
323
OBJECT_FLAG_REGEXP_FLAGS_SET = 0x00800000,
325
/* Flags which indicate dynamic properties of represented objects. */
326
OBJECT_FLAG_DYNAMIC_MASK = 0x00ff0000,
329
* Whether all properties of this object are considered unknown.
330
* If set, all flags in DYNAMIC_MASK will also be set.
332
OBJECT_FLAG_UNKNOWN_PROPERTIES = 0x80000000,
334
/* Mask for objects created with unknown properties. */
335
OBJECT_FLAG_UNKNOWN_MASK =
336
OBJECT_FLAG_DYNAMIC_MASK
337
| OBJECT_FLAG_UNKNOWN_PROPERTIES
338
| OBJECT_FLAG_SETS_MARKED_UNKNOWN
340
typedef uint32_t TypeObjectFlags;
345
/* Information about the set of types associated with an lvalue. */
348
/* Flags for this type set. */
351
/* Possible objects this type set can represent. */
352
TypeObjectKey **objectSet;
356
/* Chain of constraints which propagate changes out from this type set. */
357
TypeConstraint *constraintList;
360
: flags(0), objectSet(NULL), constraintList(NULL)
363
void print(JSContext *cx);
365
inline void sweep(JSCompartment *compartment);
366
inline size_t computedSizeOfExcludingThis();
368
/* Whether this set contains a specific type. */
369
inline bool hasType(Type type);
371
TypeFlags baseFlags() const { return flags & TYPE_FLAG_BASE_MASK; }
372
bool unknown() const { return !!(flags & TYPE_FLAG_UNKNOWN); }
373
bool unknownObject() const { return !!(flags & (TYPE_FLAG_UNKNOWN | TYPE_FLAG_ANYOBJECT)); }
375
bool empty() const { return !baseFlags() && !baseObjectCount(); }
377
bool hasAnyFlag(TypeFlags flags) const {
378
JS_ASSERT((flags & TYPE_FLAG_BASE_MASK) == flags);
379
return !!(baseFlags() & flags);
382
bool ownProperty(bool configurable) const {
383
return flags & (configurable ? TYPE_FLAG_CONFIGURED_PROPERTY : TYPE_FLAG_OWN_PROPERTY);
385
bool definiteProperty() const { return flags & TYPE_FLAG_DEFINITE_PROPERTY; }
386
unsigned definiteSlot() const {
387
JS_ASSERT(definiteProperty());
388
return flags >> TYPE_FLAG_DEFINITE_SHIFT;
392
* Add a type to this set, calling any constraint handlers if this is a new
395
inline void addType(JSContext *cx, Type type);
397
/* Mark this type set as representing an own property or configured property. */
398
inline void setOwnProperty(JSContext *cx, bool configured);
401
* Iterate through the objects in this set. getObjectCount overapproximates
402
* in the hash case (see SET_ARRAY_SIZE in jsinferinlines.h), and getObject
405
inline unsigned getObjectCount();
406
inline TypeObjectKey *getObject(unsigned i);
407
inline JSObject *getSingleObject(unsigned i);
408
inline TypeObject *getTypeObject(unsigned i);
410
void setOwnProperty(bool configurable) {
411
flags |= TYPE_FLAG_OWN_PROPERTY;
413
flags |= TYPE_FLAG_CONFIGURED_PROPERTY;
415
void setDefinite(unsigned slot) {
416
JS_ASSERT(slot <= (TYPE_FLAG_DEFINITE_MASK >> TYPE_FLAG_DEFINITE_SHIFT));
417
flags |= TYPE_FLAG_DEFINITE_PROPERTY | (slot << TYPE_FLAG_DEFINITE_SHIFT);
420
bool hasPropagatedProperty() { return !!(flags & TYPE_FLAG_PROPAGATED_PROPERTY); }
421
void setPropagatedProperty() { flags |= TYPE_FLAG_PROPAGATED_PROPERTY; }
423
bool constraintsPurged() { return !!(flags & TYPE_FLAG_CONSTRAINTS_PURGED); }
424
void setConstraintsPurged() { flags |= TYPE_FLAG_CONSTRAINTS_PURGED; }
426
bool purged() { return !!(flags & TYPE_FLAG_PURGED); }
427
void setPurged() { flags |= TYPE_FLAG_PURGED | TYPE_FLAG_CONSTRAINTS_PURGED; }
429
inline StackTypeSet *toStackTypeSet();
430
inline HeapTypeSet *toHeapTypeSet();
432
inline void addTypesToConstraint(JSContext *cx, TypeConstraint *constraint);
433
inline void add(JSContext *cx, TypeConstraint *constraint, bool callExisting = true);
436
uint32_t baseObjectCount() const {
437
return (flags & TYPE_FLAG_OBJECT_COUNT_MASK) >> TYPE_FLAG_OBJECT_COUNT_SHIFT;
439
inline void setBaseObjectCount(uint32_t count);
441
inline void clearObjects();
445
* Type set for a stack value manipulated in a script, or the argument or
446
* local types of said script. Constraints on these type sets are cleared
447
* during analysis purges; the contents of the sets are implicitly frozen
448
* during compilation to ensure that changes to the sets trigger recompilation
449
* of the associated script.
451
class StackTypeSet : public TypeSet
456
* Make a type set with the specified debugging name, not embedded in
459
static StackTypeSet *make(JSContext *cx, const char *name);
461
/* Constraints for type inference. */
463
void addSubset(JSContext *cx, TypeSet *target);
464
void addGetProperty(JSContext *cx, JSScript *script, jsbytecode *pc,
465
StackTypeSet *target, jsid id);
466
void addSetProperty(JSContext *cx, JSScript *script, jsbytecode *pc,
467
StackTypeSet *target, jsid id);
468
void addSetElement(JSContext *cx, JSScript *script, jsbytecode *pc,
469
StackTypeSet *objectTypes, StackTypeSet *valueTypes);
470
void addCall(JSContext *cx, TypeCallsite *site);
471
void addArith(JSContext *cx, JSScript *script, jsbytecode *pc,
472
TypeSet *target, TypeSet *other = NULL);
473
void addTransformThis(JSContext *cx, JSScript *script, TypeSet *target);
474
void addPropagateThis(JSContext *cx, JSScript *script, jsbytecode *pc,
475
Type type, StackTypeSet *types = NULL);
476
void addSubsetBarrier(JSContext *cx, JSScript *script, jsbytecode *pc, TypeSet *target);
479
* Constraints for JIT compilation.
481
* Methods for JIT compilation. These must be used when a script is
482
* currently being compiled (see AutoEnterCompilation) and will add
483
* constraints ensuring that if the return value change in the future due
484
* to new type information, the script's jitcode will be discarded.
487
/* Get any type tag which all values in this set must have. */
488
JSValueType getKnownTypeTag();
490
bool isMagicArguments() { return getKnownTypeTag() == JSVAL_TYPE_MAGIC; }
492
/* Whether the type set contains objects with any of a set of flags. */
493
bool hasObjectFlags(JSContext *cx, TypeObjectFlags flags);
496
* Get the typed array type of all objects in this set. Returns
497
* TypedArray::TYPE_MAX if the set contains different array types.
499
int getTypedArrayType();
501
/* Get the single value which can appear in this type set, otherwise NULL. */
502
JSObject *getSingleton();
504
/* Whether any objects in the type set needs a barrier on id. */
505
bool propertyNeedsBarrier(JSContext *cx, jsid id);
509
* Type set for a property of a TypeObject, or for the return value or property
510
* read inputs of a script. In contrast with stack type sets, constraints on
511
* these sets are not cleared during analysis purges, and are not implicitly
512
* frozen during compilation.
514
class HeapTypeSet : public TypeSet
518
/* Constraints for type inference. */
520
void addSubset(JSContext *cx, TypeSet *target);
521
void addGetProperty(JSContext *cx, JSScript *script, jsbytecode *pc,
522
StackTypeSet *target, jsid id);
523
void addCallProperty(JSContext *cx, JSScript *script, jsbytecode *pc, jsid id);
524
void addFilterPrimitives(JSContext *cx, TypeSet *target);
525
void addSubsetBarrier(JSContext *cx, JSScript *script, jsbytecode *pc, TypeSet *target);
527
/* Constraints for JIT compilation. */
529
/* Completely freeze the contents of this type set. */
530
void addFreeze(JSContext *cx);
534
* Watch for a generic object state change on a type object. This currently
535
* includes reallocations of slot pointers for global objects, and changes
536
* to newScript data on types.
538
static void WatchObjectStateChange(JSContext *cx, TypeObject *object);
540
/* Whether an object has any of a set of flags. */
541
static bool HasObjectFlags(JSContext *cx, TypeObject *object, TypeObjectFlags flags);
544
* For type sets on a property, return true if the property has any 'own'
545
* values assigned. If configurable is set, return 'true' if the property
546
* has additionally been reconfigured as non-configurable, non-enumerable
547
* or non-writable (this only applies to properties that have changed after
548
* having been created, not to e.g. properties non-writable on creation).
550
bool isOwnProperty(JSContext *cx, TypeObject *object, bool configurable);
552
/* Get whether this type set is non-empty. */
553
bool knownNonEmpty(JSContext *cx);
555
/* Get whether this type set is known to be a subset of other. */
556
bool knownSubset(JSContext *cx, TypeSet *other);
558
/* Get the single value which can appear in this type set, otherwise NULL. */
559
JSObject *getSingleton(JSContext *cx);
562
* Whether a location with this TypeSet needs a write barrier (i.e., whether
563
* it can hold GC things). The type set is frozen if no barrier is needed.
565
bool needsBarrier(JSContext *cx);
568
inline StackTypeSet *
569
TypeSet::toStackTypeSet()
571
JS_ASSERT(constraintsPurged());
572
return (StackTypeSet *) this;
576
TypeSet::toHeapTypeSet()
578
JS_ASSERT(!constraintsPurged());
579
return (HeapTypeSet *) this;
583
* Handler which persists information about dynamic types pushed within a
584
* script which can affect its behavior and are not covered by JOF_TYPESET ops,
585
* such as integer operations which overflow to a double. These persist across
586
* GCs, and are used to re-seed script types when they are reanalyzed.
594
TypeResult(uint32_t offset, Type type)
595
: offset(offset), type(type), next(NULL)
600
* Type barriers overview.
602
* Type barriers are a technique for using dynamic type information to improve
603
* the inferred types within scripts. At certain opcodes --- those with the
604
* JOF_TYPESET format --- we will construct a type set storing the set of types
605
* which we have observed to be pushed at that opcode, and will only use those
606
* observed types when doing propagation downstream from the bytecode. For
607
* example, in the following script:
613
* Suppose we know the type of 'x' and that the type of its 'f' property is
614
* either an int or float. To account for all possible behaviors statically,
615
* we would mark the result of the 'x.f' access as an int or float, as well
616
* as the result of the addition and the return value of foo (and everywhere
617
* the result of 'foo' is used). When dealing with polymorphic code, this is
618
* undesirable behavior --- the type imprecision surrounding the polymorphism
619
* will tend to leak to many places in the program.
621
* Instead, we will keep track of the types that have been dynamically observed
622
* to have been produced by the 'x.f', and only use those observed types
623
* downstream from the access. If the 'x.f' has only ever produced integers,
624
* we will treat its result as an integer and mark the result of foo as an
627
* The set of observed types will be a subset of the set of possible types,
628
* and if the two sets are different, a type barriers will be added at the
629
* bytecode which checks the dynamic result every time the bytecode executes
630
* and makes sure it is in the set of observed types. If it is not, that
631
* observed set is updated, and the new type information is automatically
632
* propagated along the already-generated type constraints to the places
633
* where the result of the bytecode is used.
635
* Observing new types at a bytecode removes type barriers at the bytecode
636
* (this removal happens lazily, see ScriptAnalysis::pruneTypeBarriers), and if
637
* all type barriers at a bytecode are removed --- the set of observed types
638
* grows to match the set of possible types --- then the result of the bytecode
639
* no longer needs to be dynamically checked (unless the set of possible types
640
* grows, triggering the generation of new type barriers).
642
* Barriers are only relevant for accesses on properties whose types inference
643
* actually tracks (see propertySet comment under TypeObject). Accesses on
644
* other properties may be able to produce additional unobserved types even
645
* without a barrier present, and can only be compiled to jitcode with special
646
* knowledge of the property in question (e.g. for lengths of arrays, or
647
* elements of typed arrays).
651
* Barrier introduced at some bytecode. These are added when, during inference,
652
* we block a type from being propagated as would normally be done for a subset
653
* constraint. The propagation is technically possible, but we suspect it will
654
* not happen dynamically and this type needs to be watched for. These are only
655
* added at reads of properties and at scripted call sites.
659
/* Next barrier on the same bytecode. */
662
/* Target type set into which propagation was blocked. */
666
* Type which was not added to the target. If target ends up containing the
667
* type somehow, this barrier can be removed.
672
* If specified, this barrier can be removed if object has a non-undefined
673
* value in property id.
678
TypeBarrier(TypeSet *target, Type type, JSObject *singleton, jsid singletonId)
679
: next(NULL), target(target), type(type),
680
singleton(singleton), singletonId(singletonId)
684
/* Type information about a property. */
687
/* Identifier for this property, JSID_VOID for the aggregate integer index property. */
690
/* Possible types for this property, including types inherited from prototypes. */
693
inline Property(jsid id);
694
inline Property(const Property &o);
696
static uint32_t keyBits(jsid id) { return uint32_t(JSID_BITS(id)); }
697
static jsid getKey(Property *p) { return p->id; }
701
* Information attached to a TypeObject if it is always constructed using 'new'
702
* on a particular script. This is used to manage state related to the definite
703
* properties on the type object: these definite properties depend on type
704
* information which could change as the script executes (e.g. a scripted
705
* setter is added to a prototype object), and we need to ensure both that the
706
* appropriate type constraints are in place when necessary, and that we can
707
* remove the definite property information and repair the JS stack if the
708
* constraints are violated.
714
/* Allocation kind to use for newly constructed objects. */
715
gc::AllocKind allocKind;
718
* Shape to use for newly constructed objects. Reflects all definite
719
* properties the object will have.
724
* Order in which properties become initialized. We need this in case a
725
* scripted setter is added to one of the object's prototypes while it is
726
* in the middle of being initialized, so we can walk the stack and fixup
727
* any objects which look for in-progress objects which were prematurely
728
* set with their final shape. Initialization can traverse stack frames,
729
* in which case FRAME_PUSH/FRAME_POP are used.
739
Initializer(Kind kind, uint32_t offset)
740
: kind(kind), offset(offset)
743
Initializer *initializerList;
745
static inline void writeBarrierPre(TypeNewScript *newScript);
746
static inline void writeBarrierPost(TypeNewScript *newScript, void *addr);
750
* Lazy type objects overview.
752
* Type objects which represent at most one JS object are constructed lazily.
753
* These include types for native functions, standard classes, scripted
754
* functions defined at the top level of global/eval scripts, and in some
755
* other cases. Typical web workloads often create many windows (and many
756
* copies of standard natives) and many scripts, with comparatively few
757
* non-singleton types.
759
* We can recover the type information for the object from examining it,
760
* so don't normally track the possible types of its properties as it is
761
* updated. Property type sets for the object are only constructed when an
762
* analyzed script attaches constraints to it: the script is querying that
763
* property off the object or another which delegates to it, and the analysis
764
* information is sensitive to changes in the property's type. Future changes
765
* to the property (whether those uncovered by analysis or those occurring
766
* in the VM) will treat these properties like those of any other type object.
768
* When a GC occurs, we wipe out all analysis information for all the
769
* compartment's scripts, so can destroy all properties on singleton type
770
* objects at the same time. If there is no reference on the stack to the
771
* type object itself, the type object is also destroyed, and the JS object
772
* reverts to having a lazy type.
775
/* Type information about an object accessed by a script. */
776
struct TypeObject : gc::Cell
778
/* Prototype shared by objects using this type. */
782
* Whether there is a singleton JS object with this type. That JS object
783
* must appear in type sets instead of this; we include the back reference
784
* here to allow reverting the JS object to a lazy type.
786
HeapPtrObject singleton;
789
* Value held by singleton if this is a standin type for a singleton JS
790
* object whose type has not been constructed yet.
792
static const size_t LAZY_SINGLETON = 1;
793
bool lazy() const { return singleton == (JSObject *) LAZY_SINGLETON; }
795
/* Flags for this object. */
796
TypeObjectFlags flags;
799
* Estimate of the contribution of this object to the type sets it appears in.
800
* This is the sum of the sizes of those sets at the point when the object
803
* When the contribution exceeds the CONTRIBUTION_LIMIT, any type sets the
804
* object is added to are instead marked as unknown. If we get to this point
805
* we are probably not adding types which will let us do meaningful optimization
806
* later, and we want to ensure in such cases that our time/space complexity
807
* is linear, not worst-case cubic as it would otherwise be.
809
uint32_t contribution;
810
static const uint32_t CONTRIBUTION_LIMIT = 2000;
813
* If non-NULL, objects of this type have always been constructed using
814
* 'new' on the specified script, which adds some number of properties to
815
* the object in a definite order before the object escapes.
817
HeapPtr<TypeNewScript> newScript;
820
* Properties of this object. This may contain JSID_VOID, representing the
821
* types of all integer indexes of the object, and/or JSID_EMPTY, holding
822
* constraints listening to changes to the object's state.
824
* The type sets in the properties of a type object describe the possible
825
* values that can be read out of that property in actual JS objects.
826
* Properties only account for native properties (those with a slot and no
827
* specialized getter hook) and the elements of dense arrays. For accesses
828
* on such properties, the correspondence is as follows:
830
* 1. If the type has unknownProperties(), the possible properties and
831
* value types for associated JSObjects are unknown.
833
* 2. Otherwise, for any JSObject obj with TypeObject type, and any jsid id
834
* which is a property in obj, before obj->getProperty(id) the property
835
* in type for id must reflect the result of the getProperty.
837
* There is an exception for properties of singleton JS objects which
838
* are undefined at the point where the property was (lazily) generated.
839
* In such cases the property type set will remain empty, and the
840
* 'undefined' type will only be added after a subsequent assignment or
841
* deletion. After these properties have been assigned a defined value,
842
* the only way they can become undefined again is after such an assign
845
* We establish these by using write barriers on calls to setProperty and
846
* defineProperty which are on native properties, and by using the inference
847
* analysis to determine the side effects of code which is JIT-compiled.
849
Property **propertySet;
851
/* If this is an interpreted function, the function object. */
852
HeapPtrFunction interpretedFunction;
854
#if JS_BITS_PER_WORD == 32
858
inline TypeObject(JSObject *proto, bool isFunction, bool unknown);
860
bool isFunction() { return !!(flags & OBJECT_FLAG_FUNCTION); }
862
bool hasAnyFlags(TypeObjectFlags flags) {
863
JS_ASSERT((flags & OBJECT_FLAG_DYNAMIC_MASK) == flags);
864
return !!(this->flags & flags);
866
bool hasAllFlags(TypeObjectFlags flags) {
867
JS_ASSERT((flags & OBJECT_FLAG_DYNAMIC_MASK) == flags);
868
return (this->flags & flags) == flags;
871
bool unknownProperties() {
872
JS_ASSERT_IF(flags & OBJECT_FLAG_UNKNOWN_PROPERTIES,
873
hasAllFlags(OBJECT_FLAG_DYNAMIC_MASK));
874
return !!(flags & OBJECT_FLAG_UNKNOWN_PROPERTIES);
878
* Get or create a property of this object. Only call this for properties which
879
* a script accesses explicitly. 'assign' indicates whether this is for an
880
* assignment, and the own types of the property will be used instead of
883
inline HeapTypeSet *getProperty(JSContext *cx, jsid id, bool own);
885
/* Get a property only if it already exists. */
886
inline HeapTypeSet *maybeGetProperty(JSContext *cx, jsid id);
888
inline unsigned getPropertyCount();
889
inline Property *getProperty(unsigned i);
891
/* Set flags on this object which are implied by the specified key. */
892
inline void setFlagsFromKey(JSContext *cx, JSProtoKey kind);
895
* Get the global object which all objects of this type are parented to,
896
* or NULL if there is none known.
898
//inline JSObject *getGlobal();
902
bool addProperty(JSContext *cx, jsid id, Property **pprop);
903
bool addDefiniteProperties(JSContext *cx, JSObject *obj);
904
bool matchDefiniteProperties(JSObject *obj);
905
void addPrototype(JSContext *cx, TypeObject *proto);
906
void addPropertyType(JSContext *cx, jsid id, Type type);
907
void addPropertyType(JSContext *cx, jsid id, const Value &value);
908
void addPropertyType(JSContext *cx, const char *name, Type type);
909
void addPropertyType(JSContext *cx, const char *name, const Value &value);
910
void markPropertyConfigured(JSContext *cx, jsid id);
911
void markStateChange(JSContext *cx);
912
void setFlags(JSContext *cx, TypeObjectFlags flags);
913
void markUnknown(JSContext *cx);
914
void clearNewScript(JSContext *cx);
915
void getFromPrototypes(JSContext *cx, jsid id, TypeSet *types, bool force = false);
917
void print(JSContext *cx);
919
inline void clearProperties();
920
inline void sweep(FreeOp *fop);
922
inline size_t computedSizeOfExcludingThis();
924
void sizeOfExcludingThis(TypeInferenceSizes *sizes, JSMallocSizeOfFun mallocSizeOf);
927
* Type objects don't have explicit finalizers. Memory owned by a type
928
* object pending deletion is released when weak references are sweeped
929
* from all the compartment's type objects.
931
void finalize(FreeOp *fop) {}
933
static inline void writeBarrierPre(TypeObject *type);
934
static inline void writeBarrierPost(TypeObject *type, void *addr);
935
static inline void readBarrier(TypeObject *type);
937
static inline ThingRootKind rootKind() { return THING_ROOT_TYPE_OBJECT; }
940
inline uint32_t basePropertyCount() const;
941
inline void setBasePropertyCount(uint32_t count);
943
static void staticAsserts() {
944
JS_STATIC_ASSERT(offsetof(TypeObject, proto) == offsetof(js::shadow::TypeObject, proto));
949
* Entries for the per-compartment set of type objects which are the default
950
* 'new' or the lazy types of some prototype.
952
struct TypeObjectEntry
954
typedef JSObject *Lookup;
956
static inline HashNumber hash(JSObject *base);
957
static inline bool match(TypeObject *key, JSObject *lookup);
959
typedef HashSet<ReadBarriered<TypeObject>, TypeObjectEntry, SystemAllocPolicy> TypeObjectSet;
961
/* Whether to use a new type object when calling 'new' at script/pc. */
963
UseNewType(JSContext *cx, JSScript *script, jsbytecode *pc);
965
/* Whether to use a new type object for an initializer opcode at script/pc. */
967
UseNewTypeForInitializer(JSContext *cx, JSScript *script, jsbytecode *pc, JSProtoKey key);
970
* Whether Array.prototype, or an object on its proto chain, has an
974
ArrayPrototypeHasIndexedProperty(JSContext *cx, JSScript *script);
977
* Type information about a callsite. this is separated from the bytecode
978
* information itself so we can handle higher order functions not called
979
* directly via a bytecode.
986
/* Whether this is a 'NEW' call. */
989
/* Types of each argument to the call. */
990
unsigned argumentCount;
991
StackTypeSet **argumentTypes;
993
/* Types of the this variable. */
994
StackTypeSet *thisTypes;
996
/* Type set receiving the return value of this call. */
997
StackTypeSet *returnTypes;
999
inline TypeCallsite(JSContext *cx, JSScript *script, jsbytecode *pc,
1000
bool isNew, unsigned argumentCount);
1003
/* Persistent type information for a script, retained across GCs. */
1006
friend struct ::JSScript;
1008
/* Analysis information for the script, cleared on each GC. */
1009
analyze::ScriptAnalysis *analysis;
1012
/* Dynamic types generated at points within this script. */
1013
TypeResult *dynamicList;
1016
* Array of type sets storing the possible inputs to property reads.
1017
* Generated the first time the script is analyzed by inference and kept
1018
* after analysis purges.
1020
HeapTypeSet *propertyReadTypes;
1022
/* Array of type type sets for variables and JOF_TYPESET ops. */
1023
TypeSet *typeArray() { return (TypeSet *) (uintptr_t(this) + sizeof(TypeScript)); }
1025
static inline unsigned NumTypeSets(JSScript *script);
1027
static inline HeapTypeSet *ReturnTypes(JSScript *script);
1028
static inline StackTypeSet *ThisTypes(JSScript *script);
1029
static inline StackTypeSet *ArgTypes(JSScript *script, unsigned i);
1030
static inline StackTypeSet *LocalTypes(JSScript *script, unsigned i);
1032
/* Follows slot layout in jsanalyze.h, can get this/arg/local type sets. */
1033
static inline StackTypeSet *SlotTypes(JSScript *script, unsigned slot);
1036
/* Check that correct types were inferred for the values pushed by this bytecode. */
1037
static void CheckBytecode(JSContext *cx, JSScript *script, jsbytecode *pc, const js::Value *sp);
1040
/* Get the default 'new' object for a given standard class, per the script's global. */
1041
static inline TypeObject *StandardType(JSContext *cx, JSScript *script, JSProtoKey kind);
1043
/* Get a type object for an allocation site in this script. */
1044
static inline TypeObject *InitObject(JSContext *cx, JSScript *script, jsbytecode *pc, JSProtoKey kind);
1047
* Monitor a bytecode pushing a value which is not accounted for by the
1048
* inference type constraints, such as integer overflow.
1050
static inline void MonitorOverflow(JSContext *cx, JSScript *script, jsbytecode *pc);
1051
static inline void MonitorString(JSContext *cx, JSScript *script, jsbytecode *pc);
1052
static inline void MonitorUnknown(JSContext *cx, JSScript *script, jsbytecode *pc);
1054
static inline void GetPcScript(JSContext *cx, JSScript **script, jsbytecode **pc);
1055
static inline void MonitorOverflow(JSContext *cx);
1056
static inline void MonitorString(JSContext *cx);
1057
static inline void MonitorUnknown(JSContext *cx);
1060
* Monitor a bytecode pushing any value. This must be called for any opcode
1061
* which is JOF_TYPESET, and where either the script has not been analyzed
1062
* by type inference or where the pc has type barriers. For simplicity, we
1063
* always monitor JOF_TYPESET opcodes in the interpreter and stub calls,
1064
* and only look at barriers when generating JIT code for the script.
1066
static inline void Monitor(JSContext *cx, JSScript *script, jsbytecode *pc,
1067
const js::Value &val);
1068
static inline void Monitor(JSContext *cx, const js::Value &rval);
1070
/* Monitor an assignment at a SETELEM on a non-integer identifier. */
1071
static inline void MonitorAssign(JSContext *cx, JSObject *obj, jsid id);
1073
/* Add a type for a variable in a script. */
1074
static inline void SetThis(JSContext *cx, JSScript *script, Type type);
1075
static inline void SetThis(JSContext *cx, JSScript *script, const js::Value &value);
1076
static inline void SetLocal(JSContext *cx, JSScript *script, unsigned local, Type type);
1077
static inline void SetLocal(JSContext *cx, JSScript *script, unsigned local, const js::Value &value);
1078
static inline void SetArgument(JSContext *cx, JSScript *script, unsigned arg, Type type);
1079
static inline void SetArgument(JSContext *cx, JSScript *script, unsigned arg, const js::Value &value);
1081
static void AddFreezeConstraints(JSContext *cx, JSScript *script);
1082
static void Purge(JSContext *cx, JSScript *script);
1084
static void Sweep(FreeOp *fop, JSScript *script);
1088
struct ArrayTableKey;
1089
typedef HashMap<ArrayTableKey,ReadBarriered<TypeObject>,ArrayTableKey,SystemAllocPolicy> ArrayTypeTable;
1091
struct ObjectTableKey;
1092
struct ObjectTableEntry;
1093
typedef HashMap<ObjectTableKey,ObjectTableEntry,ObjectTableKey,SystemAllocPolicy> ObjectTypeTable;
1095
struct AllocationSiteKey;
1096
typedef HashMap<AllocationSiteKey,ReadBarriered<TypeObject>,AllocationSiteKey,SystemAllocPolicy> AllocationSiteTable;
1099
* Information about the result of the compilation of a script. This structure
1100
* stored in the TypeCompartment is indexed by the RecompileInfo. This
1101
* indirection enable the invalidation of all constraints related to the same
1102
* compilation. The compiler output is build by the AutoEnterCompilation.
1104
struct CompilerOutput
1107
bool constructing : 1;
1109
bool pendingRecompilation : 1;
1110
uint32_t chunkIndex:29;
1114
bool isJM() const { return true; }
1116
mjit::JITScript * mjit() const;
1118
bool isValid() const;
1120
void setPendingRecompilation() {
1121
pendingRecompilation = true;
1128
struct RecompileInfo
1130
static const uint32_t NoCompilerRunning = uint32_t(-1);
1131
uint32_t outputIndex;
1134
: outputIndex(NoCompilerRunning)
1138
bool operator == (const RecompileInfo &o) const {
1139
return outputIndex == o.outputIndex;
1141
CompilerOutput *compilerOutput(TypeCompartment &types) const;
1142
CompilerOutput *compilerOutput(JSContext *cx) const;
1145
/* Type information for a compartment. */
1146
struct TypeCompartment
1148
/* Constraint solving worklist structures. */
1151
* Worklist of types which need to be propagated to constraints. We use a
1152
* worklist to avoid blowing the native stack.
1156
TypeConstraint *constraint;
1160
PendingWork *pendingArray;
1161
unsigned pendingCount;
1162
unsigned pendingCapacity;
1164
/* Whether we are currently resolving the pending worklist. */
1167
/* Whether type inference is enabled in this compartment. */
1168
bool inferenceEnabled;
1171
* Bit set if all current types must be marked as unknown, and all scripts
1172
* recompiled. Caused by OOM failure within inference operations.
1174
bool pendingNukeTypes;
1176
/* Number of scripts in this compartment. */
1177
unsigned scriptCount;
1179
/* Valid & Invalid script referenced by type constraints. */
1180
Vector<CompilerOutput> *constrainedOutputs;
1182
/* Pending recompilations to perform before execution of JIT code can resume. */
1183
Vector<RecompileInfo> *pendingRecompiles;
1186
* Number of recompilation events and inline frame expansions that have
1187
* occurred in this compartment. If these change, code should not count on
1188
* compiled code or the current stack being intact.
1190
unsigned recompilations;
1191
unsigned frameExpansions;
1194
* Script currently being compiled. All constraints which look for type
1195
* changes inducing recompilation are keyed to this script. Note: script
1196
* compilation is not reentrant.
1198
RecompileInfo compiledInfo;
1200
/* Table for referencing types of objects keyed to an allocation site. */
1201
AllocationSiteTable *allocationSiteTable;
1203
/* Tables for determining types of singleton/JSON objects. */
1205
ArrayTypeTable *arrayTypeTable;
1206
ObjectTypeTable *objectTypeTable;
1208
void fixArrayType(JSContext *cx, JSObject *obj);
1209
void fixObjectType(JSContext *cx, JSObject *obj);
1211
/* Logging fields */
1213
/* Counts of stack type sets with some number of possible operand types. */
1214
static const unsigned TYPE_COUNT_LIMIT = 4;
1215
unsigned typeCounts[TYPE_COUNT_LIMIT];
1216
unsigned typeCountOver;
1218
void init(JSContext *cx);
1221
inline JSCompartment *compartment();
1223
/* Add a type to register with a list of constraints. */
1224
inline void addPending(JSContext *cx, TypeConstraint *constraint, TypeSet *source, Type type);
1225
bool growPendingArray(JSContext *cx);
1227
/* Resolve pending type registrations, excluding delayed ones. */
1228
inline void resolvePending(JSContext *cx);
1230
/* Prints results of this compartment if spew is enabled or force is set. */
1231
void print(JSContext *cx, bool force);
1234
* Make a function or non-function object associated with an optional
1235
* script. The 'key' parameter here may be an array, typed array, function
1236
* or JSProto_Object to indicate a type whose class is unknown (not just
1239
TypeObject *newTypeObject(JSContext *cx, JSScript *script,
1240
JSProtoKey kind, JSObject *proto,
1241
bool unknown = false, bool isDOM = false);
1243
/* Make an object for an allocation site. */
1244
TypeObject *newAllocationSiteTypeObject(JSContext *cx, AllocationSiteKey key);
1246
void nukeTypes(FreeOp *fop);
1247
void processPendingRecompiles(FreeOp *fop);
1249
/* Mark all types as needing destruction once inference has 'finished'. */
1250
void setPendingNukeTypes(JSContext *cx);
1251
void setPendingNukeTypesNoReport();
1253
/* Mark a script as needing recompilation once inference has finished. */
1254
void addPendingRecompile(JSContext *cx, const RecompileInfo &info);
1255
void addPendingRecompile(JSContext *cx, JSScript *script, jsbytecode *pc);
1257
/* Monitor future effects on a bytecode. */
1258
void monitorBytecode(JSContext *cx, JSScript *script, uint32_t offset,
1259
bool returnOnly = false);
1261
/* Mark any type set containing obj as having a generic object type. */
1262
void markSetsUnknown(JSContext *cx, TypeObject *obj);
1264
void sweep(FreeOp *fop);
1265
void sweepCompilerOutputs(FreeOp *fop, bool discardConstraints);
1267
void maybePurgeAnalysis(JSContext *cx, bool force = false);
1269
void finalizeObjects();
1273
ISpewOps, /* ops: New constraints and types. */
1274
ISpewResult, /* result: Final type sets. */
1280
const char * InferSpewColorReset();
1281
const char * InferSpewColor(TypeConstraint *constraint);
1282
const char * InferSpewColor(TypeSet *types);
1284
void InferSpew(SpewChannel which, const char *fmt, ...);
1285
const char * TypeString(Type type);
1286
const char * TypeObjectString(TypeObject *type);
1288
/* Check that the type property for id in obj contains value. */
1289
bool TypeHasProperty(JSContext *cx, TypeObject *obj, jsid id, const Value &value);
1293
inline const char * InferSpewColorReset() { return NULL; }
1294
inline const char * InferSpewColor(TypeConstraint *constraint) { return NULL; }
1295
inline const char * InferSpewColor(TypeSet *types) { return NULL; }
1296
inline void InferSpew(SpewChannel which, const char *fmt, ...) {}
1297
inline const char * TypeString(Type type) { return NULL; }
1298
inline const char * TypeObjectString(TypeObject *type) { return NULL; }
1302
/* Print a warning, dump state and abort the program. */
1303
MOZ_NORETURN void TypeFailure(JSContext *cx, const char *fmt, ...);
1305
} /* namespace types */
1306
} /* namespace js */
1308
#endif // jsinfer_h___