← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/JavaScriptCore/dfg/DFGAbstractValue.h

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
Source/JavaScriptCore/dfg/DFGAbstractValue.h
 
1
/*
 
2
 * Copyright (C) 2011, 2012 Apple Inc. All rights reserved.
 
3
 *
 
4
 * Redistribution and use in source and binary forms, with or without
 
5
 * modification, are permitted provided that the following conditions
 
6
 * are met:
 
7
 * 1. Redistributions of source code must retain the above copyright
 
8
 *    notice, this list of conditions and the following disclaimer.
 
9
 * 2. Redistributions in binary form must reproduce the above copyright
 
10
 *    notice, this list of conditions and the following disclaimer in the
 
11
 *    documentation and/or other materials provided with the distribution.
 
12
 *
 
13
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 
14
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
15
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 
16
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 
17
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 
18
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 
19
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 
20
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 
21
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
22
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 
23
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 
24
 */
 
25
 
 
26
#ifndef DFGAbstractValue_h
 
27
#define DFGAbstractValue_h
 
28
 
 
29
#include <wtf/Platform.h>
 
30
 
 
31
#if ENABLE(DFG_JIT)
 
32
 
 
33
#include "ArrayProfile.h"
 
34
#include "DFGStructureAbstractValue.h"
 
35
#include "JSCell.h"
 
36
#include "SpeculatedType.h"
 
37
#include "StructureSet.h"
 
38
 
 
39
namespace JSC { namespace DFG {
 
40
 
 
41
struct AbstractValue {
 
42
    AbstractValue()
 
43
        : m_type(SpecNone)
 
44
        , m_arrayModes(0)
 
45
    {
 
46
    }
 
47
    
 
48
    void clear()
 
49
    {
 
50
        m_type = SpecNone;
 
51
        m_arrayModes = 0;
 
52
        m_currentKnownStructure.clear();
 
53
        m_futurePossibleStructure.clear();
 
54
        m_value = JSValue();
 
55
        checkConsistency();
 
56
    }
 
57
    
 
58
    bool isClear() const
 
59
    {
 
60
        bool result = m_type == SpecNone && !m_arrayModes && m_currentKnownStructure.isClear() && m_futurePossibleStructure.isClear();
 
61
        if (result)
 
62
            ASSERT(!m_value);
 
63
        return result;
 
64
    }
 
65
    
 
66
    void makeTop()
 
67
    {
 
68
        m_type = SpecTop;
 
69
        m_arrayModes = ALL_ARRAY_MODES;
 
70
        m_currentKnownStructure.makeTop();
 
71
        m_futurePossibleStructure.makeTop();
 
72
        m_value = JSValue();
 
73
        checkConsistency();
 
74
    }
 
75
    
 
76
    void clobberStructures()
 
77
    {
 
78
        if (m_type & SpecCell) {
 
79
            m_currentKnownStructure.makeTop();
 
80
            clobberArrayModes();
 
81
        } else {
 
82
            ASSERT(m_currentKnownStructure.isClear());
 
83
            ASSERT(!m_arrayModes);
 
84
        }
 
85
        checkConsistency();
 
86
    }
 
87
        
 
88
    void clobberValue()
 
89
    {
 
90
        m_value = JSValue();
 
91
    }
 
92
    
 
93
    bool isTop() const
 
94
    {
 
95
        return m_type == SpecTop && m_currentKnownStructure.isTop() && m_futurePossibleStructure.isTop();
 
96
    }
 
97
    
 
98
    bool valueIsTop() const
 
99
    {
 
100
        return !m_value && m_type;
 
101
    }
 
102
    
 
103
    JSValue value() const
 
104
    {
 
105
        return m_value;
 
106
    }
 
107
    
 
108
    static AbstractValue top()
 
109
    {
 
110
        AbstractValue result;
 
111
        result.makeTop();
 
112
        return result;
 
113
    }
 
114
    
 
115
    void setMostSpecific(JSValue value)
 
116
    {
 
117
        if (!!value && value.isCell()) {
 
118
            Structure* structure = value.asCell()->structure();
 
119
            m_currentKnownStructure = structure;
 
120
            setFuturePossibleStructure(structure);
 
121
            m_arrayModes = asArrayModes(structure->indexingType());
 
122
        } else {
 
123
            m_currentKnownStructure.clear();
 
124
            m_futurePossibleStructure.clear();
 
125
            m_arrayModes = 0;
 
126
        }
 
127
        
 
128
        m_type = speculationFromValue(value);
 
129
        m_value = value;
 
130
        
 
131
        checkConsistency();
 
132
    }
 
133
    
 
134
    void set(JSValue value)
 
135
    {
 
136
        if (!!value && value.isCell()) {
 
137
            m_currentKnownStructure.makeTop();
 
138
            Structure* structure = value.asCell()->structure();
 
139
            setFuturePossibleStructure(structure);
 
140
            m_arrayModes = asArrayModes(structure->indexingType());
 
141
            clobberArrayModes();
 
142
        } else {
 
143
            m_currentKnownStructure.clear();
 
144
            m_futurePossibleStructure.clear();
 
145
            m_arrayModes = 0;
 
146
        }
 
147
        
 
148
        m_type = speculationFromValue(value);
 
149
        m_value = value;
 
150
        
 
151
        checkConsistency();
 
152
    }
 
153
    
 
154
    void set(Structure* structure)
 
155
    {
 
156
        m_currentKnownStructure = structure;
 
157
        setFuturePossibleStructure(structure);
 
158
        m_arrayModes = asArrayModes(structure->indexingType());
 
159
        m_type = speculationFromStructure(structure);
 
160
        m_value = JSValue();
 
161
        
 
162
        checkConsistency();
 
163
    }
 
164
    
 
165
    void set(SpeculatedType type)
 
166
    {
 
167
        if (type & SpecCell) {
 
168
            m_currentKnownStructure.makeTop();
 
169
            m_futurePossibleStructure.makeTop();
 
170
            m_arrayModes = ALL_ARRAY_MODES;
 
171
        } else {
 
172
            m_currentKnownStructure.clear();
 
173
            m_futurePossibleStructure.clear();
 
174
            m_arrayModes = 0;
 
175
        }
 
176
        m_type = type;
 
177
        m_value = JSValue();
 
178
        checkConsistency();
 
179
    }
 
180
    
 
181
    bool operator==(const AbstractValue& other) const
 
182
    {
 
183
        return m_type == other.m_type
 
184
            && m_arrayModes == other.m_arrayModes
 
185
            && m_currentKnownStructure == other.m_currentKnownStructure
 
186
            && m_futurePossibleStructure == other.m_futurePossibleStructure
 
187
            && m_value == other.m_value;
 
188
    }
 
189
    bool operator!=(const AbstractValue& other) const
 
190
    {
 
191
        return !(*this == other);
 
192
    }
 
193
    
 
194
    bool merge(const AbstractValue& other)
 
195
    {
 
196
#if !ASSERT_DISABLED
 
197
        AbstractValue oldMe = *this;
 
198
#endif
 
199
        bool result = false;
 
200
        if (isClear()) {
 
201
            *this = other;
 
202
            result = !other.isClear();
 
203
        } else {
 
204
            result |= mergeSpeculation(m_type, other.m_type);
 
205
            result |= mergeArrayModes(m_arrayModes, other.m_arrayModes);
 
206
            result |= m_currentKnownStructure.addAll(other.m_currentKnownStructure);
 
207
            result |= m_futurePossibleStructure.addAll(other.m_futurePossibleStructure);
 
208
            if (m_value != other.m_value) {
 
209
                result |= !!m_value;
 
210
                m_value = JSValue();
 
211
            }
 
212
        }
 
213
        checkConsistency();
 
214
        ASSERT(result == (*this != oldMe));
 
215
        return result;
 
216
    }
 
217
    
 
218
    void merge(SpeculatedType type)
 
219
    {
 
220
        mergeSpeculation(m_type, type);
 
221
        
 
222
        if (type & SpecCell) {
 
223
            m_currentKnownStructure.makeTop();
 
224
            m_futurePossibleStructure.makeTop();
 
225
            m_arrayModes = ALL_ARRAY_MODES;
 
226
        }
 
227
        m_value = JSValue();
 
228
 
 
229
        checkConsistency();
 
230
    }
 
231
    
 
232
    void filter(const StructureSet& other)
 
233
    {
 
234
        m_type &= other.speculationFromStructures();
 
235
        m_arrayModes &= other.arrayModesFromStructures();
 
236
        m_currentKnownStructure.filter(other);
 
237
        if (m_currentKnownStructure.isClear())
 
238
            m_futurePossibleStructure.clear();
 
239
        else if (m_currentKnownStructure.hasSingleton())
 
240
            filterFuturePossibleStructure(m_currentKnownStructure.singleton());
 
241
        
 
242
        // It's possible that prior to the above two statements we had (Foo, TOP), where
 
243
        // Foo is a SpeculatedType that is disjoint with the passed StructureSet. In that
 
244
        // case, we will now have (None, [someStructure]). In general, we need to make
 
245
        // sure that new information gleaned from the SpeculatedType needs to be fed back
 
246
        // into the information gleaned from the StructureSet.
 
247
        m_currentKnownStructure.filter(m_type);
 
248
        m_futurePossibleStructure.filter(m_type);
 
249
        
 
250
        filterArrayModesByType();
 
251
        filterValueByType();
 
252
        
 
253
        checkConsistency();
 
254
    }
 
255
    
 
256
    void filterArrayModes(ArrayModes arrayModes)
 
257
    {
 
258
        ASSERT(arrayModes);
 
259
        
 
260
        m_type &= SpecCell;
 
261
        m_arrayModes &= arrayModes;
 
262
        
 
263
        // I could do more fancy filtering here. But it probably won't make any difference.
 
264
        
 
265
        checkConsistency();
 
266
    }
 
267
    
 
268
    void filter(SpeculatedType type)
 
269
    {
 
270
        if (type == SpecTop)
 
271
            return;
 
272
        m_type &= type;
 
273
        
 
274
        // It's possible that prior to this filter() call we had, say, (Final, TOP), and
 
275
        // the passed type is Array. At this point we'll have (None, TOP). The best way
 
276
        // to ensure that the structure filtering does the right thing is to filter on
 
277
        // the new type (None) rather than the one passed (Array).
 
278
        m_currentKnownStructure.filter(m_type);
 
279
        m_futurePossibleStructure.filter(m_type);
 
280
        
 
281
        filterArrayModesByType();
 
282
        filterValueByType();
 
283
        
 
284
        checkConsistency();
 
285
    }
 
286
    
 
287
    bool filterByValue(JSValue value)
 
288
    {
 
289
        if (!validate(value))
 
290
            return false;
 
291
        
 
292
        if (!!value && value.isCell())
 
293
            filter(StructureSet(value.asCell()->structure()));
 
294
        else
 
295
            filter(speculationFromValue(value));
 
296
        
 
297
        m_value = value;
 
298
        
 
299
        return true;
 
300
    }
 
301
    
 
302
    bool validateType(JSValue value) const
 
303
    {
 
304
        if (isTop())
 
305
            return true;
 
306
        
 
307
        if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
 
308
            return false;
 
309
        
 
310
        if (value.isEmpty()) {
 
311
            ASSERT(m_type & SpecEmpty);
 
312
            return true;
 
313
        }
 
314
        
 
315
        return true;
 
316
    }
 
317
    
 
318
    bool validate(JSValue value) const
 
319
    {
 
320
        if (isTop())
 
321
            return true;
 
322
        
 
323
        if (!!m_value && m_value != value)
 
324
            return false;
 
325
        
 
326
        if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
 
327
            return false;
 
328
        
 
329
        if (value.isEmpty()) {
 
330
            ASSERT(m_type & SpecEmpty);
 
331
            return true;
 
332
        }
 
333
        
 
334
        if (!!value && value.isCell()) {
 
335
            ASSERT(m_type & SpecCell);
 
336
            Structure* structure = value.asCell()->structure();
 
337
            return m_currentKnownStructure.contains(structure)
 
338
                && m_futurePossibleStructure.contains(structure)
 
339
                && (m_arrayModes & asArrayModes(structure->indexingType()));
 
340
        }
 
341
        
 
342
        return true;
 
343
    }
 
344
    
 
345
    Structure* bestProvenStructure() const
 
346
    {
 
347
        if (m_currentKnownStructure.hasSingleton())
 
348
            return m_currentKnownStructure.singleton();
 
349
        if (m_futurePossibleStructure.hasSingleton())
 
350
            return m_futurePossibleStructure.singleton();
 
351
        return 0;
 
352
    }
 
353
    
 
354
    void checkConsistency() const
 
355
    {
 
356
        if (!(m_type & SpecCell)) {
 
357
            ASSERT(m_currentKnownStructure.isClear());
 
358
            ASSERT(m_futurePossibleStructure.isClear());
 
359
            ASSERT(!m_arrayModes);
 
360
        }
 
361
        
 
362
        if (isClear())
 
363
            ASSERT(!m_value);
 
364
        
 
365
        if (!!m_value)
 
366
            ASSERT(mergeSpeculations(m_type, speculationFromValue(m_value)) == m_type);
 
367
        
 
368
        // Note that it's possible for a prediction like (Final, []). This really means that
 
369
        // the value is bottom and that any code that uses the value is unreachable. But
 
370
        // we don't want to get pedantic about this as it would only increase the computational
 
371
        // complexity of the code.
 
372
    }
 
373
    
 
374
    void dump(PrintStream& out) const
 
375
    {
 
376
        out.print(
 
377
            "(", SpeculationDump(m_type), ", ", arrayModesToString(m_arrayModes), ", ",
 
378
            m_currentKnownStructure, ", ", m_futurePossibleStructure);
 
379
        if (!!m_value)
 
380
            out.print(", ", m_value.description());
 
381
        out.print(")");
 
382
    }
 
383
    
 
384
    // A great way to think about the difference between m_currentKnownStructure and
 
385
    // m_futurePossibleStructure is to consider these four examples:
 
386
    //
 
387
    // 1) x = foo();
 
388
    //
 
389
    //    In this case x's m_currentKnownStructure and m_futurePossibleStructure will
 
390
    //    both be TOP, since we don't know anything about x for sure, yet.
 
391
    //
 
392
    // 2) x = foo();
 
393
    //    y = x.f;
 
394
    //
 
395
    //    Where x will later have a new property added to it, 'g'. Because of the
 
396
    //    known but not-yet-executed property addition, x's currently structure will
 
397
    //    not be watchpointable; hence we have no way of statically bounding the set
 
398
    //    of possible structures that x may have if a clobbering event happens. So,
 
399
    //    x's m_currentKnownStructure will be whatever structure we check to get
 
400
    //    property 'f', and m_futurePossibleStructure will be TOP.
 
401
    //
 
402
    // 3) x = foo();
 
403
    //    y = x.f;
 
404
    //
 
405
    //    Where x has a terminal structure that is still watchpointable. In this case,
 
406
    //    x's m_currentKnownStructure and m_futurePossibleStructure will both be
 
407
    //    whatever structure we checked for when getting 'f'.
 
408
    //
 
409
    // 4) x = foo();
 
410
    //    y = x.f;
 
411
    //    bar();
 
412
    //
 
413
    //    Where x has a terminal structure that is still watchpointable. In this
 
414
    //    case, m_currentKnownStructure will be TOP because bar() may potentially
 
415
    //    change x's structure and we have no way of proving otherwise, but
 
416
    //    x's m_futurePossibleStructure will be whatever structure we had checked
 
417
    //    when getting property 'f'.
 
418
 
 
419
    // This is a proven constraint on the structures that this value can have right
 
420
    // now. The structure of the current value must belong to this set. The set may
 
421
    // be TOP, indicating that it is the set of all possible structures, in which
 
422
    // case the current value can have any structure. The set may be BOTTOM (empty)
 
423
    // in which case this value cannot be a cell. This is all subject to change
 
424
    // anytime a new value is assigned to this one, anytime there is a control flow
 
425
    // merge, or most crucially, anytime a side-effect or structure check happens.
 
426
    // In case of a side-effect, we typically must assume that any value may have
 
427
    // had its structure changed, hence contravening our proof. We make the proof
 
428
    // valid again by switching this to TOP (i.e. claiming that we have proved that
 
429
    // this value may have any structure). Of note is that the proof represented by
 
430
    // this field is not subject to structure transition watchpoints - even if one
 
431
    // fires, we can be sure that this proof is still valid.
 
432
    StructureAbstractValue m_currentKnownStructure;
 
433
    
 
434
    // This is a proven constraint on the structures that this value can have now
 
435
    // or any time in the future subject to the structure transition watchpoints of
 
436
    // all members of this set not having fired. This set is impervious to side-
 
437
    // effects; even if one happens the side-effect can only cause the value to
 
438
    // change to at worst another structure that is also a member of this set. But,
 
439
    // the theorem being proved by this field is predicated upon there not being
 
440
    // any new structure transitions introduced into any members of this set. In
 
441
    // cases where there is no way for us to guard this happening, the set must be
 
442
    // TOP. But in cases where we can guard new structure transitions (all members
 
443
    // of the set have still-valid structure transition watchpoints) then this set
 
444
    // will be finite. Anytime that we make use of the finite nature of this set,
 
445
    // we must first issue a structure transition watchpoint, which will effectively
 
446
    // result in m_currentKnownStructure being filtered according to
 
447
    // m_futurePossibleStructure.
 
448
    StructureAbstractValue m_futurePossibleStructure;
 
449
    
 
450
    // This is a proven constraint on the possible types that this value can have
 
451
    // now or any time in the future, unless it is reassigned. This field is
 
452
    // impervious to side-effects unless the side-effect can reassign the value
 
453
    // (for example if we're talking about a captured variable). The relationship
 
454
    // between this field, and the structure fields above, is as follows. The
 
455
    // fields above constraint the structures that a cell may have, but they say
 
456
    // nothing about whether or not the value is known to be a cell. More formally,
 
457
    // the m_currentKnownStructure is itself an abstract value that consists of the
 
458
    // union of the set of all non-cell values and the set of cell values that have
 
459
    // the given structure. This abstract value is then the intersection of the
 
460
    // m_currentKnownStructure and the set of values whose type is m_type. So, for
 
461
    // example if m_type is SpecFinal|SpecInt32 and m_currentKnownStructure is
 
462
    // [0x12345] then this abstract value corresponds to the set of all integers
 
463
    // unified with the set of all objects with structure 0x12345.
 
464
    SpeculatedType m_type;
 
465
    
 
466
    // This is a proven constraint on the possible indexing types that this value
 
467
    // can have right now. It also implicitly constraints the set of structures
 
468
    // that the value may have right now, since a structure has an immutable
 
469
    // indexing type. This is subject to change upon reassignment, or any side
 
470
    // effect that makes non-obvious changes to the heap.
 
471
    ArrayModes m_arrayModes;
 
472
    
 
473
    // This is a proven constraint on the possible values that this value can
 
474
    // have now or any time in the future, unless it is reassigned. Note that this
 
475
    // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value)
 
476
    // means either BOTTOM or TOP depending on the state of m_type: if m_type is
 
477
    // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue()
 
478
    // means TOP.
 
479
    JSValue m_value;
 
480
 
 
481
private:
 
482
    void clobberArrayModes()
 
483
    {
 
484
        // FIXME: We could make this try to predict the set of array modes that this object
 
485
        // could have in the future. For now, just do the simple thing.
 
486
        m_arrayModes = ALL_ARRAY_MODES;
 
487
    }
 
488
    
 
489
    void setFuturePossibleStructure(Structure* structure)
 
490
    {
 
491
        if (structure->transitionWatchpointSetIsStillValid())
 
492
            m_futurePossibleStructure = structure;
 
493
        else
 
494
            m_futurePossibleStructure.makeTop();
 
495
    }
 
496
    
 
497
    void filterFuturePossibleStructure(Structure* structure)
 
498
    {
 
499
        if (structure->transitionWatchpointSetIsStillValid())
 
500
            m_futurePossibleStructure.filter(StructureAbstractValue(structure));
 
501
    }
 
502
 
 
503
    // We could go further, and ensure that if the futurePossibleStructure contravenes
 
504
    // the value, then we could clear both of those things. But that's unlikely to help
 
505
    // in any realistic scenario, so we don't do it. Simpler is better.
 
506
    void filterValueByType()
 
507
    {
 
508
        if (!!m_type) {
 
509
            // The type is still non-empty. This implies that regardless of what filtering
 
510
            // was done, we either didn't have a value to begin with, or that value is still
 
511
            // valid.
 
512
            ASSERT(!m_value || validateType(m_value));
 
513
            return;
 
514
        }
 
515
        
 
516
        // The type has been rendered empty. That means that the value must now be invalid,
 
517
        // as well.
 
518
        ASSERT(!m_value || !validateType(m_value));
 
519
        m_value = JSValue();
 
520
    }
 
521
    
 
522
    void filterArrayModesByType()
 
523
    {
 
524
        if (!(m_type & SpecCell))
 
525
            m_arrayModes = 0;
 
526
        else if (!(m_type & ~SpecArray))
 
527
            m_arrayModes &= ALL_ARRAY_ARRAY_MODES;
 
528
        else if (!(m_type & SpecArray))
 
529
            m_arrayModes &= ALL_NON_ARRAY_ARRAY_MODES;
 
530
    }
 
531
};
 
532
 
 
533
} } // namespace JSC::DFG
 
534
 
 
535
#endif // ENABLE(DFG_JIT)
 
536
 
 
537
#endif // DFGAbstractValue_h
 
538
 
 
539