DFG should not speculate array even when predictions say that the base is not an...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGAbstractState.cpp
1 /*
2  * Copyright (C) 2011 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 #define CFA_PROFILING 0
37
38 #if CFA_PROFILING
39 #define PROFILE(flag) SamplingFlags::ScopedFlag scopedFlag(flag)
40 #else
41 #define PROFILE(flag) do { } while (false)
42 #endif
43
44 // Profiling flags
45 #define FLAG_FOR_BLOCK_INITIALIZATION  17
46 #define FLAG_FOR_BLOCK_END             18
47 #define FLAG_FOR_EXECUTION             19
48 #define FLAG_FOR_MERGE_TO_SUCCESSORS   20
49 #define FLAG_FOR_STRUCTURE_CLOBBERING  21
50
51 AbstractState::AbstractState(CodeBlock* codeBlock, Graph& graph)
52     : m_codeBlock(codeBlock)
53     , m_graph(graph)
54     , m_variables(codeBlock->m_numParameters, graph.m_localVars)
55     , m_block(0)
56 {
57     size_t maxBlockSize = 0;
58     for (size_t i = 0; i < graph.m_blocks.size(); ++i) {
59         BasicBlock* block = graph.m_blocks[i].get();
60         if (block->end - block->begin > maxBlockSize)
61             maxBlockSize = block->end - block->begin;
62     }
63     m_nodes.resize(maxBlockSize);
64 }
65
66 AbstractState::~AbstractState() { }
67
68 void AbstractState::beginBasicBlock(BasicBlock* basicBlock)
69 {
70     PROFILE(FLAG_FOR_BLOCK_INITIALIZATION);
71     
72     ASSERT(!m_block);
73     
74     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
75     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
76     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
77     
78     for (size_t i = 0; i < basicBlock->end - basicBlock->begin; ++i)
79         m_nodes[i].clear();
80     m_variables = basicBlock->valuesAtHead;
81     m_haveStructures = false;
82     for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
83         if (m_variables.argument(i).m_structure.isNeitherClearNorTop()) {
84             m_haveStructures = true;
85             break;
86         }
87     }
88     for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
89         if (m_variables.local(i).m_structure.isNeitherClearNorTop()) {
90             m_haveStructures = true;
91             break;
92         }
93     }
94     
95     basicBlock->cfaShouldRevisit = false;
96     basicBlock->cfaHasVisited = true;
97     m_block = basicBlock;
98     m_isValid = true;
99 }
100
101 void AbstractState::initialize(Graph& graph)
102 {
103     PROFILE(FLAG_FOR_BLOCK_INITIALIZATION);
104     BasicBlock* root = graph.m_blocks[0].get();
105     root->cfaShouldRevisit = true;
106     for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
107         PredictedType prediction = graph[root->variablesAtHead.argument(i)].variableAccessData()->prediction();
108         if (isInt32Prediction(prediction))
109             root->valuesAtHead.argument(i).set(PredictInt32);
110         else if (isArrayPrediction(prediction))
111             root->valuesAtHead.argument(i).set(PredictArray);
112         else if (isByteArrayPrediction(prediction))
113             root->valuesAtHead.argument(i).set(PredictByteArray);
114         else if (isBooleanPrediction(prediction))
115             root->valuesAtHead.argument(i).set(PredictBoolean);
116         else if (isInt8ArrayPrediction(prediction))
117             root->valuesAtHead.argument(i).set(PredictInt8Array);
118         else if (isInt16ArrayPrediction(prediction))
119             root->valuesAtHead.argument(i).set(PredictInt16Array);
120         else if (isInt32ArrayPrediction(prediction))
121             root->valuesAtHead.argument(i).set(PredictInt32Array);
122         else if (isUint8ArrayPrediction(prediction))
123             root->valuesAtHead.argument(i).set(PredictUint8Array);
124         else if (isUint16ArrayPrediction(prediction))
125             root->valuesAtHead.argument(i).set(PredictUint16Array);
126         else if (isUint32ArrayPrediction(prediction))
127             root->valuesAtHead.argument(i).set(PredictUint32Array);
128         else if (isFloat32ArrayPrediction(prediction))
129             root->valuesAtHead.argument(i).set(PredictFloat32Array);
130         else if (isFloat64ArrayPrediction(prediction))
131             root->valuesAtHead.argument(i).set(PredictFloat64Array);
132         else
133             root->valuesAtHead.argument(i).makeTop();
134     }
135 }
136
137 bool AbstractState::endBasicBlock(MergeMode mergeMode)
138 {
139     PROFILE(FLAG_FOR_BLOCK_END);
140     ASSERT(m_block);
141     
142     BasicBlock* block = m_block; // Save the block for successor merging.
143     
144     if (!m_isValid) {
145         reset();
146         return false;
147     }
148     
149     bool changed = false;
150     
151     if (mergeMode != DontMerge || !ASSERT_DISABLED) {
152         for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
153 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
154             printf("        Merging state for argument %lu.\n", argument);
155 #endif
156             changed |= mergeStateAtTail(block->valuesAtTail.argument(argument), m_variables.argument(argument), block->variablesAtTail.argument(argument));
157         }
158         
159         for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
160 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
161             printf("        Merging state for local %lu.\n", local);
162 #endif
163             changed |= mergeStateAtTail(block->valuesAtTail.local(local), m_variables.local(local), block->variablesAtTail.local(local));
164         }
165     }
166     
167     ASSERT(mergeMode != DontMerge || !changed);
168     
169     reset();
170     
171     if (mergeMode != MergeToSuccessors)
172         return changed;
173     
174     return mergeToSuccessors(m_graph, block);
175 }
176
177 void AbstractState::reset()
178 {
179     m_block = 0;
180     m_isValid = false;
181 }
182
183 bool AbstractState::execute(NodeIndex nodeIndex)
184 {
185     PROFILE(FLAG_FOR_EXECUTION);
186     ASSERT(m_block);
187     ASSERT(m_isValid);
188         
189     Node& node = m_graph[nodeIndex];
190         
191     if (!node.shouldGenerate())
192         return true;
193         
194     switch (node.op) {
195     case JSConstant:
196     case WeakJSConstant: {
197         JSValue value = m_graph.valueOfJSConstant(m_codeBlock, nodeIndex);
198         if (value.isCell())
199             m_haveStructures = true;
200         forNode(nodeIndex).set(value);
201         break;
202     }
203             
204     case GetLocal: {
205         forNode(nodeIndex) = m_variables.operand(node.local());
206         break;
207     }
208         
209     case SetLocal: {
210         if (node.variableAccessData()->shouldUseDoubleFormat()) {
211             forNode(node.child1()).filter(PredictNumber);
212             m_variables.operand(node.local()).set(PredictDouble);
213             break;
214         }
215         
216         PredictedType predictedType = node.variableAccessData()->prediction();
217         if (isInt32Prediction(predictedType))
218             forNode(node.child1()).filter(PredictInt32);
219         else if (isArrayPrediction(predictedType))
220             forNode(node.child1()).filter(PredictArray);
221         else if (isByteArrayPrediction(predictedType))
222             forNode(node.child1()).filter(PredictByteArray);
223         else if (isBooleanPrediction(predictedType))
224             forNode(node.child1()).filter(PredictBoolean);
225         
226         m_variables.operand(node.local()) = forNode(node.child1());
227         break;
228     }
229             
230     case SetArgument:
231         // Assert that the state of arguments has been set.
232         ASSERT(!m_block->valuesAtHead.operand(node.local()).isClear());
233         break;
234             
235     case BitAnd:
236     case BitOr:
237     case BitXor:
238     case BitRShift:
239     case BitLShift:
240     case BitURShift:
241         forNode(node.child1()).filter(PredictInt32);
242         forNode(node.child2()).filter(PredictInt32);
243         forNode(nodeIndex).set(PredictInt32);
244         break;
245         
246     case UInt32ToNumber:
247         if (!node.canSpeculateInteger())
248             forNode(nodeIndex).set(PredictDouble);
249         else
250             forNode(nodeIndex).set(PredictInt32);
251         break;
252             
253     case ValueToInt32:
254         if (!m_graph[node.child1()].shouldNotSpeculateInteger()) {
255             if (m_graph[node.child1()].shouldSpeculateDouble())
256                 forNode(node.child1()).filter(PredictNumber);
257             else
258                 forNode(node.child1()).filter(PredictInt32);
259         }
260         forNode(nodeIndex).set(PredictInt32);
261         break;
262             
263     case ValueToNumber:
264         if (m_graph[node.child1()].shouldNotSpeculateInteger()) {
265             forNode(node.child1()).filter(PredictNumber);
266             forNode(nodeIndex).set(PredictDouble);
267             break;
268         }
269             
270         forNode(node.child1()).filter(PredictInt32);
271         forNode(nodeIndex).set(PredictInt32);
272         break;
273             
274     case ValueToDouble:
275         forNode(node.child1()).filter(PredictNumber);
276         forNode(nodeIndex).set(PredictDouble);
277         break;
278             
279     case ValueAdd:
280     case ArithAdd: {
281         if (Node::shouldSpeculateInteger(m_graph[node.child1()], m_graph[node.child2()]) && node.canSpeculateInteger()) {
282             forNode(node.child1()).filter(PredictInt32);
283             forNode(node.child2()).filter(PredictInt32);
284             forNode(nodeIndex).set(PredictInt32);
285             break;
286         }
287         if (Node::shouldSpeculateNumber(m_graph[node.child1()], m_graph[node.child2()])) {
288             forNode(node.child1()).filter(PredictNumber);
289             forNode(node.child2()).filter(PredictNumber);
290             forNode(nodeIndex).set(PredictDouble);
291             break;
292         }
293         ASSERT(node.op == ValueAdd);
294         clobberStructures(nodeIndex);
295         forNode(nodeIndex).set(PredictString | PredictInt32 | PredictNumber);
296         break;
297     }
298             
299     case ArithSub:
300     case ArithMul:
301     case ArithDiv:
302     case ArithMin:
303     case ArithMax: {
304         if (Node::shouldSpeculateInteger(m_graph[node.child1()], m_graph[node.child2()]) && node.canSpeculateInteger()) {
305             forNode(node.child1()).filter(PredictInt32);
306             forNode(node.child2()).filter(PredictInt32);
307             forNode(nodeIndex).set(PredictInt32);
308             break;
309         }
310         forNode(node.child1()).filter(PredictNumber);
311         forNode(node.child2()).filter(PredictNumber);
312         forNode(nodeIndex).set(PredictDouble);
313         break;
314     }
315             
316     case ArithMod: {
317         if (m_graph[node.child1()].shouldNotSpeculateInteger() || m_graph[node.child2()].shouldNotSpeculateInteger() || !node.canSpeculateInteger()) {
318             forNode(node.child1()).filter(PredictNumber);
319             forNode(node.child2()).filter(PredictNumber);
320             forNode(nodeIndex).set(PredictDouble);
321             break;
322         }
323         forNode(node.child1()).filter(PredictInt32);
324         forNode(node.child2()).filter(PredictInt32);
325         forNode(nodeIndex).set(PredictInt32);
326         break;
327     }
328             
329     case ArithAbs:
330         if (m_graph[node.child1()].shouldSpeculateInteger() && node.canSpeculateInteger()) {
331             forNode(node.child1()).filter(PredictInt32);
332             forNode(nodeIndex).set(PredictInt32);
333             break;
334         }
335         forNode(node.child1()).filter(PredictNumber);
336         forNode(nodeIndex).set(PredictDouble);
337         break;
338             
339     case ArithSqrt:
340         forNode(node.child1()).filter(PredictNumber);
341         forNode(nodeIndex).set(PredictDouble);
342         break;
343             
344     case LogicalNot: {
345         Node& child = m_graph[node.child1()];
346         if (isBooleanPrediction(child.prediction()) || !child.prediction())
347             forNode(node.child1()).filter(PredictBoolean);
348         else if (child.shouldSpeculateFinalObjectOrOther())
349             forNode(node.child1()).filter(PredictFinalObject | PredictOther);
350         else if (child.shouldSpeculateArrayOrOther())
351             forNode(node.child1()).filter(PredictArray | PredictOther);
352         else if (child.shouldSpeculateInteger())
353             forNode(node.child1()).filter(PredictInt32);
354         else if (child.shouldSpeculateNumber())
355             forNode(node.child1()).filter(PredictNumber);
356         else
357             clobberStructures(nodeIndex);
358         forNode(nodeIndex).set(PredictBoolean);
359         break;
360     }
361             
362     case CompareLess:
363     case CompareLessEq:
364     case CompareGreater:
365     case CompareGreaterEq:
366     case CompareEq: {
367         Node& left = m_graph[node.child1()];
368         Node& right = m_graph[node.child2()];
369         PredictedType filter;
370         if (Node::shouldSpeculateInteger(left, right))
371             filter = PredictInt32;
372         else if (Node::shouldSpeculateNumber(left, right))
373             filter = PredictNumber;
374         else if (node.op == CompareEq && Node::shouldSpeculateFinalObject(left, right))
375             filter = PredictFinalObject;
376         else if (node.op == CompareEq && Node::shouldSpeculateArray(left, right))
377             filter = PredictArray;
378         else {
379             filter = PredictTop;
380             clobberStructures(nodeIndex);
381         }
382         forNode(node.child1()).filter(filter);
383         forNode(node.child2()).filter(filter);
384         forNode(nodeIndex).set(PredictBoolean);
385         break;
386     }
387             
388     case CompareStrictEq:
389         forNode(nodeIndex).set(PredictBoolean);
390         break;
391         
392     case StringCharCodeAt:
393         forNode(node.child1()).filter(PredictString);
394         forNode(node.child2()).filter(PredictInt32);
395         forNode(nodeIndex).set(PredictInt32);
396         break;
397         
398     case StringCharAt:
399         forNode(node.child1()).filter(PredictString);
400         forNode(node.child2()).filter(PredictInt32);
401         forNode(nodeIndex).set(PredictString);
402         break;
403             
404     case GetByVal: {
405         if (!node.prediction() || !m_graph[node.child1()].prediction() || !m_graph[node.child2()].prediction()) {
406             m_isValid = false;
407             break;
408         }
409         if (!isActionableArrayPrediction(m_graph[node.child1()].prediction()) || !m_graph[node.child2()].shouldSpeculateInteger()) {
410             clobberStructures(nodeIndex);
411             forNode(nodeIndex).makeTop();
412             break;
413         }
414         if (m_graph[node.child1()].prediction() == PredictString) {
415             forNode(node.child1()).filter(PredictString);
416             forNode(node.child2()).filter(PredictInt32);
417             forNode(nodeIndex).set(PredictString);
418             break;
419         }
420         if (m_graph[node.child1()].shouldSpeculateByteArray()) {
421             forNode(node.child1()).filter(PredictByteArray);
422             forNode(node.child2()).filter(PredictInt32);
423             forNode(nodeIndex).set(PredictInt32);
424             break;
425         }
426         
427         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
428             forNode(node.child1()).filter(PredictInt8Array);
429             forNode(node.child2()).filter(PredictInt32);
430             forNode(nodeIndex).set(PredictInt32);
431             break;
432         }
433         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
434             forNode(node.child1()).filter(PredictInt16Array);
435             forNode(node.child2()).filter(PredictInt32);
436             forNode(nodeIndex).set(PredictInt32);
437             break;
438         }
439         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
440             forNode(node.child1()).filter(PredictInt32Array);
441             forNode(node.child2()).filter(PredictInt32);
442             forNode(nodeIndex).set(PredictInt32);
443             break;
444         }
445         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
446             forNode(node.child1()).filter(PredictUint8Array);
447             forNode(node.child2()).filter(PredictInt32);
448             forNode(nodeIndex).set(PredictInt32);
449             break;
450         }
451         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
452             forNode(node.child1()).filter(PredictUint16Array);
453             forNode(node.child2()).filter(PredictInt32);
454             forNode(nodeIndex).set(PredictInt32);
455             break;
456         }
457         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
458             forNode(node.child1()).filter(PredictUint32Array);
459             forNode(node.child2()).filter(PredictInt32);
460             forNode(nodeIndex).set(PredictDouble);
461             break;
462         }
463         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
464             forNode(node.child1()).filter(PredictFloat32Array);
465             forNode(node.child2()).filter(PredictInt32);
466             forNode(nodeIndex).set(PredictDouble);
467             break;
468         }
469         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
470             forNode(node.child1()).filter(PredictFloat64Array);
471             forNode(node.child2()).filter(PredictInt32);
472             forNode(nodeIndex).set(PredictDouble);
473             break;
474         }
475         ASSERT(m_graph[node.child1()].shouldSpeculateArray());
476         forNode(node.child1()).filter(PredictArray);
477         forNode(node.child2()).filter(PredictInt32);
478         forNode(nodeIndex).makeTop();
479         break;
480     }
481             
482     case PutByVal:
483     case PutByValAlias: {
484         if (!m_graph[node.child1()].prediction() || !m_graph[node.child2()].prediction()) {
485             m_isValid = false;
486             break;
487         }
488         if (!m_graph[node.child2()].shouldSpeculateInteger() || !isActionableMutableArrayPrediction(m_graph[node.child1()].prediction())) {
489             ASSERT(node.op == PutByVal);
490             clobberStructures(nodeIndex);
491             forNode(nodeIndex).makeTop();
492             break;
493         }
494         if (m_graph[node.child1()].shouldSpeculateByteArray()) {
495             forNode(node.child1()).filter(PredictByteArray);
496             forNode(node.child2()).filter(PredictInt32);
497             forNode(node.child3()).filter(PredictNumber);
498             break;
499         }
500         
501         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
502             forNode(node.child1()).filter(PredictInt8Array);
503             forNode(node.child2()).filter(PredictInt32);
504             forNode(node.child3()).filter(PredictNumber);
505             break;
506         }
507         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
508             forNode(node.child1()).filter(PredictInt16Array);
509             forNode(node.child2()).filter(PredictInt32);
510             forNode(node.child3()).filter(PredictNumber);
511             break;
512         }
513         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
514             forNode(node.child1()).filter(PredictInt32Array);
515             forNode(node.child2()).filter(PredictInt32);
516             forNode(node.child3()).filter(PredictNumber);
517             break;
518         }
519         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
520             forNode(node.child1()).filter(PredictUint8Array);
521             forNode(node.child2()).filter(PredictInt32);
522             forNode(node.child3()).filter(PredictNumber);
523             break;
524         }
525         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
526             forNode(node.child1()).filter(PredictUint16Array);
527             forNode(node.child2()).filter(PredictInt32);
528             forNode(node.child3()).filter(PredictNumber);
529             break;
530         }
531         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
532             forNode(node.child1()).filter(PredictUint32Array);
533             forNode(node.child2()).filter(PredictInt32);
534             forNode(node.child3()).filter(PredictNumber);
535             break;
536         }
537         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
538             forNode(node.child1()).filter(PredictFloat32Array);
539             forNode(node.child2()).filter(PredictInt32);
540             forNode(node.child3()).filter(PredictNumber);
541             break;
542         }
543         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
544             forNode(node.child1()).filter(PredictFloat64Array);
545             forNode(node.child2()).filter(PredictInt32);
546             forNode(node.child3()).filter(PredictNumber);
547             break;
548         }
549         ASSERT(m_graph[node.child1()].shouldSpeculateArray());
550         forNode(node.child1()).filter(PredictArray);
551         forNode(node.child2()).filter(PredictInt32);
552         break;
553     }
554             
555     case ArrayPush:
556         forNode(node.child1()).filter(PredictArray);
557         forNode(nodeIndex).set(PredictNumber);
558         break;
559             
560     case ArrayPop:
561         forNode(node.child1()).filter(PredictArray);
562         forNode(nodeIndex).makeTop();
563         break;
564             
565     case Jump:
566         break;
567             
568     case Branch: {
569         // There is probably profit to be found in doing sparse conditional constant
570         // propagation, and to take it one step further, where a variable's value
571         // is specialized on each direction of a branch. For now, we don't do this.
572         Node& child = m_graph[node.child1()];
573         if (isBooleanPrediction(child.prediction()) || !child.prediction())
574             forNode(node.child1()).filter(PredictBoolean);
575         else if (child.shouldSpeculateFinalObjectOrOther())
576             forNode(node.child1()).filter(PredictFinalObject | PredictOther);
577         else if (child.shouldSpeculateArrayOrOther())
578             forNode(node.child1()).filter(PredictArray | PredictOther);
579         else if (child.shouldSpeculateInteger())
580             forNode(node.child1()).filter(PredictInt32);
581         else if (child.shouldSpeculateNumber())
582             forNode(node.child1()).filter(PredictNumber);
583         break;
584     }
585             
586     case Return:
587     case Throw:
588     case ThrowReferenceError:
589         m_isValid = false;
590         break;
591             
592     case ToPrimitive: {
593         Node& child = m_graph[node.child1()];
594         if (child.shouldSpeculateInteger()) {
595             forNode(node.child1()).filter(PredictInt32);
596             forNode(nodeIndex).set(PredictInt32);
597             break;
598         }
599
600         AbstractValue& source = forNode(node.child1());
601         AbstractValue& destination = forNode(nodeIndex);
602             
603         PredictedType type = source.m_type;
604         if (type & ~(PredictNumber | PredictString | PredictBoolean)) {
605             type &= (PredictNumber | PredictString | PredictBoolean);
606             type |= PredictString;
607         }
608         destination.set(type);
609         break;
610     }
611             
612     case StrCat:
613         forNode(nodeIndex).set(PredictString);
614         break;
615             
616     case NewArray:
617     case NewArrayBuffer:
618         forNode(nodeIndex).set(m_codeBlock->globalObject()->arrayStructure());
619         m_haveStructures = true;
620         break;
621             
622     case NewRegexp:
623         forNode(nodeIndex).set(m_codeBlock->globalObject()->regExpStructure());
624         m_haveStructures = true;
625         break;
626             
627     case ConvertThis: {
628         Node& child = m_graph[node.child1()];
629         AbstractValue& source = forNode(node.child1());
630         AbstractValue& destination = forNode(nodeIndex);
631             
632         if (isObjectPrediction(source.m_type)) {
633             // This is the simple case. We already know that the source is an
634             // object, so there's nothing to do. I don't think this case will
635             // be hit, but then again, you never know.
636             destination = source;
637             break;
638         }
639         
640         if (isOtherPrediction(child.prediction())) {
641             source.filter(PredictOther);
642             destination.set(PredictObjectOther);
643             break;
644         }
645         
646         if (isObjectPrediction(child.prediction())) {
647             source.filter(PredictObjectMask);
648             destination = source;
649             break;
650         }
651             
652         destination = source;
653         destination.merge(PredictObjectOther);
654         break;
655     }
656             
657     case CreateThis: {
658         Node& child = m_graph[node.child1()];
659         AbstractValue& source = forNode(node.child1());
660         AbstractValue& destination = forNode(nodeIndex);
661             
662         if (child.shouldSpeculateFinalObject())
663             source.filter(PredictFinalObject);
664             
665         destination.set(PredictFinalObject);
666         break;
667     }
668             
669     case NewObject:
670         forNode(nodeIndex).set(m_codeBlock->globalObject()->emptyObjectStructure());
671         m_haveStructures = true;
672         break;
673             
674     case GetCallee:
675         forNode(nodeIndex).set(PredictFunction);
676         break;
677             
678     case GetScopeChain:
679         forNode(nodeIndex).set(PredictCellOther);
680         break;
681             
682     case GetScopedVar:
683         forNode(nodeIndex).makeTop();
684         break;
685             
686     case PutScopedVar:
687         clobberStructures(nodeIndex);
688         break;
689             
690     case GetById:
691         if (!node.prediction()) {
692             m_isValid = false;
693             break;
694         }
695         if (isCellPrediction(m_graph[node.child1()].prediction()))
696             forNode(node.child1()).filter(PredictCell);
697         clobberStructures(nodeIndex);
698         forNode(nodeIndex).makeTop();
699         break;
700             
701     case GetArrayLength:
702         forNode(node.child1()).filter(PredictArray);
703         forNode(nodeIndex).set(PredictInt32);
704         break;
705
706     case GetStringLength:
707         forNode(node.child1()).filter(PredictString);
708         forNode(nodeIndex).set(PredictInt32);
709         break;
710         
711     case GetByteArrayLength:
712         forNode(node.child1()).filter(PredictByteArray);
713         forNode(nodeIndex).set(PredictInt32);
714         break;
715     case GetInt8ArrayLength:
716         forNode(node.child1()).filter(PredictInt8Array);
717         forNode(nodeIndex).set(PredictInt32);
718         break;
719     case GetInt16ArrayLength:
720         forNode(node.child1()).filter(PredictInt16Array);
721         forNode(nodeIndex).set(PredictInt32);
722         break;
723     case GetInt32ArrayLength:
724         forNode(node.child1()).filter(PredictInt32Array);
725         forNode(nodeIndex).set(PredictInt32);
726         break;
727     case GetUint8ArrayLength:
728         forNode(node.child1()).filter(PredictUint8Array);
729         forNode(nodeIndex).set(PredictInt32);
730         break;
731     case GetUint16ArrayLength:
732         forNode(node.child1()).filter(PredictUint16Array);
733         forNode(nodeIndex).set(PredictInt32);
734         break;
735     case GetUint32ArrayLength:
736         forNode(node.child1()).filter(PredictUint32Array);
737         forNode(nodeIndex).set(PredictInt32);
738         break;
739     case GetFloat32ArrayLength:
740         forNode(node.child1()).filter(PredictFloat32Array);
741         forNode(nodeIndex).set(PredictInt32);
742         break;
743     case GetFloat64ArrayLength:
744         forNode(node.child1()).filter(PredictFloat64Array);
745         forNode(nodeIndex).set(PredictInt32);
746         break;
747             
748     case CheckStructure:
749         // FIXME: We should be able to propagate the structure sets of constants (i.e. prototypes).
750         forNode(node.child1()).filter(node.structureSet());
751         m_haveStructures = true;
752         break;
753             
754     case PutStructure:
755         clobberStructures(nodeIndex);
756         forNode(node.child1()).set(node.structureTransitionData().newStructure);
757         m_haveStructures = true;
758         break;
759     case GetPropertyStorage:
760         forNode(node.child1()).filter(PredictCell);
761         forNode(nodeIndex).clear(); // The result is not a JS value.
762         break;
763     case GetIndexedPropertyStorage: {
764         PredictedType basePrediction = m_graph[node.child2()].prediction();
765         if (!(basePrediction & PredictInt32) && basePrediction) {
766             forNode(nodeIndex).clear();
767             break;
768         }
769         if (m_graph[node.child1()].prediction() == PredictString) {
770             forNode(node.child1()).filter(PredictString);
771             forNode(nodeIndex).clear();
772             break;
773         }
774         if (m_graph[node.child1()].shouldSpeculateByteArray()) {
775             forNode(node.child1()).filter(PredictByteArray);
776             forNode(nodeIndex).clear();
777             break;
778         }
779         
780         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
781             forNode(node.child1()).filter(PredictInt8Array);
782             forNode(nodeIndex).clear();
783             break;
784         }
785         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
786             forNode(node.child1()).filter(PredictInt16Array);
787             forNode(nodeIndex).clear();
788             break;
789         }
790         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
791             forNode(node.child1()).filter(PredictInt32Array);
792             forNode(nodeIndex).clear();
793             break;
794         }
795         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
796             forNode(node.child1()).filter(PredictUint8Array);
797             forNode(nodeIndex).clear();
798             break;
799         }
800         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
801             forNode(node.child1()).filter(PredictUint16Array);
802             forNode(nodeIndex).set(PredictOther);
803             break;
804         }
805         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
806             forNode(node.child1()).filter(PredictUint32Array);
807             forNode(nodeIndex).clear();
808             break;
809         }
810         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
811             forNode(node.child1()).filter(PredictFloat32Array);
812             forNode(nodeIndex).clear();
813             break;
814         }
815         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
816             forNode(node.child1()).filter(PredictFloat64Array);
817             forNode(nodeIndex).clear();
818             break;
819         }
820         forNode(node.child1()).filter(PredictArray);
821         forNode(nodeIndex).clear();
822         break; 
823     }
824     case GetByOffset:
825         forNode(node.child1()).filter(PredictCell);
826         forNode(nodeIndex).makeTop();
827         break;
828             
829     case PutByOffset:
830         forNode(node.child1()).filter(PredictCell);
831         break;
832             
833     case CheckFunction:
834         forNode(node.child1()).filter(PredictFunction);
835         // FIXME: Should be able to propagate the fact that we know what the function is.
836         break;
837             
838     case PutById:
839     case PutByIdDirect:
840         forNode(node.child1()).filter(PredictCell);
841         clobberStructures(nodeIndex);
842         break;
843             
844     case GetGlobalVar:
845         forNode(nodeIndex).makeTop();
846         break;
847             
848     case PutGlobalVar:
849         break;
850             
851     case CheckHasInstance:
852         forNode(node.child1()).filter(PredictCell);
853         // Sadly, we don't propagate the fact that we've done CheckHasInstance
854         break;
855             
856     case InstanceOf:
857         // Again, sadly, we don't propagate the fact that we've done InstanceOf
858         if (!(m_graph[node.child1()].prediction() & ~PredictCell) && !(forNode(node.child1()).m_type & ~PredictCell))
859             forNode(node.child1()).filter(PredictCell);
860         forNode(node.child3()).filter(PredictCell);
861         forNode(nodeIndex).set(PredictBoolean);
862         break;
863             
864     case Phi:
865     case Flush:
866         break;
867             
868     case Breakpoint:
869         break;
870             
871     case Call:
872     case Construct:
873     case Resolve:
874     case ResolveBase:
875     case ResolveBaseStrictPut:
876     case ResolveGlobal:
877         clobberStructures(nodeIndex);
878         forNode(nodeIndex).makeTop();
879         break;
880             
881     case ForceOSRExit:
882         m_isValid = false;
883         break;
884             
885     case Phantom:
886     case InlineStart:
887     case Nop:
888         break;
889     }
890     
891     return m_isValid;
892 }
893
894 inline void AbstractState::clobberStructures(NodeIndex nodeIndex)
895 {
896     PROFILE(FLAG_FOR_STRUCTURE_CLOBBERING);
897     if (!m_haveStructures)
898         return;
899     for (size_t i = nodeIndex - m_block->begin + 1; i-- > 0;)
900         m_nodes[i].clobberStructures();
901     for (size_t i = 0; i < m_variables.numberOfArguments(); ++i)
902         m_variables.argument(i).clobberStructures();
903     for (size_t i = 0; i < m_variables.numberOfLocals(); ++i)
904         m_variables.local(i).clobberStructures();
905     m_haveStructures = false;
906 }
907
908 inline bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, NodeIndex nodeIndex)
909 {
910     if (nodeIndex == NoNode)
911         return false;
912         
913     AbstractValue* source;
914         
915     Node& node = m_graph[nodeIndex];
916     if (!node.refCount())
917         return false;
918     
919 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
920             printf("          It's live, node @%u.\n", nodeIndex);
921 #endif
922
923     switch (node.op) {
924     case Phi:
925     case SetArgument:
926     case Flush:
927         // The block transfers the value from head to tail.
928         source = &inVariable;
929 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
930         printf("          Transfering from head to tail.\n");
931 #endif
932         break;
933             
934     case GetLocal:
935         // The block refines the value with additional speculations.
936         source = &forNode(nodeIndex);
937 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
938         printf("          Refining.\n");
939 #endif
940         break;
941             
942     case SetLocal:
943         // The block sets the variable, and potentially refines it, both
944         // before and after setting it.
945         source = &forNode(node.child1());
946 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
947         printf("          Setting.\n");
948 #endif
949         break;
950         
951     default:
952         ASSERT_NOT_REACHED();
953         source = 0;
954         break;
955     }
956     
957     if (destination == *source) {
958         // Abstract execution did not change the output value of the variable, for this
959         // basic block, on this iteration.
960 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
961         printf("          Not changed!\n");
962 #endif
963         return false;
964     }
965     
966     // Abstract execution reached a new conclusion about the speculations reached about
967     // this variable after execution of this basic block. Update the state, and return
968     // true to indicate that the fixpoint must go on!
969     destination = *source;
970 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
971     printf("          Changed!\n");
972 #endif
973     return true;
974 }
975
976 inline bool AbstractState::merge(BasicBlock* from, BasicBlock* to)
977 {
978     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
979     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
980     
981     bool changed = false;
982     
983     for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument)
984         changed |= mergeVariableBetweenBlocks(to->valuesAtHead.argument(argument), from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
985     
986     for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local)
987         changed |= mergeVariableBetweenBlocks(to->valuesAtHead.local(local), from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
988
989     if (!to->cfaHasVisited)
990         changed = true;
991     
992     to->cfaShouldRevisit |= changed;
993     
994     return changed;
995 }
996
997 inline bool AbstractState::mergeToSuccessors(Graph& graph, BasicBlock* basicBlock)
998 {
999     PROFILE(FLAG_FOR_MERGE_TO_SUCCESSORS);
1000
1001     Node& terminal = graph[basicBlock->end - 1];
1002     
1003     ASSERT(terminal.isTerminal());
1004     
1005     switch (terminal.op) {
1006     case Jump:
1007         return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
1008         
1009     case Branch:
1010         return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get())
1011             | merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get());
1012         
1013     case Return:
1014     case Throw:
1015     case ThrowReferenceError:
1016         return false;
1017         
1018     default:
1019         ASSERT_NOT_REACHED();
1020         return false;
1021     }
1022 }
1023
1024 inline bool AbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, NodeIndex destinationNodeIndex, NodeIndex sourceNodeIndex)
1025 {
1026     if (destinationNodeIndex == NoNode)
1027         return false;
1028     
1029     ASSERT_UNUSED(sourceNodeIndex, sourceNodeIndex != NoNode);
1030     
1031     // FIXME: We could do some sparse conditional propagation here!
1032     
1033     return destination.merge(source);
1034 }
1035
1036 #ifndef NDEBUG
1037 void AbstractState::dump(FILE* out)
1038 {
1039     bool first = true;
1040     for (size_t i = 0; i < m_nodes.size(); ++i) {
1041         if (m_nodes[i].isClear())
1042             continue;
1043         if (first)
1044             first = false;
1045         else
1046             fprintf(out, " ");
1047         fprintf(out, "@%lu:", static_cast<unsigned long>(i + m_block->begin));
1048         m_nodes[i].dump(out);
1049     }
1050 }
1051 #endif
1052
1053 } } // namespace JSC::DFG
1054
1055 #endif // ENABLE(DFG_JIT)
1056