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