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