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