1/*
2 * Copyright (C) 2011, 2012, 2013 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#include "config.h"
27#include "DFGAbstractState.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "CodeBlock.h"
32#include "DFGBasicBlock.h"
33#include "GetByIdStatus.h"
34#include "Operations.h"
35#include "PutByIdStatus.h"
36#include "StringObject.h"
37
38namespace JSC { namespace DFG {
39
40AbstractState::AbstractState(Graph& graph)
41    : m_codeBlock(graph.m_codeBlock)
42    , m_graph(graph)
43    , m_variables(m_codeBlock->numParameters(), graph.m_localVars)
44    , m_block(0)
45{
46}
47
48AbstractState::~AbstractState() { }
49
50void AbstractState::beginBasicBlock(BasicBlock* basicBlock)
51{
52    ASSERT(!m_block);
53
54    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
55    ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
56    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
57
58    for (size_t i = 0; i < basicBlock->size(); i++)
59        forNode(basicBlock->at(i)).clear();
60
61    m_variables = basicBlock->valuesAtHead;
62    m_haveStructures = false;
63    for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
64        if (m_variables.argument(i).m_currentKnownStructure.isNeitherClearNorTop()) {
65            m_haveStructures = true;
66            break;
67        }
68    }
69    for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
70        if (m_variables.local(i).m_currentKnownStructure.isNeitherClearNorTop()) {
71            m_haveStructures = true;
72            break;
73        }
74    }
75
76    basicBlock->cfaShouldRevisit = false;
77    basicBlock->cfaHasVisited = true;
78    m_block = basicBlock;
79    m_isValid = true;
80    m_foundConstants = false;
81    m_branchDirection = InvalidBranchDirection;
82}
83
84void AbstractState::initialize(Graph& graph)
85{
86    BasicBlock* root = graph.m_blocks[0].get();
87    root->cfaShouldRevisit = true;
88    root->cfaHasVisited = false;
89    root->cfaFoundConstants = false;
90    for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
91        Node* node = root->variablesAtHead.argument(i);
92        ASSERT(node->op() == SetArgument);
93        if (!node->variableAccessData()->shouldUnboxIfPossible()) {
94            root->valuesAtHead.argument(i).makeTop();
95            continue;
96        }
97
98        SpeculatedType prediction = node->variableAccessData()->prediction();
99        if (isInt32Speculation(prediction))
100            root->valuesAtHead.argument(i).set(SpecInt32);
101        else if (isBooleanSpeculation(prediction))
102            root->valuesAtHead.argument(i).set(SpecBoolean);
103        else if (isCellSpeculation(prediction))
104            root->valuesAtHead.argument(i).set(SpecCell);
105        else
106            root->valuesAtHead.argument(i).makeTop();
107
108        root->valuesAtTail.argument(i).clear();
109    }
110    for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
111        Node* node = root->variablesAtHead.local(i);
112        if (node && node->variableAccessData()->isCaptured())
113            root->valuesAtHead.local(i).makeTop();
114        else
115            root->valuesAtHead.local(i).clear();
116        root->valuesAtTail.local(i).clear();
117    }
118    for (BlockIndex blockIndex = 1 ; blockIndex < graph.m_blocks.size(); ++blockIndex) {
119        BasicBlock* block = graph.m_blocks[blockIndex].get();
120        if (!block)
121            continue;
122        if (!block->isReachable)
123            continue;
124        block->cfaShouldRevisit = false;
125        block->cfaHasVisited = false;
126        block->cfaFoundConstants = false;
127        for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
128            block->valuesAtHead.argument(i).clear();
129            block->valuesAtTail.argument(i).clear();
130        }
131        for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
132            block->valuesAtHead.local(i).clear();
133            block->valuesAtTail.local(i).clear();
134        }
135        if (!block->isOSRTarget)
136            continue;
137        if (block->bytecodeBegin != graph.m_osrEntryBytecodeIndex)
138            continue;
139        for (size_t i = 0; i < graph.m_mustHandleValues.size(); ++i) {
140            AbstractValue value;
141            value.setMostSpecific(graph.m_mustHandleValues[i]);
142            int operand = graph.m_mustHandleValues.operandForIndex(i);
143            block->valuesAtHead.operand(operand).merge(value);
144#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
145            dataLogF("    Initializing Block #%u, operand r%d, to ", blockIndex, operand);
146            block->valuesAtHead.operand(operand).dump(WTF::dataFile());
147            dataLogF("\n");
148#endif
149        }
150        block->cfaShouldRevisit = true;
151    }
152}
153
154bool AbstractState::endBasicBlock(MergeMode mergeMode)
155{
156    ASSERT(m_block);
157
158    BasicBlock* block = m_block; // Save the block for successor merging.
159
160    block->cfaFoundConstants = m_foundConstants;
161    block->cfaDidFinish = m_isValid;
162    block->cfaBranchDirection = m_branchDirection;
163
164    if (!m_isValid) {
165        reset();
166        return false;
167    }
168
169    bool changed = false;
170
171    if (mergeMode != DontMerge || !ASSERT_DISABLED) {
172        for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
173#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
174            dataLogF("        Merging state for argument %zu.\n", argument);
175#endif
176            AbstractValue& destination = block->valuesAtTail.argument(argument);
177            changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
178        }
179
180        for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
181#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
182            dataLogF("        Merging state for local %zu.\n", local);
183#endif
184            AbstractValue& destination = block->valuesAtTail.local(local);
185            changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
186        }
187    }
188
189    ASSERT(mergeMode != DontMerge || !changed);
190
191#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
192    dataLogF("        Branch direction = %s\n", branchDirectionToString(m_branchDirection));
193#endif
194
195    reset();
196
197    if (mergeMode != MergeToSuccessors)
198        return changed;
199
200    return mergeToSuccessors(m_graph, block);
201}
202
203void AbstractState::reset()
204{
205    m_block = 0;
206    m_isValid = false;
207    m_branchDirection = InvalidBranchDirection;
208}
209
210AbstractState::BooleanResult AbstractState::booleanResult(Node* node, AbstractValue& value)
211{
212    JSValue childConst = value.value();
213    if (childConst) {
214        if (childConst.toBoolean(m_codeBlock->globalObjectFor(node->codeOrigin)->globalExec()))
215            return DefinitelyTrue;
216        return DefinitelyFalse;
217    }
218
219    // Next check if we can fold because we know that the source is an object or string and does not equal undefined.
220    if (isCellSpeculation(value.m_type)
221        && value.m_currentKnownStructure.hasSingleton()) {
222        Structure* structure = value.m_currentKnownStructure.singleton();
223        if (!structure->masqueradesAsUndefined(m_codeBlock->globalObjectFor(node->codeOrigin))
224            && structure->typeInfo().type() != StringType)
225            return DefinitelyTrue;
226    }
227
228    return UnknownBooleanResult;
229}
230
231bool AbstractState::startExecuting(Node* node)
232{
233    ASSERT(m_block);
234    ASSERT(m_isValid);
235
236    m_didClobber = false;
237
238    node->setCanExit(false);
239
240    if (!node->shouldGenerate())
241        return false;
242
243    return true;
244}
245
246bool AbstractState::startExecuting(unsigned indexInBlock)
247{
248    return startExecuting(m_block->at(indexInBlock));
249}
250
251void AbstractState::executeEdges(Node* node)
252{
253    DFG_NODE_DO_TO_CHILDREN(m_graph, node, filterEdgeByUse);
254}
255
256void AbstractState::executeEdges(unsigned indexInBlock)
257{
258    executeEdges(m_block->at(indexInBlock));
259}
260
261void AbstractState::verifyEdge(Node*, Edge edge)
262{
263    RELEASE_ASSERT(!(forNode(edge).m_type & ~typeFilterFor(edge.useKind())));
264}
265
266void AbstractState::verifyEdges(Node* node)
267{
268    DFG_NODE_DO_TO_CHILDREN(m_graph, node, verifyEdge);
269}
270
271bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
272{
273    if (!ASSERT_DISABLED)
274        verifyEdges(node);
275
276    switch (node->op()) {
277    case JSConstant:
278    case WeakJSConstant:
279    case PhantomArguments: {
280        forNode(node).set(m_graph.valueOfJSConstant(node));
281        break;
282    }
283
284    case Identity: {
285        forNode(node) = forNode(node->child1());
286        break;
287    }
288
289    case GetLocal: {
290        VariableAccessData* variableAccessData = node->variableAccessData();
291        if (variableAccessData->prediction() == SpecNone) {
292            m_isValid = false;
293            break;
294        }
295        AbstractValue value = m_variables.operand(variableAccessData->local());
296        if (!variableAccessData->isCaptured()) {
297            if (value.isClear())
298                node->setCanExit(true);
299        }
300        if (value.value())
301            m_foundConstants = true;
302        forNode(node) = value;
303        break;
304    }
305
306    case GetLocalUnlinked: {
307        AbstractValue value = m_variables.operand(node->unlinkedLocal());
308        if (value.value())
309            m_foundConstants = true;
310        forNode(node) = value;
311        break;
312    }
313
314    case SetLocal: {
315        m_variables.operand(node->local()) = forNode(node->child1());
316        break;
317    }
318
319    case MovHintAndCheck: {
320        // Don't need to do anything. A MovHint is effectively a promise that the SetLocal
321        // was dead.
322        break;
323    }
324
325    case MovHint:
326    case ZombieHint: {
327        RELEASE_ASSERT_NOT_REACHED();
328        break;
329    }
330
331    case SetArgument:
332        // Assert that the state of arguments has been set.
333        ASSERT(!m_block->valuesAtHead.operand(node->local()).isClear());
334        break;
335
336    case BitAnd:
337    case BitOr:
338    case BitXor:
339    case BitRShift:
340    case BitLShift:
341    case BitURShift: {
342        JSValue left = forNode(node->child1()).value();
343        JSValue right = forNode(node->child2()).value();
344        if (left && right && left.isInt32() && right.isInt32()) {
345            int32_t a = left.asInt32();
346            int32_t b = right.asInt32();
347            bool constantWasSet;
348            switch (node->op()) {
349            case BitAnd:
350                constantWasSet = trySetConstant(node, JSValue(a & b));
351                break;
352            case BitOr:
353                constantWasSet = trySetConstant(node, JSValue(a | b));
354                break;
355            case BitXor:
356                constantWasSet = trySetConstant(node, JSValue(a ^ b));
357                break;
358            case BitRShift:
359                constantWasSet = trySetConstant(node, JSValue(a >> static_cast<uint32_t>(b)));
360                break;
361            case BitLShift:
362                constantWasSet = trySetConstant(node, JSValue(a << static_cast<uint32_t>(b)));
363                break;
364            case BitURShift:
365                constantWasSet = trySetConstant(node, JSValue(static_cast<uint32_t>(a) >> static_cast<uint32_t>(b)));
366                break;
367            default:
368                RELEASE_ASSERT_NOT_REACHED();
369                constantWasSet = false;
370            }
371            if (constantWasSet) {
372                m_foundConstants = true;
373                break;
374            }
375        }
376        forNode(node).set(SpecInt32);
377        break;
378    }
379
380    case UInt32ToNumber: {
381        JSValue child = forNode(node->child1()).value();
382        if (child && child.isNumber()) {
383            ASSERT(child.isInt32());
384            if (trySetConstant(node, JSValue(child.asUInt32()))) {
385                m_foundConstants = true;
386                break;
387            }
388        }
389        if (!node->canSpeculateInteger())
390            forNode(node).set(SpecDouble);
391        else {
392            forNode(node).set(SpecInt32);
393            node->setCanExit(true);
394        }
395        break;
396    }
397
398    case DoubleAsInt32: {
399        JSValue child = forNode(node->child1()).value();
400        if (child && child.isNumber()) {
401            double asDouble = child.asNumber();
402            int32_t asInt = JSC::toInt32(asDouble);
403            if (bitwise_cast<int64_t>(static_cast<double>(asInt)) == bitwise_cast<int64_t>(asDouble)
404                && trySetConstant(node, JSValue(asInt))) {
405                m_foundConstants = true;
406                break;
407            }
408        }
409        node->setCanExit(true);
410        forNode(node).set(SpecInt32);
411        break;
412    }
413
414    case ValueToInt32: {
415        JSValue child = forNode(node->child1()).value();
416        if (child && child.isNumber()) {
417            bool constantWasSet;
418            if (child.isInt32())
419                constantWasSet = trySetConstant(node, child);
420            else
421                constantWasSet = trySetConstant(node, JSValue(JSC::toInt32(child.asDouble())));
422            if (constantWasSet) {
423                m_foundConstants = true;
424                break;
425            }
426        }
427
428        forNode(node).set(SpecInt32);
429        break;
430    }
431
432    case Int32ToDouble:
433    case ForwardInt32ToDouble: {
434        JSValue child = forNode(node->child1()).value();
435        if (child && child.isNumber()
436            && trySetConstant(node, JSValue(JSValue::EncodeAsDouble, child.asNumber()))) {
437            m_foundConstants = true;
438            break;
439        }
440        if (isInt32Speculation(forNode(node->child1()).m_type))
441            forNode(node).set(SpecDoubleReal);
442        else
443            forNode(node).set(SpecDouble);
444        break;
445    }
446
447    case ValueAdd:
448    case ArithAdd: {
449        JSValue left = forNode(node->child1()).value();
450        JSValue right = forNode(node->child2()).value();
451        if (left && right && left.isNumber() && right.isNumber()
452            && trySetConstant(node, JSValue(left.asNumber() + right.asNumber()))) {
453            m_foundConstants = true;
454            break;
455        }
456        switch (node->binaryUseKind()) {
457        case Int32Use:
458            forNode(node).set(SpecInt32);
459            if (!nodeCanTruncateInteger(node->arithNodeFlags()))
460                node->setCanExit(true);
461            break;
462        case NumberUse:
463            if (isRealNumberSpeculation(forNode(node->child1()).m_type)
464                && isRealNumberSpeculation(forNode(node->child2()).m_type))
465                forNode(node).set(SpecDoubleReal);
466            else
467                forNode(node).set(SpecDouble);
468            break;
469        default:
470            RELEASE_ASSERT(node->op() == ValueAdd);
471            clobberWorld(node->codeOrigin, indexInBlock);
472            forNode(node).set(SpecString | SpecInt32 | SpecNumber);
473            break;
474        }
475        break;
476    }
477
478    case MakeRope: {
479        node->setCanExit(true);
480        forNode(node).set(m_graph.m_vm.stringStructure.get());
481        break;
482    }
483
484    case ArithSub: {
485        JSValue left = forNode(node->child1()).value();
486        JSValue right = forNode(node->child2()).value();
487        if (left && right && left.isNumber() && right.isNumber()
488            && trySetConstant(node, JSValue(left.asNumber() - right.asNumber()))) {
489            m_foundConstants = true;
490            break;
491        }
492        switch (node->binaryUseKind()) {
493        case Int32Use:
494            forNode(node).set(SpecInt32);
495            if (!nodeCanTruncateInteger(node->arithNodeFlags()))
496                node->setCanExit(true);
497            break;
498        case NumberUse:
499            forNode(node).set(SpecDouble);
500            break;
501        default:
502            RELEASE_ASSERT_NOT_REACHED();
503            break;
504        }
505        break;
506    }
507
508    case ArithNegate: {
509        JSValue child = forNode(node->child1()).value();
510        if (child && child.isNumber()
511            && trySetConstant(node, JSValue(-child.asNumber()))) {
512            m_foundConstants = true;
513            break;
514        }
515        switch (node->child1().useKind()) {
516        case Int32Use:
517            forNode(node).set(SpecInt32);
518            if (!nodeCanTruncateInteger(node->arithNodeFlags()))
519                node->setCanExit(true);
520            break;
521        case NumberUse:
522            forNode(node).set(SpecDouble);
523            break;
524        default:
525            RELEASE_ASSERT_NOT_REACHED();
526            break;
527        }
528        break;
529    }
530
531    case ArithMul: {
532        JSValue left = forNode(node->child1()).value();
533        JSValue right = forNode(node->child2()).value();
534        if (left && right && left.isNumber() && right.isNumber()
535            && trySetConstant(node, JSValue(left.asNumber() * right.asNumber()))) {
536            m_foundConstants = true;
537            break;
538        }
539        switch (node->binaryUseKind()) {
540        case Int32Use:
541            forNode(node).set(SpecInt32);
542            if (!nodeCanTruncateInteger(node->arithNodeFlags())
543                || !nodeCanIgnoreNegativeZero(node->arithNodeFlags()))
544                node->setCanExit(true);
545            break;
546        case NumberUse:
547            if (isRealNumberSpeculation(forNode(node->child1()).m_type)
548                || isRealNumberSpeculation(forNode(node->child2()).m_type))
549                forNode(node).set(SpecDoubleReal);
550            else
551                forNode(node).set(SpecDouble);
552            break;
553        default:
554            RELEASE_ASSERT_NOT_REACHED();
555            break;
556        }
557        break;
558    }
559
560    case ArithIMul: {
561        forNode(node).set(SpecInt32);
562        break;
563    }
564
565    case ArithDiv:
566    case ArithMin:
567    case ArithMax:
568    case ArithMod: {
569        JSValue left = forNode(node->child1()).value();
570        JSValue right = forNode(node->child2()).value();
571        if (left && right && left.isNumber() && right.isNumber()) {
572            double a = left.asNumber();
573            double b = right.asNumber();
574            bool constantWasSet;
575            switch (node->op()) {
576            case ArithDiv:
577                constantWasSet = trySetConstant(node, JSValue(a / b));
578                break;
579            case ArithMin:
580                constantWasSet = trySetConstant(node, JSValue(a < b ? a : (b <= a ? b : a + b)));
581                break;
582            case ArithMax:
583                constantWasSet = trySetConstant(node, JSValue(a > b ? a : (b >= a ? b : a + b)));
584                break;
585            case ArithMod:
586                constantWasSet = trySetConstant(node, JSValue(fmod(a, b)));
587                break;
588            default:
589                RELEASE_ASSERT_NOT_REACHED();
590                constantWasSet = false;
591                break;
592            }
593            if (constantWasSet) {
594                m_foundConstants = true;
595                break;
596            }
597        }
598        switch (node->binaryUseKind()) {
599        case Int32Use:
600            forNode(node).set(SpecInt32);
601            node->setCanExit(true);
602            break;
603        case NumberUse:
604            forNode(node).set(SpecDouble);
605            break;
606        default:
607            RELEASE_ASSERT_NOT_REACHED();
608            break;
609        }
610        break;
611    }
612
613    case ArithAbs: {
614        JSValue child = forNode(node->child1()).value();
615        if (child && child.isNumber()
616            && trySetConstant(node, JSValue(fabs(child.asNumber())))) {
617            m_foundConstants = true;
618            break;
619        }
620        switch (node->child1().useKind()) {
621        case Int32Use:
622            forNode(node).set(SpecInt32);
623            node->setCanExit(true);
624            break;
625        case NumberUse:
626            forNode(node).set(SpecDouble);
627            break;
628        default:
629            RELEASE_ASSERT_NOT_REACHED();
630            break;
631        }
632        break;
633    }
634
635    case ArithSqrt: {
636        JSValue child = forNode(node->child1()).value();
637        if (child && child.isNumber()
638            && trySetConstant(node, JSValue(sqrt(child.asNumber())))) {
639            m_foundConstants = true;
640            break;
641        }
642        forNode(node).set(SpecDouble);
643        break;
644    }
645
646    case LogicalNot: {
647        bool didSetConstant = false;
648        switch (booleanResult(node, forNode(node->child1()))) {
649        case DefinitelyTrue:
650            didSetConstant = trySetConstant(node, jsBoolean(false));
651            break;
652        case DefinitelyFalse:
653            didSetConstant = trySetConstant(node, jsBoolean(true));
654            break;
655        default:
656            break;
657        }
658        if (didSetConstant) {
659            m_foundConstants = true;
660            break;
661        }
662        switch (node->child1().useKind()) {
663        case BooleanUse:
664        case Int32Use:
665        case NumberUse:
666        case UntypedUse:
667            break;
668        case ObjectOrOtherUse:
669            node->setCanExit(true);
670            break;
671        default:
672            RELEASE_ASSERT_NOT_REACHED();
673            break;
674        }
675        forNode(node).set(SpecBoolean);
676        break;
677    }
678
679    case IsUndefined:
680    case IsBoolean:
681    case IsNumber:
682    case IsString:
683    case IsObject:
684    case IsFunction: {
685        node->setCanExit(node->op() == IsUndefined && m_codeBlock->globalObjectFor(node->codeOrigin)->masqueradesAsUndefinedWatchpoint()->isStillValid());
686        JSValue child = forNode(node->child1()).value();
687        if (child) {
688            bool constantWasSet;
689            switch (node->op()) {
690            case IsUndefined:
691                if (m_codeBlock->globalObjectFor(node->codeOrigin)->masqueradesAsUndefinedWatchpoint()->isStillValid()) {
692                    constantWasSet = trySetConstant(node, jsBoolean(
693                        child.isCell()
694                        ? false
695                        : child.isUndefined()));
696                } else {
697                    constantWasSet = trySetConstant(node, jsBoolean(
698                        child.isCell()
699                        ? child.asCell()->structure()->masqueradesAsUndefined(m_codeBlock->globalObjectFor(node->codeOrigin))
700                        : child.isUndefined()));
701                }
702                break;
703            case IsBoolean:
704                constantWasSet = trySetConstant(node, jsBoolean(child.isBoolean()));
705                break;
706            case IsNumber:
707                constantWasSet = trySetConstant(node, jsBoolean(child.isNumber()));
708                break;
709            case IsString:
710                constantWasSet = trySetConstant(node, jsBoolean(isJSString(child)));
711                break;
712            case IsObject:
713                if (child.isNull() || !child.isObject()) {
714                    constantWasSet = trySetConstant(node, jsBoolean(child.isNull()));
715                    break;
716                }
717            default:
718                constantWasSet = false;
719                break;
720            }
721            if (constantWasSet) {
722                m_foundConstants = true;
723                break;
724            }
725        }
726
727        forNode(node).set(SpecBoolean);
728        break;
729    }
730
731    case TypeOf: {
732        VM* vm = m_codeBlock->vm();
733        JSValue child = forNode(node->child1()).value();
734        AbstractValue& abstractChild = forNode(node->child1());
735        if (child) {
736            JSValue typeString = jsTypeStringForValue(*vm, m_codeBlock->globalObjectFor(node->codeOrigin), child);
737            if (trySetConstant(node, typeString)) {
738                m_foundConstants = true;
739                break;
740            }
741        } else if (isNumberSpeculation(abstractChild.m_type)) {
742            if (trySetConstant(node, vm->smallStrings.numberString())) {
743                forNode(node->child1()).filter(SpecNumber);
744                m_foundConstants = true;
745                break;
746            }
747        } else if (isStringSpeculation(abstractChild.m_type)) {
748            if (trySetConstant(node, vm->smallStrings.stringString())) {
749                forNode(node->child1()).filter(SpecString);
750                m_foundConstants = true;
751                break;
752            }
753        } else if (isFinalObjectSpeculation(abstractChild.m_type) || isArraySpeculation(abstractChild.m_type) || isArgumentsSpeculation(abstractChild.m_type)) {
754            if (trySetConstant(node, vm->smallStrings.objectString())) {
755                forNode(node->child1()).filter(SpecFinalObject | SpecArray | SpecArguments);
756                m_foundConstants = true;
757                break;
758            }
759        } else if (isFunctionSpeculation(abstractChild.m_type)) {
760            if (trySetConstant(node, vm->smallStrings.functionString())) {
761                forNode(node->child1()).filter(SpecFunction);
762                m_foundConstants = true;
763                break;
764            }
765        } else if (isBooleanSpeculation(abstractChild.m_type)) {
766            if (trySetConstant(node, vm->smallStrings.booleanString())) {
767                forNode(node->child1()).filter(SpecBoolean);
768                m_foundConstants = true;
769                break;
770            }
771        }
772
773        switch (node->child1().useKind()) {
774        case StringUse:
775        case CellUse:
776            node->setCanExit(true);
777            break;
778        case UntypedUse:
779            break;
780        default:
781            RELEASE_ASSERT_NOT_REACHED();
782            break;
783        }
784        forNode(node).set(m_graph.m_vm.stringStructure.get());
785        break;
786    }
787
788    case CompareLess:
789    case CompareLessEq:
790    case CompareGreater:
791    case CompareGreaterEq:
792    case CompareEq:
793    case CompareEqConstant: {
794        bool constantWasSet = false;
795
796        JSValue leftConst = forNode(node->child1()).value();
797        JSValue rightConst = forNode(node->child2()).value();
798        if (leftConst && rightConst && leftConst.isNumber() && rightConst.isNumber()) {
799            double a = leftConst.asNumber();
800            double b = rightConst.asNumber();
801            switch (node->op()) {
802            case CompareLess:
803                constantWasSet = trySetConstant(node, jsBoolean(a < b));
804                break;
805            case CompareLessEq:
806                constantWasSet = trySetConstant(node, jsBoolean(a <= b));
807                break;
808            case CompareGreater:
809                constantWasSet = trySetConstant(node, jsBoolean(a > b));
810                break;
811            case CompareGreaterEq:
812                constantWasSet = trySetConstant(node, jsBoolean(a >= b));
813                break;
814            case CompareEq:
815                constantWasSet = trySetConstant(node, jsBoolean(a == b));
816                break;
817            default:
818                RELEASE_ASSERT_NOT_REACHED();
819                constantWasSet = false;
820                break;
821            }
822        }
823
824        if (!constantWasSet && (node->op() == CompareEqConstant || node->op() == CompareEq)) {
825            SpeculatedType leftType = forNode(node->child1()).m_type;
826            SpeculatedType rightType = forNode(node->child2()).m_type;
827            if ((isInt32Speculation(leftType) && isOtherSpeculation(rightType))
828                || (isOtherSpeculation(leftType) && isInt32Speculation(rightType)))
829                constantWasSet = trySetConstant(node, jsBoolean(false));
830        }
831
832        if (constantWasSet) {
833            m_foundConstants = true;
834            break;
835        }
836
837        forNode(node).set(SpecBoolean);
838
839        // This is overly conservative. But the only thing this prevents is store elimination,
840        // and how likely is it, really, that you'll have redundant stores across a comparison
841        // operation? Comparison operations are typically at the end of basic blocks, so
842        // unless we have global store elimination (super unlikely given how unprofitable that
843        // optimization is to begin with), you aren't going to be wanting to store eliminate
844        // across an equality op.
845        node->setCanExit(true);
846        break;
847    }
848
849    case CompareStrictEq:
850    case CompareStrictEqConstant: {
851        Node* leftNode = node->child1().node();
852        Node* rightNode = node->child2().node();
853        JSValue left = forNode(leftNode).value();
854        JSValue right = forNode(rightNode).value();
855        if (left && right && left.isNumber() && right.isNumber()
856            && trySetConstant(node, jsBoolean(left.asNumber() == right.asNumber()))) {
857            m_foundConstants = true;
858            break;
859        }
860        forNode(node).set(SpecBoolean);
861        node->setCanExit(true); // This is overly conservative.
862        break;
863    }
864
865    case StringCharCodeAt:
866        node->setCanExit(true);
867        forNode(node).set(SpecInt32);
868        break;
869
870    case StringFromCharCode:
871        forNode(node).set(SpecString);
872        break;
873
874    case StringCharAt:
875        node->setCanExit(true);
876        forNode(node).set(m_graph.m_vm.stringStructure.get());
877        break;
878
879    case GetByVal: {
880        node->setCanExit(true);
881        switch (node->arrayMode().type()) {
882        case Array::SelectUsingPredictions:
883        case Array::Unprofiled:
884        case Array::Undecided:
885            RELEASE_ASSERT_NOT_REACHED();
886            break;
887        case Array::ForceExit:
888            m_isValid = false;
889            break;
890        case Array::Generic:
891            clobberWorld(node->codeOrigin, indexInBlock);
892            forNode(node).makeTop();
893            break;
894        case Array::String:
895            forNode(node).set(m_graph.m_vm.stringStructure.get());
896            break;
897        case Array::Arguments:
898            forNode(node).makeTop();
899            break;
900        case Array::Int32:
901            if (node->arrayMode().isOutOfBounds()) {
902                clobberWorld(node->codeOrigin, indexInBlock);
903                forNode(node).makeTop();
904            } else
905                forNode(node).set(SpecInt32);
906            break;
907        case Array::Double:
908            if (node->arrayMode().isOutOfBounds()) {
909                clobberWorld(node->codeOrigin, indexInBlock);
910                forNode(node).makeTop();
911            } else if (node->arrayMode().isSaneChain())
912                forNode(node).set(SpecDouble);
913            else
914                forNode(node).set(SpecDoubleReal);
915            break;
916        case Array::Contiguous:
917        case Array::ArrayStorage:
918        case Array::SlowPutArrayStorage:
919            if (node->arrayMode().isOutOfBounds())
920                clobberWorld(node->codeOrigin, indexInBlock);
921            forNode(node).makeTop();
922            break;
923        case Array::Int8Array:
924            forNode(node).set(SpecInt32);
925            break;
926        case Array::Int16Array:
927            forNode(node).set(SpecInt32);
928            break;
929        case Array::Int32Array:
930            forNode(node).set(SpecInt32);
931            break;
932        case Array::Uint8Array:
933            forNode(node).set(SpecInt32);
934            break;
935        case Array::Uint8ClampedArray:
936            forNode(node).set(SpecInt32);
937            break;
938        case Array::Uint16Array:
939            forNode(node).set(SpecInt32);
940            break;
941        case Array::Uint32Array:
942            if (node->shouldSpeculateInteger())
943                forNode(node).set(SpecInt32);
944            else
945                forNode(node).set(SpecDouble);
946            break;
947        case Array::Float32Array:
948            forNode(node).set(SpecDouble);
949            break;
950        case Array::Float64Array:
951            forNode(node).set(SpecDouble);
952            break;
953        default:
954            RELEASE_ASSERT_NOT_REACHED();
955            break;
956        }
957        break;
958    }
959
960    case PutByVal:
961    case PutByValAlias: {
962        node->setCanExit(true);
963        switch (node->arrayMode().modeForPut().type()) {
964        case Array::ForceExit:
965            m_isValid = false;
966            break;
967        case Array::Generic:
968            clobberWorld(node->codeOrigin, indexInBlock);
969            break;
970        case Array::Int32:
971            if (node->arrayMode().isOutOfBounds())
972                clobberWorld(node->codeOrigin, indexInBlock);
973            break;
974        case Array::Double:
975            if (node->arrayMode().isOutOfBounds())
976                clobberWorld(node->codeOrigin, indexInBlock);
977            break;
978        case Array::Contiguous:
979        case Array::ArrayStorage:
980            if (node->arrayMode().isOutOfBounds())
981                clobberWorld(node->codeOrigin, indexInBlock);
982            break;
983        case Array::SlowPutArrayStorage:
984            if (node->arrayMode().mayStoreToHole())
985                clobberWorld(node->codeOrigin, indexInBlock);
986            break;
987        default:
988            break;
989        }
990        break;
991    }
992
993    case ArrayPush:
994        node->setCanExit(true);
995        clobberWorld(node->codeOrigin, indexInBlock);
996        forNode(node).set(SpecNumber);
997        break;
998
999    case ArrayPop:
1000        node->setCanExit(true);
1001        clobberWorld(node->codeOrigin, indexInBlock);
1002        forNode(node).makeTop();
1003        break;
1004
1005    case RegExpExec:
1006        forNode(node).makeTop();
1007        break;
1008
1009    case RegExpTest:
1010        forNode(node).set(SpecBoolean);
1011        break;
1012
1013    case Jump:
1014        break;
1015
1016    case Branch: {
1017        Node* child = node->child1().node();
1018        BooleanResult result = booleanResult(node, forNode(child));
1019        if (result == DefinitelyTrue) {
1020            m_branchDirection = TakeTrue;
1021            break;
1022        }
1023        if (result == DefinitelyFalse) {
1024            m_branchDirection = TakeFalse;
1025            break;
1026        }
1027        // FIXME: The above handles the trivial cases of sparse conditional
1028        // constant propagation, but we can do better:
1029        // We can specialize the source variable's value on each direction of
1030        // the branch.
1031        node->setCanExit(true); // This is overly conservative.
1032        m_branchDirection = TakeBoth;
1033        break;
1034    }
1035
1036    case Return:
1037        m_isValid = false;
1038        break;
1039
1040    case Throw:
1041    case ThrowReferenceError:
1042        m_isValid = false;
1043        node->setCanExit(true);
1044        break;
1045
1046    case ToPrimitive: {
1047        JSValue childConst = forNode(node->child1()).value();
1048        if (childConst && childConst.isNumber() && trySetConstant(node, childConst)) {
1049            m_foundConstants = true;
1050            break;
1051        }
1052
1053        ASSERT(node->child1().useKind() == UntypedUse);
1054
1055        AbstractValue& source = forNode(node->child1());
1056        AbstractValue& destination = forNode(node);
1057
1058        // NB. The more canonical way of writing this would have been:
1059        //
1060        // destination = source;
1061        // if (destination.m_type & !(SpecNumber | SpecString | SpecBoolean)) {
1062        //     destination.filter(SpecNumber | SpecString | SpecBoolean);
1063        //     AbstractValue string;
1064        //     string.set(vm->stringStructure);
1065        //     destination.merge(string);
1066        // }
1067        //
1068        // The reason why this would, in most other cases, have been better is that
1069        // then destination would preserve any non-SpeculatedType knowledge of source.
1070        // As it stands, the code below forgets any non-SpeculatedType knowledge that
1071        // source would have had. Fortunately, though, for things like strings and
1072        // numbers and booleans, we don't care about the non-SpeculatedType knowedge:
1073        // the structure won't tell us anything we don't already know, and neither
1074        // will ArrayModes. And if the source was a meaningful constant then we
1075        // would have handled that above. Unfortunately, this does mean that
1076        // ToPrimitive will currently forget string constants. But that's not a big
1077        // deal since we don't do any optimization on those currently.
1078
1079        clobberWorld(node->codeOrigin, indexInBlock);
1080
1081        SpeculatedType type = source.m_type;
1082        if (type & ~(SpecNumber | SpecString | SpecBoolean))
1083            type = (SpecTop & ~SpecCell) | SpecString;
1084
1085        destination.set(type);
1086        break;
1087    }
1088
1089    case ToString: {
1090        switch (node->child1().useKind()) {
1091        case StringObjectUse:
1092            // This also filters that the StringObject has the primordial StringObject
1093            // structure.
1094            forNode(node->child1()).filter(m_graph.globalObjectFor(node->codeOrigin)->stringObjectStructure());
1095            node->setCanExit(true); // We could be more precise but it's likely not worth it.
1096            break;
1097        case StringOrStringObjectUse:
1098            node->setCanExit(true); // We could be more precise but it's likely not worth it.
1099            break;
1100        case CellUse:
1101        case UntypedUse:
1102            clobberWorld(node->codeOrigin, indexInBlock);
1103            break;
1104        default:
1105            RELEASE_ASSERT_NOT_REACHED();
1106            break;
1107        }
1108        forNode(node).set(m_graph.m_vm.stringStructure.get());
1109        break;
1110    }
1111
1112    case NewStringObject: {
1113        ASSERT(node->structure()->classInfo() == &StringObject::s_info);
1114        forNode(node).set(node->structure());
1115        break;
1116    }
1117
1118    case NewArray:
1119        node->setCanExit(true);
1120        forNode(node).set(m_graph.globalObjectFor(node->codeOrigin)->arrayStructureForIndexingTypeDuringAllocation(node->indexingType()));
1121        m_haveStructures = true;
1122        break;
1123
1124    case NewArrayBuffer:
1125        node->setCanExit(true);
1126        forNode(node).set(m_graph.globalObjectFor(node->codeOrigin)->arrayStructureForIndexingTypeDuringAllocation(node->indexingType()));
1127        m_haveStructures = true;
1128        break;
1129
1130    case NewArrayWithSize:
1131        node->setCanExit(true);
1132        forNode(node).set(SpecArray);
1133        m_haveStructures = true;
1134        break;
1135
1136    case NewRegexp:
1137        forNode(node).set(m_graph.globalObjectFor(node->codeOrigin)->regExpStructure());
1138        m_haveStructures = true;
1139        break;
1140
1141    case ConvertThis: {
1142        AbstractValue& source = forNode(node->child1());
1143        AbstractValue& destination = forNode(node);
1144
1145        destination = source;
1146        destination.merge(SpecObjectOther);
1147        break;
1148    }
1149
1150    case CreateThis: {
1151        forNode(node).set(SpecFinalObject);
1152        break;
1153    }
1154
1155    case AllocationProfileWatchpoint:
1156        node->setCanExit(true);
1157        break;
1158
1159    case NewObject:
1160        forNode(node).set(node->structure());
1161        m_haveStructures = true;
1162        break;
1163
1164    case CreateActivation:
1165        forNode(node).set(m_codeBlock->globalObjectFor(node->codeOrigin)->activationStructure());
1166        m_haveStructures = true;
1167        break;
1168
1169    case CreateArguments:
1170        forNode(node).set(m_codeBlock->globalObjectFor(node->codeOrigin)->argumentsStructure());
1171        m_haveStructures = true;
1172        break;
1173
1174    case TearOffActivation:
1175    case TearOffArguments:
1176        // Does nothing that is user-visible.
1177        break;
1178
1179    case CheckArgumentsNotCreated:
1180        if (isEmptySpeculation(
1181                m_variables.operand(
1182                    m_graph.argumentsRegisterFor(node->codeOrigin)).m_type))
1183            m_foundConstants = true;
1184        else
1185            node->setCanExit(true);
1186        break;
1187
1188    case GetMyArgumentsLength:
1189        // We know that this executable does not escape its arguments, so we can optimize
1190        // the arguments a bit. Note that this is not sufficient to force constant folding
1191        // of GetMyArgumentsLength, because GetMyArgumentsLength is a clobbering operation.
1192        // We perform further optimizations on this later on.
1193        if (node->codeOrigin.inlineCallFrame)
1194            forNode(node).set(jsNumber(node->codeOrigin.inlineCallFrame->arguments.size() - 1));
1195        else
1196            forNode(node).set(SpecInt32);
1197        node->setCanExit(
1198            !isEmptySpeculation(
1199                m_variables.operand(
1200                    m_graph.argumentsRegisterFor(node->codeOrigin)).m_type));
1201        break;
1202
1203    case GetMyArgumentsLengthSafe:
1204        // This potentially clobbers all structures if the arguments object had a getter
1205        // installed on the length property.
1206        clobberWorld(node->codeOrigin, indexInBlock);
1207        // We currently make no guarantee about what this returns because it does not
1208        // speculate that the length property is actually a length.
1209        forNode(node).makeTop();
1210        break;
1211
1212    case GetMyArgumentByVal:
1213        node->setCanExit(true);
1214        // We know that this executable does not escape its arguments, so we can optimize
1215        // the arguments a bit. Note that this ends up being further optimized by the
1216        // ArgumentsSimplificationPhase.
1217        forNode(node).makeTop();
1218        break;
1219
1220    case GetMyArgumentByValSafe:
1221        node->setCanExit(true);
1222        // This potentially clobbers all structures if the property we're accessing has
1223        // a getter. We don't speculate against this.
1224        clobberWorld(node->codeOrigin, indexInBlock);
1225        // And the result is unknown.
1226        forNode(node).makeTop();
1227        break;
1228
1229    case NewFunction: {
1230        AbstractValue& value = forNode(node);
1231        value = forNode(node->child1());
1232
1233        if (!(value.m_type & SpecEmpty)) {
1234            m_foundConstants = true;
1235            break;
1236        }
1237
1238        value.set((value.m_type & ~SpecEmpty) | SpecFunction);
1239        break;
1240    }
1241
1242    case NewFunctionExpression:
1243    case NewFunctionNoCheck:
1244        forNode(node).set(m_codeBlock->globalObjectFor(node->codeOrigin)->functionStructure());
1245        break;
1246
1247    case GetCallee:
1248        forNode(node).set(SpecFunction);
1249        break;
1250
1251    case SetCallee:
1252    case SetMyScope:
1253        break;
1254
1255    case GetScope: // FIXME: We could get rid of these if we know that the JSFunction is a constant. https://bugs.webkit.org/show_bug.cgi?id=106202
1256    case GetMyScope:
1257    case SkipTopScope:
1258        forNode(node).set(SpecObjectOther);
1259        break;
1260
1261    case SkipScope: {
1262        JSValue child = forNode(node->child1()).value();
1263        if (child && trySetConstant(node, JSValue(jsCast<JSScope*>(child.asCell())->next()))) {
1264            m_foundConstants = true;
1265            break;
1266        }
1267        forNode(node).set(SpecObjectOther);
1268        break;
1269    }
1270
1271    case GetScopeRegisters:
1272        forNode(node).clear(); // The result is not a JS value.
1273        break;
1274
1275    case GetScopedVar:
1276        forNode(node).makeTop();
1277        break;
1278
1279    case PutScopedVar:
1280        clobberCapturedVars(node->codeOrigin);
1281        break;
1282
1283    case GetById:
1284    case GetByIdFlush:
1285        node->setCanExit(true);
1286        if (!node->prediction()) {
1287            m_isValid = false;
1288            break;
1289        }
1290        if (isCellSpeculation(node->child1()->prediction())) {
1291            if (Structure* structure = forNode(node->child1()).bestProvenStructure()) {
1292                GetByIdStatus status = GetByIdStatus::computeFor(
1293                    m_graph.m_vm, structure,
1294                    m_graph.m_codeBlock->identifier(node->identifierNumber()));
1295                if (status.isSimple()) {
1296                    // Assert things that we can't handle and that the computeFor() method
1297                    // above won't be able to return.
1298                    ASSERT(status.structureSet().size() == 1);
1299                    ASSERT(status.chain().isEmpty());
1300
1301                    if (status.specificValue())
1302                        forNode(node).set(status.specificValue());
1303                    else
1304                        forNode(node).makeTop();
1305                    forNode(node->child1()).filter(status.structureSet());
1306
1307                    m_foundConstants = true;
1308                    break;
1309                }
1310            }
1311        }
1312        clobberWorld(node->codeOrigin, indexInBlock);
1313        forNode(node).makeTop();
1314        break;
1315
1316    case GetArrayLength:
1317        node->setCanExit(true); // Lies, but it's true for the common case of JSArray, so it's good enough.
1318        forNode(node).set(SpecInt32);
1319        break;
1320
1321    case CheckExecutable: {
1322        // FIXME: We could track executables in AbstractValue, which would allow us to get rid of these checks
1323        // more thoroughly. https://bugs.webkit.org/show_bug.cgi?id=106200
1324        // FIXME: We could eliminate these entirely if we know the exact value that flows into this.
1325        // https://bugs.webkit.org/show_bug.cgi?id=106201
1326        node->setCanExit(true);
1327        break;
1328    }
1329
1330    case CheckStructure:
1331    case ForwardCheckStructure: {
1332        // FIXME: We should be able to propagate the structure sets of constants (i.e. prototypes).
1333        AbstractValue& value = forNode(node->child1());
1334        ASSERT(!(value.m_type & ~SpecCell)); // Edge filtering should have already ensured this.
1335        // If this structure check is attempting to prove knowledge already held in
1336        // the futurePossibleStructure set then the constant folding phase should
1337        // turn this into a watchpoint instead.
1338        StructureSet& set = node->structureSet();
1339        if (value.m_futurePossibleStructure.isSubsetOf(set)
1340            || value.m_currentKnownStructure.isSubsetOf(set))
1341            m_foundConstants = true;
1342        if (!value.m_currentKnownStructure.isSubsetOf(set))
1343            node->setCanExit(true);
1344        value.filter(set);
1345        m_haveStructures = true;
1346        break;
1347    }
1348
1349    case StructureTransitionWatchpoint:
1350    case ForwardStructureTransitionWatchpoint: {
1351        AbstractValue& value = forNode(node->child1());
1352
1353        // It's only valid to issue a structure transition watchpoint if we already
1354        // know that the watchpoint covers a superset of the structures known to
1355        // belong to the set of future structures that this value may have.
1356        // Currently, we only issue singleton watchpoints (that check one structure)
1357        // and our futurePossibleStructure set can only contain zero, one, or an
1358        // infinity of structures.
1359        ASSERT(value.m_futurePossibleStructure.isSubsetOf(StructureSet(node->structure())));
1360
1361        value.filter(node->structure());
1362        m_haveStructures = true;
1363        node->setCanExit(true);
1364        break;
1365    }
1366
1367    case PutStructure:
1368    case PhantomPutStructure:
1369        if (!forNode(node->child1()).m_currentKnownStructure.isClear()) {
1370            clobberStructures(indexInBlock);
1371            forNode(node->child1()).set(node->structureTransitionData().newStructure);
1372            m_haveStructures = true;
1373        }
1374        break;
1375    case GetButterfly:
1376    case AllocatePropertyStorage:
1377    case ReallocatePropertyStorage:
1378        forNode(node).clear(); // The result is not a JS value.
1379        break;
1380    case CheckArray: {
1381        if (node->arrayMode().alreadyChecked(m_graph, node, forNode(node->child1()))) {
1382            m_foundConstants = true;
1383            break;
1384        }
1385        node->setCanExit(true); // Lies, but this is followed by operations (like GetByVal) that always exit, so there is no point in us trying to be clever here.
1386        switch (node->arrayMode().type()) {
1387        case Array::String:
1388            forNode(node->child1()).filter(SpecString);
1389            break;
1390        case Array::Int32:
1391        case Array::Double:
1392        case Array::Contiguous:
1393        case Array::ArrayStorage:
1394        case Array::SlowPutArrayStorage:
1395            break;
1396        case Array::Arguments:
1397            forNode(node->child1()).filter(SpecArguments);
1398            break;
1399        case Array::Int8Array:
1400            forNode(node->child1()).filter(SpecInt8Array);
1401            break;
1402        case Array::Int16Array:
1403            forNode(node->child1()).filter(SpecInt16Array);
1404            break;
1405        case Array::Int32Array:
1406            forNode(node->child1()).filter(SpecInt32Array);
1407            break;
1408        case Array::Uint8Array:
1409            forNode(node->child1()).filter(SpecUint8Array);
1410            break;
1411        case Array::Uint8ClampedArray:
1412            forNode(node->child1()).filter(SpecUint8ClampedArray);
1413            break;
1414        case Array::Uint16Array:
1415            forNode(node->child1()).filter(SpecUint16Array);
1416            break;
1417        case Array::Uint32Array:
1418            forNode(node->child1()).filter(SpecUint32Array);
1419            break;
1420        case Array::Float32Array:
1421            forNode(node->child1()).filter(SpecFloat32Array);
1422            break;
1423        case Array::Float64Array:
1424            forNode(node->child1()).filter(SpecFloat64Array);
1425            break;
1426        default:
1427            RELEASE_ASSERT_NOT_REACHED();
1428            break;
1429        }
1430        forNode(node->child1()).filterArrayModes(node->arrayMode().arrayModesThatPassFiltering());
1431        m_haveStructures = true;
1432        break;
1433    }
1434    case Arrayify: {
1435        if (node->arrayMode().alreadyChecked(m_graph, node, forNode(node->child1()))) {
1436            m_foundConstants = true;
1437            break;
1438        }
1439        ASSERT(node->arrayMode().conversion() == Array::Convert
1440            || node->arrayMode().conversion() == Array::RageConvert);
1441        node->setCanExit(true);
1442        clobberStructures(indexInBlock);
1443        forNode(node->child1()).filterArrayModes(node->arrayMode().arrayModesThatPassFiltering());
1444        m_haveStructures = true;
1445        break;
1446    }
1447    case ArrayifyToStructure: {
1448        AbstractValue& value = forNode(node->child1());
1449        StructureSet set = node->structure();
1450        if (value.m_futurePossibleStructure.isSubsetOf(set)
1451            || value.m_currentKnownStructure.isSubsetOf(set))
1452            m_foundConstants = true;
1453        node->setCanExit(true);
1454        clobberStructures(indexInBlock);
1455        value.filter(set);
1456        m_haveStructures = true;
1457        break;
1458    }
1459    case GetIndexedPropertyStorage: {
1460        forNode(node).clear();
1461        break;
1462    }
1463    case GetByOffset: {
1464        forNode(node).makeTop();
1465        break;
1466    }
1467
1468    case PutByOffset: {
1469        break;
1470    }
1471
1472    case CheckFunction: {
1473        JSValue value = forNode(node->child1()).value();
1474        if (value == node->function()) {
1475            m_foundConstants = true;
1476            ASSERT(value);
1477            break;
1478        }
1479
1480        node->setCanExit(true); // Lies! We can do better.
1481        forNode(node->child1()).filterByValue(node->function());
1482        break;
1483    }
1484
1485    case PutById:
1486    case PutByIdDirect:
1487        node->setCanExit(true);
1488        if (Structure* structure = forNode(node->child1()).bestProvenStructure()) {
1489            PutByIdStatus status = PutByIdStatus::computeFor(
1490                m_graph.m_vm,
1491                m_graph.globalObjectFor(node->codeOrigin),
1492                structure,
1493                m_graph.m_codeBlock->identifier(node->identifierNumber()),
1494                node->op() == PutByIdDirect);
1495            if (status.isSimpleReplace()) {
1496                forNode(node->child1()).filter(structure);
1497                m_foundConstants = true;
1498                break;
1499            }
1500            if (status.isSimpleTransition()) {
1501                clobberStructures(indexInBlock);
1502                forNode(node->child1()).set(status.newStructure());
1503                m_haveStructures = true;
1504                m_foundConstants = true;
1505                break;
1506            }
1507        }
1508        clobberWorld(node->codeOrigin, indexInBlock);
1509        break;
1510
1511    case GetGlobalVar:
1512        forNode(node).makeTop();
1513        break;
1514
1515    case GlobalVarWatchpoint:
1516        node->setCanExit(true);
1517        break;
1518
1519    case PutGlobalVar:
1520    case PutGlobalVarCheck:
1521        break;
1522
1523    case CheckHasInstance:
1524        node->setCanExit(true);
1525        // Sadly, we don't propagate the fact that we've done CheckHasInstance
1526        break;
1527
1528    case InstanceOf:
1529        node->setCanExit(true);
1530        // Again, sadly, we don't propagate the fact that we've done InstanceOf
1531        forNode(node).set(SpecBoolean);
1532        break;
1533
1534    case Phi:
1535    case Flush:
1536    case PhantomLocal:
1537    case Breakpoint:
1538        break;
1539
1540    case Call:
1541    case Construct:
1542    case Resolve:
1543    case ResolveBase:
1544    case ResolveBaseStrictPut:
1545    case ResolveGlobal:
1546        node->setCanExit(true);
1547        clobberWorld(node->codeOrigin, indexInBlock);
1548        forNode(node).makeTop();
1549        break;
1550
1551    case GarbageValue:
1552        clobberWorld(node->codeOrigin, indexInBlock);
1553        forNode(node).makeTop();
1554        break;
1555
1556    case Unreachable:
1557        RELEASE_ASSERT_NOT_REACHED();
1558        break;
1559
1560    case ForceOSRExit:
1561        node->setCanExit(true);
1562        m_isValid = false;
1563        break;
1564
1565    case CheckWatchdogTimer:
1566        node->setCanExit(true);
1567        break;
1568
1569    case Phantom:
1570    case InlineStart:
1571    case Nop:
1572    case CountExecution:
1573        break;
1574
1575    case LastNodeType:
1576        RELEASE_ASSERT_NOT_REACHED();
1577        break;
1578    }
1579
1580    return m_isValid;
1581}
1582
1583bool AbstractState::executeEffects(unsigned indexInBlock)
1584{
1585    return executeEffects(indexInBlock, m_block->at(indexInBlock));
1586}
1587
1588bool AbstractState::execute(unsigned indexInBlock)
1589{
1590    Node* node = m_block->at(indexInBlock);
1591    if (!startExecuting(node))
1592        return true;
1593
1594    executeEdges(node);
1595    return executeEffects(indexInBlock, node);
1596}
1597
1598inline void AbstractState::clobberWorld(const CodeOrigin& codeOrigin, unsigned indexInBlock)
1599{
1600    clobberCapturedVars(codeOrigin);
1601    clobberStructures(indexInBlock);
1602}
1603
1604inline void AbstractState::clobberCapturedVars(const CodeOrigin& codeOrigin)
1605{
1606    if (codeOrigin.inlineCallFrame) {
1607        const BitVector& capturedVars = codeOrigin.inlineCallFrame->capturedVars;
1608        for (size_t i = capturedVars.size(); i--;) {
1609            if (!capturedVars.quickGet(i))
1610                continue;
1611            m_variables.local(i).makeTop();
1612        }
1613    } else {
1614        for (size_t i = m_codeBlock->m_numVars; i--;) {
1615            if (m_codeBlock->isCaptured(i))
1616                m_variables.local(i).makeTop();
1617        }
1618    }
1619
1620    for (size_t i = m_variables.numberOfArguments(); i--;) {
1621        if (m_codeBlock->isCaptured(argumentToOperand(i)))
1622            m_variables.argument(i).makeTop();
1623    }
1624}
1625
1626inline void AbstractState::clobberStructures(unsigned indexInBlock)
1627{
1628    if (!m_haveStructures)
1629        return;
1630    for (size_t i = indexInBlock + 1; i--;)
1631        forNode(m_block->at(i)).clobberStructures();
1632    for (size_t i = m_variables.numberOfArguments(); i--;)
1633        m_variables.argument(i).clobberStructures();
1634    for (size_t i = m_variables.numberOfLocals(); i--;)
1635        m_variables.local(i).clobberStructures();
1636    m_haveStructures = false;
1637    m_didClobber = true;
1638}
1639
1640inline bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
1641{
1642    if (!node)
1643        return false;
1644
1645    AbstractValue source;
1646
1647    if (node->variableAccessData()->isCaptured()) {
1648        // If it's captured then we know that whatever value was stored into the variable last is the
1649        // one we care about. This is true even if the variable at tail is dead, which might happen if
1650        // the last thing we did to the variable was a GetLocal and then ended up now using the
1651        // GetLocal's result.
1652
1653        source = inVariable;
1654#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1655        dataLogF("          Transfering ");
1656        source.dump(WTF::dataFile());
1657        dataLogF(" from last access due to captured variable.\n");
1658#endif
1659    } else {
1660#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1661        dataLogF("          It's live, node @%u.\n", node->index());
1662#endif
1663
1664        switch (node->op()) {
1665        case Phi:
1666        case SetArgument:
1667        case PhantomLocal:
1668        case Flush:
1669            // The block transfers the value from head to tail.
1670            source = inVariable;
1671#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1672            dataLogF("          Transfering ");
1673            source.dump(WTF::dataFile());
1674            dataLogF(" from head to tail.\n");
1675#endif
1676            break;
1677
1678        case GetLocal:
1679            // The block refines the value with additional speculations.
1680            source = forNode(node);
1681#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1682            dataLogF("          Refining to ");
1683            source.dump(WTF::dataFile());
1684            dataLogF("\n");
1685#endif
1686            break;
1687
1688        case SetLocal:
1689            // The block sets the variable, and potentially refines it, both
1690            // before and after setting it.
1691            if (node->variableAccessData()->shouldUseDoubleFormat()) {
1692                // FIXME: This unnecessarily loses precision.
1693                source.set(SpecDouble);
1694            } else
1695                source = forNode(node->child1());
1696#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1697            dataLogF("          Setting to ");
1698            source.dump(WTF::dataFile());
1699            dataLogF("\n");
1700#endif
1701            break;
1702
1703        default:
1704            RELEASE_ASSERT_NOT_REACHED();
1705            break;
1706        }
1707    }
1708
1709    if (destination == source) {
1710        // Abstract execution did not change the output value of the variable, for this
1711        // basic block, on this iteration.
1712#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1713        dataLogF("          Not changed!\n");
1714#endif
1715        return false;
1716    }
1717
1718    // Abstract execution reached a new conclusion about the speculations reached about
1719    // this variable after execution of this basic block. Update the state, and return
1720    // true to indicate that the fixpoint must go on!
1721    destination = source;
1722#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1723    dataLogF("          Changed!\n");
1724#endif
1725    return true;
1726}
1727
1728inline bool AbstractState::merge(BasicBlock* from, BasicBlock* to)
1729{
1730    ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
1731    ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
1732
1733    bool changed = false;
1734
1735    for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
1736        AbstractValue& destination = to->valuesAtHead.argument(argument);
1737        changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
1738    }
1739
1740    for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
1741        AbstractValue& destination = to->valuesAtHead.local(local);
1742        changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
1743    }
1744
1745    if (!to->cfaHasVisited)
1746        changed = true;
1747
1748    to->cfaShouldRevisit |= changed;
1749
1750    return changed;
1751}
1752
1753inline bool AbstractState::mergeToSuccessors(Graph& graph, BasicBlock* basicBlock)
1754{
1755    Node* terminal = basicBlock->last();
1756
1757    ASSERT(terminal->isTerminal());
1758
1759    switch (terminal->op()) {
1760    case Jump: {
1761        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
1762#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1763        dataLogF("        Merging to block #%u.\n", terminal->takenBlockIndex());
1764#endif
1765        return merge(basicBlock, graph.m_blocks[terminal->takenBlockIndex()].get());
1766    }
1767
1768    case Branch: {
1769        ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
1770        bool changed = false;
1771#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1772        dataLogF("        Merging to block #%u.\n", terminal->takenBlockIndex());
1773#endif
1774        if (basicBlock->cfaBranchDirection != TakeFalse)
1775            changed |= merge(basicBlock, graph.m_blocks[terminal->takenBlockIndex()].get());
1776#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1777        dataLogF("        Merging to block #%u.\n", terminal->notTakenBlockIndex());
1778#endif
1779        if (basicBlock->cfaBranchDirection != TakeTrue)
1780            changed |= merge(basicBlock, graph.m_blocks[terminal->notTakenBlockIndex()].get());
1781        return changed;
1782    }
1783
1784    case Return:
1785    case Unreachable:
1786        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
1787        return false;
1788
1789    default:
1790        RELEASE_ASSERT_NOT_REACHED();
1791        return false;
1792    }
1793}
1794
1795inline bool AbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
1796{
1797    if (!destinationNode)
1798        return false;
1799
1800    ASSERT_UNUSED(sourceNode, sourceNode);
1801
1802    // FIXME: We could do some sparse conditional propagation here!
1803
1804    return destination.merge(source);
1805}
1806
1807void AbstractState::dump(PrintStream& out)
1808{
1809    bool first = true;
1810    for (size_t i = 0; i < m_block->size(); ++i) {
1811        Node* node = m_block->at(i);
1812        AbstractValue& value = forNode(node);
1813        if (value.isClear())
1814            continue;
1815        if (first)
1816            first = false;
1817        else
1818            out.printf(" ");
1819        out.printf("@%lu:", static_cast<unsigned long>(node->index()));
1820        value.dump(out);
1821    }
1822}
1823
1824} } // namespace JSC::DFG
1825
1826#endif // ENABLE(DFG_JIT)
1827
1828