DFG JIT cannot compile op_new_object, op_new_array,
[WebKit.git] / Source / JavaScriptCore / dfg / DFGByteCodeParser.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 "DFGByteCodeParser.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGCapabilities.h"
32 #include "CodeBlock.h"
33 #include <wtf/MathExtras.h>
34
35 namespace JSC { namespace DFG {
36
37 // === ByteCodeParser ===
38 //
39 // This class is used to compile the dataflow graph from a CodeBlock.
40 class ByteCodeParser {
41 public:
42     ByteCodeParser(JSGlobalData* globalData, CodeBlock* codeBlock, CodeBlock* profiledBlock, Graph& graph)
43         : m_globalData(globalData)
44         , m_codeBlock(codeBlock)
45         , m_profiledBlock(profiledBlock)
46         , m_graph(graph)
47         , m_currentIndex(0)
48         , m_parseFailed(false)
49         , m_constantUndefined(UINT_MAX)
50         , m_constantNull(UINT_MAX)
51         , m_constantNaN(UINT_MAX)
52         , m_constant1(UINT_MAX)
53         , m_constants(codeBlock->numberOfConstantRegisters())
54         , m_numArguments(codeBlock->m_numParameters)
55         , m_numLocals(codeBlock->m_numCalleeRegisters)
56         , m_preservedVars(codeBlock->m_numVars)
57         , m_parameterSlots(0)
58         , m_numPassedVarArgs(0)
59         , m_globalResolveNumber(0)
60     {
61         ASSERT(m_profiledBlock);
62     }
63
64     // Parse a full CodeBlock of bytecode.
65     bool parse();
66
67 private:
68     // Helper for min and max.
69     bool handleMinMax(bool usesResult, int resultOperand, NodeType op, int firstArg, int lastArg);
70     
71     // Handle intrinsic functions.
72     bool handleIntrinsic(bool usesResult, int resultOperand, Intrinsic, int firstArg, int lastArg);
73     // Parse a single basic block of bytecode instructions.
74     bool parseBlock(unsigned limit);
75     // Setup predecessor links in the graph's BasicBlocks.
76     void setupPredecessors();
77     // Link GetLocal & SetLocal nodes, to ensure live values are generated.
78     enum PhiStackType {
79         LocalPhiStack,
80         ArgumentPhiStack
81     };
82     template<PhiStackType stackType>
83     void processPhiStack();
84     // Add spill locations to nodes.
85     void allocateVirtualRegisters();
86
87     // Get/Set the operands/result of a bytecode instruction.
88     NodeIndex get(int operand)
89     {
90         // Is this a constant?
91         if (operand >= FirstConstantRegisterIndex) {
92             unsigned constant = operand - FirstConstantRegisterIndex;
93             ASSERT(constant < m_constants.size());
94             return getJSConstant(constant);
95         }
96
97         // Is this an argument?
98         if (operandIsArgument(operand))
99             return getArgument(operand);
100
101         // Must be a local.
102         return getLocal((unsigned)operand);
103     }
104     void set(int operand, NodeIndex value)
105     {
106         // Is this an argument?
107         if (operandIsArgument(operand)) {
108             setArgument(operand, value);
109             return;
110         }
111
112         // Must be a local.
113         setLocal((unsigned)operand, value);
114     }
115
116     // Used in implementing get/set, above, where the operand is a local variable.
117     NodeIndex getLocal(unsigned operand)
118     {
119         NodeIndex nodeIndex = m_currentBlock->m_locals[operand].value;
120
121         if (nodeIndex != NoNode) {
122             Node& node = m_graph[nodeIndex];
123             if (node.op == GetLocal)
124                 return nodeIndex;
125             ASSERT(node.op == SetLocal);
126             return node.child1();
127         }
128
129         // Check for reads of temporaries from prior blocks,
130         // expand m_preservedVars to cover these.
131         m_preservedVars = std::max(m_preservedVars, operand + 1);
132
133         NodeIndex phi = addToGraph(Phi);
134         m_localPhiStack.append(PhiStackEntry(m_currentBlock, phi, operand));
135         nodeIndex = addToGraph(GetLocal, OpInfo(operand), phi);
136         m_currentBlock->m_locals[operand].value = nodeIndex;
137         return nodeIndex;
138     }
139     void setLocal(unsigned operand, NodeIndex value)
140     {
141         m_currentBlock->m_locals[operand].value = addToGraph(SetLocal, OpInfo(operand), value);
142     }
143
144     // Used in implementing get/set, above, where the operand is an argument.
145     NodeIndex getArgument(unsigned operand)
146     {
147         unsigned argument = operand + m_codeBlock->m_numParameters + RegisterFile::CallFrameHeaderSize;
148         ASSERT(argument < m_numArguments);
149
150         NodeIndex nodeIndex = m_currentBlock->m_arguments[argument].value;
151
152         if (nodeIndex != NoNode) {
153             Node& node = m_graph[nodeIndex];
154             if (node.op == GetLocal)
155                 return nodeIndex;
156             ASSERT(node.op == SetLocal);
157             return node.child1();
158         }
159
160         NodeIndex phi = addToGraph(Phi);
161         m_argumentPhiStack.append(PhiStackEntry(m_currentBlock, phi, argument));
162         nodeIndex = addToGraph(GetLocal, OpInfo(operand), phi);
163         m_currentBlock->m_arguments[argument].value = nodeIndex;
164         return nodeIndex;
165     }
166     void setArgument(int operand, NodeIndex value)
167     {
168         unsigned argument = operand + m_codeBlock->m_numParameters + RegisterFile::CallFrameHeaderSize;
169         ASSERT(argument < m_numArguments);
170
171         m_currentBlock->m_arguments[argument].value = addToGraph(SetLocal, OpInfo(operand), value);
172     }
173
174     // Get an operand, and perform a ToInt32/ToNumber conversion on it.
175     NodeIndex getToInt32(int operand)
176     {
177         return toInt32(get(operand));
178     }
179     NodeIndex getToNumber(int operand)
180     {
181         return toNumber(get(operand));
182     }
183
184     // Perform an ES5 ToInt32 operation - returns a node of type NodeResultInt32.
185     NodeIndex toInt32(NodeIndex index)
186     {
187         Node& node = m_graph[index];
188
189         if (node.hasInt32Result())
190             return index;
191
192         if (node.op == UInt32ToNumber)
193             return node.child1();
194
195         // Check for numeric constants boxed as JSValues.
196         if (node.op == JSConstant) {
197             JSValue v = valueOfJSConstant(index);
198             if (v.isInt32())
199                 return getJSConstant(node.constantNumber());
200             // FIXME: We could convert the double ToInteger at this point.
201         }
202
203         return addToGraph(ValueToInt32, index);
204     }
205
206     // Perform an ES5 ToNumber operation - returns a node of type NodeResultDouble.
207     NodeIndex toNumber(NodeIndex index)
208     {
209         Node& node = m_graph[index];
210
211         if (node.hasNumberResult())
212             return index;
213
214         if (node.op == JSConstant) {
215             JSValue v = valueOfJSConstant(index);
216             if (v.isNumber())
217                 return getJSConstant(node.constantNumber());
218         }
219
220         return addToGraph(ValueToNumber, OpInfo(NodeUseBottom), index);
221     }
222
223     NodeIndex getJSConstant(unsigned constant)
224     {
225         NodeIndex index = m_constants[constant].asJSValue;
226         if (index != NoNode)
227             return index;
228
229         NodeIndex resultIndex = addToGraph(JSConstant, OpInfo(constant));
230         m_constants[constant].asJSValue = resultIndex;
231         return resultIndex;
232     }
233
234     // Helper functions to get/set the this value.
235     NodeIndex getThis()
236     {
237         return getArgument(m_codeBlock->thisRegister());
238     }
239     void setThis(NodeIndex value)
240     {
241         setArgument(m_codeBlock->thisRegister(), value);
242     }
243
244     // Convenience methods for checking nodes for constants.
245     bool isJSConstant(NodeIndex index)
246     {
247         return m_graph[index].op == JSConstant;
248     }
249     bool isInt32Constant(NodeIndex nodeIndex)
250     {
251         return isJSConstant(nodeIndex) && valueOfJSConstant(nodeIndex).isInt32();
252     }
253     bool isSmallInt32Constant(NodeIndex nodeIndex)
254     {
255         if (!isJSConstant(nodeIndex))
256             return false;
257         JSValue value = valueOfJSConstant(nodeIndex);
258         if (!value.isInt32())
259             return false;
260         int32_t intValue = value.asInt32();
261         return intValue >= -5 && intValue <= 5;
262     }
263     // Convenience methods for getting constant values.
264     JSValue valueOfJSConstant(NodeIndex index)
265     {
266         ASSERT(isJSConstant(index));
267         return m_codeBlock->getConstant(FirstConstantRegisterIndex + m_graph[index].constantNumber());
268     }
269     int32_t valueOfInt32Constant(NodeIndex nodeIndex)
270     {
271         ASSERT(isInt32Constant(nodeIndex));
272         return valueOfJSConstant(nodeIndex).asInt32();
273     }
274
275     // This method returns a JSConstant with the value 'undefined'.
276     NodeIndex constantUndefined()
277     {
278         // Has m_constantUndefined been set up yet?
279         if (m_constantUndefined == UINT_MAX) {
280             // Search the constant pool for undefined, if we find it, we can just reuse this!
281             unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters();
282             for (m_constantUndefined = 0; m_constantUndefined < numberOfConstants; ++m_constantUndefined) {
283                 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantUndefined);
284                 if (testMe.isUndefined())
285                     return getJSConstant(m_constantUndefined);
286             }
287
288             // Add undefined to the CodeBlock's constants, and add a corresponding slot in m_constants.
289             ASSERT(m_constants.size() == numberOfConstants);
290             m_codeBlock->addConstant(jsUndefined());
291             m_constants.append(ConstantRecord());
292             ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters());
293         }
294
295         // m_constantUndefined must refer to an entry in the CodeBlock's constant pool that has the value 'undefined'.
296         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantUndefined).isUndefined());
297         return getJSConstant(m_constantUndefined);
298     }
299
300     // This method returns a JSConstant with the value 'null'.
301     NodeIndex constantNull()
302     {
303         // Has m_constantNull been set up yet?
304         if (m_constantNull == UINT_MAX) {
305             // Search the constant pool for null, if we find it, we can just reuse this!
306             unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters();
307             for (m_constantNull = 0; m_constantNull < numberOfConstants; ++m_constantNull) {
308                 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNull);
309                 if (testMe.isNull())
310                     return getJSConstant(m_constantNull);
311             }
312
313             // Add null to the CodeBlock's constants, and add a corresponding slot in m_constants.
314             ASSERT(m_constants.size() == numberOfConstants);
315             m_codeBlock->addConstant(jsNull());
316             m_constants.append(ConstantRecord());
317             ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters());
318         }
319
320         // m_constantNull must refer to an entry in the CodeBlock's constant pool that has the value 'null'.
321         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNull).isNull());
322         return getJSConstant(m_constantNull);
323     }
324
325     // This method returns a DoubleConstant with the value 1.
326     NodeIndex one()
327     {
328         // Has m_constant1 been set up yet?
329         if (m_constant1 == UINT_MAX) {
330             // Search the constant pool for the value 1, if we find it, we can just reuse this!
331             unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters();
332             for (m_constant1 = 0; m_constant1 < numberOfConstants; ++m_constant1) {
333                 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1);
334                 if (testMe.isInt32() && testMe.asInt32() == 1)
335                     return getJSConstant(m_constant1);
336             }
337
338             // Add the value 1 to the CodeBlock's constants, and add a corresponding slot in m_constants.
339             ASSERT(m_constants.size() == numberOfConstants);
340             m_codeBlock->addConstant(jsNumber(1));
341             m_constants.append(ConstantRecord());
342             ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters());
343         }
344
345         // m_constant1 must refer to an entry in the CodeBlock's constant pool that has the integer value 1.
346         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1).isInt32());
347         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1).asInt32() == 1);
348         return getJSConstant(m_constant1);
349     }
350     
351     // This method returns a DoubleConstant with the value NaN.
352     NodeIndex constantNaN()
353     {
354         JSValue nan = jsNaN();
355         
356         // Has m_constantNaN been set up yet?
357         if (m_constantNaN == UINT_MAX) {
358             // Search the constant pool for the value NaN, if we find it, we can just reuse this!
359             unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters();
360             for (m_constantNaN = 0; m_constantNaN < numberOfConstants; ++m_constantNaN) {
361                 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNaN);
362                 if (JSValue::encode(testMe) == JSValue::encode(nan))
363                     return getJSConstant(m_constantNaN);
364             }
365
366             // Add the value nan to the CodeBlock's constants, and add a corresponding slot in m_constants.
367             ASSERT(m_constants.size() == numberOfConstants);
368             m_codeBlock->addConstant(nan);
369             m_constants.append(ConstantRecord());
370             ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters());
371         }
372
373         // m_constantNaN must refer to an entry in the CodeBlock's constant pool that has the value nan.
374         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNaN).isDouble());
375         ASSERT(isnan(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNaN).asDouble()));
376         return getJSConstant(m_constantNaN);
377     }
378     
379     CodeOrigin currentCodeOrigin()
380     {
381         return CodeOrigin(m_currentIndex);
382     }
383
384     // These methods create a node and add it to the graph. If nodes of this type are
385     // 'mustGenerate' then the node  will implicitly be ref'ed to ensure generation.
386     NodeIndex addToGraph(NodeType op, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
387     {
388         NodeIndex resultIndex = (NodeIndex)m_graph.size();
389         m_graph.append(Node(op, currentCodeOrigin(), child1, child2, child3));
390
391         if (op & NodeMustGenerate)
392             m_graph.ref(resultIndex);
393         return resultIndex;
394     }
395     NodeIndex addToGraph(NodeType op, OpInfo info, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
396     {
397         NodeIndex resultIndex = (NodeIndex)m_graph.size();
398         m_graph.append(Node(op, currentCodeOrigin(), info, child1, child2, child3));
399
400         if (op & NodeMustGenerate)
401             m_graph.ref(resultIndex);
402         return resultIndex;
403     }
404     NodeIndex addToGraph(NodeType op, OpInfo info1, OpInfo info2, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
405     {
406         NodeIndex resultIndex = (NodeIndex)m_graph.size();
407         m_graph.append(Node(op, currentCodeOrigin(), info1, info2, child1, child2, child3));
408
409         if (op & NodeMustGenerate)
410             m_graph.ref(resultIndex);
411         return resultIndex;
412     }
413     
414     NodeIndex addToGraph(Node::VarArgTag, NodeType op, OpInfo info1, OpInfo info2)
415     {
416         NodeIndex resultIndex = (NodeIndex)m_graph.size();
417         m_graph.append(Node(Node::VarArg, op, currentCodeOrigin(), info1, info2, m_graph.m_varArgChildren.size() - m_numPassedVarArgs, m_numPassedVarArgs));
418         
419         m_numPassedVarArgs = 0;
420         
421         if (op & NodeMustGenerate)
422             m_graph.ref(resultIndex);
423         return resultIndex;
424     }
425     void addVarArgChild(NodeIndex child)
426     {
427         m_graph.m_varArgChildren.append(child);
428         m_numPassedVarArgs++;
429     }
430     
431     NodeIndex addCall(Interpreter* interpreter, Instruction* currentInstruction, NodeType op)
432     {
433         Instruction* putInstruction = currentInstruction + OPCODE_LENGTH(op_call);
434
435         PredictedType prediction = PredictNone;
436         if (interpreter->getOpcodeID(putInstruction->u.opcode) == op_call_put_result)
437             prediction = getPrediction(m_graph.size(), m_currentIndex + OPCODE_LENGTH(op_call));
438         
439         addVarArgChild(get(currentInstruction[1].u.operand));
440         int argCount = currentInstruction[2].u.operand;
441         int registerOffset = currentInstruction[3].u.operand;
442         int firstArg = registerOffset - argCount - RegisterFile::CallFrameHeaderSize;
443         for (int argIdx = firstArg + (op == Construct ? 1 : 0); argIdx < firstArg + argCount; argIdx++)
444             addVarArgChild(get(argIdx));
445         NodeIndex call = addToGraph(Node::VarArg, op, OpInfo(0), OpInfo(prediction));
446         if (interpreter->getOpcodeID(putInstruction->u.opcode) == op_call_put_result)
447             set(putInstruction[1].u.operand, call);
448         if (RegisterFile::CallFrameHeaderSize + (unsigned)argCount > m_parameterSlots)
449             m_parameterSlots = RegisterFile::CallFrameHeaderSize + argCount;
450         return call;
451     }
452
453     PredictedType getPrediction(NodeIndex nodeIndex, unsigned bytecodeIndex)
454     {
455         UNUSED_PARAM(nodeIndex);
456         
457         ValueProfile* profile = m_profiledBlock->valueProfileForBytecodeOffset(bytecodeIndex);
458         ASSERT(profile);
459         PredictedType prediction = profile->computeUpdatedPrediction();
460 #if ENABLE(DFG_DEBUG_VERBOSE)
461         printf("Dynamic [@%u, bc#%u] prediction: %s\n", nodeIndex, bytecodeIndex, predictionToString(prediction));
462 #endif
463         
464         if (prediction == PredictNone) {
465             // We have no information about what values this node generates. Give up
466             // on executing this code, since we're likely to do more damage than good.
467             addToGraph(ForceOSRExit);
468         }
469         
470         return prediction;
471     }
472     
473     PredictedType getPrediction()
474     {
475         return getPrediction(m_graph.size(), m_currentIndex);
476     }
477
478     NodeIndex makeSafe(NodeIndex nodeIndex)
479     {
480         if (!m_profiledBlock->likelyToTakeSlowCase(m_currentIndex))
481             return nodeIndex;
482         
483 #if ENABLE(DFG_DEBUG_VERBOSE)
484         printf("Making %s @%u safe at bc#%u because slow-case counter is at %u\n", Graph::opName(m_graph[nodeIndex].op), nodeIndex, m_currentIndex, m_profiledBlock->rareCaseProfileForBytecodeOffset(m_currentIndex)->m_counter);
485 #endif
486         
487         switch (m_graph[nodeIndex].op) {
488         case UInt32ToNumber:
489         case ArithAdd:
490         case ArithSub:
491         case ValueAdd:
492         case ArithMod: // for ArithMode "MayOverflow" means we tried to divide by zero, or we saw double.
493             m_graph[nodeIndex].mergeArithNodeFlags(NodeMayOverflow);
494             break;
495             
496         case ArithMul:
497             if (m_profiledBlock->likelyToTakeDeepestSlowCase(m_currentIndex))
498                 m_graph[nodeIndex].mergeArithNodeFlags(NodeMayOverflow | NodeMayNegZero);
499             else
500                 m_graph[nodeIndex].mergeArithNodeFlags(NodeMayNegZero);
501             break;
502             
503         default:
504             ASSERT_NOT_REACHED();
505             break;
506         }
507         
508         return nodeIndex;
509     }
510     
511     NodeIndex makeDivSafe(NodeIndex nodeIndex)
512     {
513         ASSERT(m_graph[nodeIndex].op == ArithDiv);
514         
515         // The main slow case counter for op_div in the old JIT counts only when
516         // the operands are not numbers. We don't care about that since we already
517         // have speculations in place that take care of that separately. We only
518         // care about when the outcome of the division is not an integer, which
519         // is what the special fast case counter tells us.
520         
521         if (!m_profiledBlock->likelyToTakeSpecialFastCase(m_currentIndex))
522             return nodeIndex;
523         
524         m_graph[nodeIndex].mergeArithNodeFlags(NodeMayOverflow | NodeMayNegZero);
525         
526         return nodeIndex;
527     }
528     
529     JSGlobalData* m_globalData;
530     CodeBlock* m_codeBlock;
531     CodeBlock* m_profiledBlock;
532     Graph& m_graph;
533
534     // The current block being generated.
535     BasicBlock* m_currentBlock;
536     // The bytecode index of the current instruction being generated.
537     unsigned m_currentIndex;
538
539     // Record failures due to unimplemented functionality or regressions.
540     bool m_parseFailed;
541
542     // We use these values during code generation, and to avoid the need for
543     // special handling we make sure they are available as constants in the
544     // CodeBlock's constant pool. These variables are initialized to
545     // UINT_MAX, and lazily updated to hold an index into the CodeBlock's
546     // constant pool, as necessary.
547     unsigned m_constantUndefined;
548     unsigned m_constantNull;
549     unsigned m_constantNaN;
550     unsigned m_constant1;
551
552     // A constant in the constant pool may be represented by more than one
553     // node in the graph, depending on the context in which it is being used.
554     struct ConstantRecord {
555         ConstantRecord()
556             : asInt32(NoNode)
557             , asNumeric(NoNode)
558             , asJSValue(NoNode)
559         {
560         }
561
562         NodeIndex asInt32;
563         NodeIndex asNumeric;
564         NodeIndex asJSValue;
565     };
566
567     // Track the index of the node whose result is the current value for every
568     // register value in the bytecode - argument, local, and temporary.
569     Vector<ConstantRecord, 16> m_constants;
570
571     // The number of arguments passed to the function.
572     unsigned m_numArguments;
573     // The number of locals (vars + temporaries) used in the function.
574     unsigned m_numLocals;
575     // The number of registers we need to preserve across BasicBlock boundaries;
576     // typically equal to the number vars, but we expand this to cover all
577     // temporaries that persist across blocks (dues to ?:, &&, ||, etc).
578     unsigned m_preservedVars;
579     // The number of slots (in units of sizeof(Register)) that we need to
580     // preallocate for calls emanating from this frame. This includes the
581     // size of the CallFrame, only if this is not a leaf function.  (I.e.
582     // this is 0 if and only if this function is a leaf.)
583     unsigned m_parameterSlots;
584     // The number of var args passed to the next var arg node.
585     unsigned m_numPassedVarArgs;
586     // The index in the global resolve info.
587     unsigned m_globalResolveNumber;
588
589     struct PhiStackEntry {
590         PhiStackEntry(BasicBlock* block, NodeIndex phi, unsigned varNo)
591             : m_block(block)
592             , m_phi(phi)
593             , m_varNo(varNo)
594         {
595         }
596
597         BasicBlock* m_block;
598         NodeIndex m_phi;
599         unsigned m_varNo;
600     };
601     Vector<PhiStackEntry, 16> m_argumentPhiStack;
602     Vector<PhiStackEntry, 16> m_localPhiStack;
603     
604     Vector<Node*, 16> m_reusableNodeStack;
605 };
606
607 #define NEXT_OPCODE(name) \
608     m_currentIndex += OPCODE_LENGTH(name); \
609     continue
610
611 #define LAST_OPCODE(name) \
612     m_currentIndex += OPCODE_LENGTH(name); \
613     return !m_parseFailed
614
615 bool ByteCodeParser::handleMinMax(bool usesResult, int resultOperand, NodeType op, int firstArg, int lastArg)
616 {
617     if (!usesResult)
618         return true;
619
620     if (lastArg == firstArg) {
621         set(resultOperand, constantNaN());
622         return true;
623     }
624      
625     if (lastArg == firstArg + 1) {
626         set(resultOperand, getToNumber(firstArg + 1));
627         return true;
628     }
629     
630     if (lastArg == firstArg + 2) {
631         set(resultOperand, addToGraph(op, OpInfo(NodeUseBottom), getToNumber(firstArg + 1), getToNumber(firstArg + 2)));
632         return true;
633     }
634     
635     // Don't handle >=3 arguments for now.
636     return false;
637 }
638
639 bool ByteCodeParser::handleIntrinsic(bool usesResult, int resultOperand, Intrinsic intrinsic, int firstArg, int lastArg)
640 {
641     switch (intrinsic) {
642     case AbsIntrinsic: {
643         if (!usesResult) {
644             // There is no such thing as executing abs for effect, so this
645             // is dead code.
646             return true;
647         }
648         
649         // We don't care about the this argument. If we don't have a first
650         // argument then make this JSConstant(NaN).
651         int absArg = firstArg + 1;
652         if (absArg > lastArg)
653             set(resultOperand, constantNaN());
654         else
655             set(resultOperand, addToGraph(ArithAbs, OpInfo(NodeUseBottom), getToNumber(absArg)));
656         return true;
657     }
658         
659     case MinIntrinsic:
660         return handleMinMax(usesResult, resultOperand, ArithMin, firstArg, lastArg);
661         
662     case MaxIntrinsic:
663         return handleMinMax(usesResult, resultOperand, ArithMax, firstArg, lastArg);
664         
665     case SqrtIntrinsic: {
666         if (!usesResult)
667             return true;
668         
669         if (firstArg == lastArg) {
670             set(resultOperand, constantNaN());
671             return true;
672         }
673         
674         set(resultOperand, addToGraph(ArithSqrt, getToNumber(firstArg + 1)));
675         return true;
676     }
677         
678     default:
679         ASSERT(intrinsic == NoIntrinsic);
680         return false;
681     }
682 }
683
684 bool ByteCodeParser::parseBlock(unsigned limit)
685 {
686     // No need to reset state initially, since it has been set by the constructor.
687     if (m_currentIndex) {
688         for (unsigned i = 0; i < m_constants.size(); ++i)
689             m_constants[i] = ConstantRecord();
690     }
691
692     Interpreter* interpreter = m_globalData->interpreter;
693     Instruction* instructionsBegin = m_codeBlock->instructions().begin();
694     unsigned blockBegin = m_currentIndex;
695     while (true) {
696         // Don't extend over jump destinations.
697         if (m_currentIndex == limit) {
698             addToGraph(Jump, OpInfo(m_currentIndex));
699             return !m_parseFailed;
700         }
701         
702         // Switch on the current bytecode opcode.
703         Instruction* currentInstruction = instructionsBegin + m_currentIndex;
704         OpcodeID opcodeID = interpreter->getOpcodeID(currentInstruction->u.opcode);
705         switch (opcodeID) {
706
707         // === Function entry opcodes ===
708
709         case op_enter:
710             // Initialize all locals to undefined.
711             for (int i = 0; i < m_codeBlock->m_numVars; ++i)
712                 set(i, constantUndefined());
713             NEXT_OPCODE(op_enter);
714
715         case op_convert_this: {
716             NodeIndex op1 = getThis();
717             setThis(addToGraph(ConvertThis, op1));
718             NEXT_OPCODE(op_convert_this);
719         }
720
721         case op_create_this: {
722             NodeIndex op1 = get(currentInstruction[2].u.operand);
723             set(currentInstruction[1].u.operand, addToGraph(CreateThis, op1));
724             NEXT_OPCODE(op_create_this);
725         }
726             
727         case op_new_object: {
728             set(currentInstruction[1].u.operand, addToGraph(NewObject));
729             NEXT_OPCODE(op_new_object);
730         }
731             
732         case op_new_array: {
733             int startOperand = currentInstruction[2].u.operand;
734             int numOperands = currentInstruction[3].u.operand;
735             for (int operandIdx = startOperand; operandIdx < startOperand + numOperands; ++operandIdx)
736                 addVarArgChild(get(operandIdx));
737             set(currentInstruction[1].u.operand, addToGraph(Node::VarArg, NewArray, OpInfo(0), OpInfo(0)));
738             NEXT_OPCODE(op_new_array);
739         }
740             
741         case op_new_array_buffer: {
742             int startConstant = currentInstruction[2].u.operand;
743             int numConstants = currentInstruction[3].u.operand;
744             set(currentInstruction[1].u.operand, addToGraph(NewArrayBuffer, OpInfo(startConstant), OpInfo(numConstants)));
745             NEXT_OPCODE(op_new_array_buffer);
746         }
747             
748         case op_new_regexp: {
749             set(currentInstruction[1].u.operand, addToGraph(NewRegexp, OpInfo(currentInstruction[2].u.operand)));
750             NEXT_OPCODE(op_new_regexp);
751         }
752             
753         case op_get_callee: {
754             set(currentInstruction[1].u.operand, addToGraph(GetCallee));
755             NEXT_OPCODE(op_get_callee);
756         }
757
758         // === Bitwise operations ===
759
760         case op_bitand: {
761             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
762             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
763             set(currentInstruction[1].u.operand, addToGraph(BitAnd, op1, op2));
764             NEXT_OPCODE(op_bitand);
765         }
766
767         case op_bitor: {
768             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
769             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
770             set(currentInstruction[1].u.operand, addToGraph(BitOr, op1, op2));
771             NEXT_OPCODE(op_bitor);
772         }
773
774         case op_bitxor: {
775             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
776             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
777             set(currentInstruction[1].u.operand, addToGraph(BitXor, op1, op2));
778             NEXT_OPCODE(op_bitxor);
779         }
780
781         case op_rshift: {
782             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
783             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
784             NodeIndex result;
785             // Optimize out shifts by zero.
786             if (isInt32Constant(op2) && !(valueOfInt32Constant(op2) & 0x1f))
787                 result = op1;
788             else
789                 result = addToGraph(BitRShift, op1, op2);
790             set(currentInstruction[1].u.operand, result);
791             NEXT_OPCODE(op_rshift);
792         }
793
794         case op_lshift: {
795             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
796             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
797             NodeIndex result;
798             // Optimize out shifts by zero.
799             if (isInt32Constant(op2) && !(valueOfInt32Constant(op2) & 0x1f))
800                 result = op1;
801             else
802                 result = addToGraph(BitLShift, op1, op2);
803             set(currentInstruction[1].u.operand, result);
804             NEXT_OPCODE(op_lshift);
805         }
806
807         case op_urshift: {
808             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
809             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
810             NodeIndex result;
811             // The result of a zero-extending right shift is treated as an unsigned value.
812             // This means that if the top bit is set, the result is not in the int32 range,
813             // and as such must be stored as a double. If the shift amount is a constant,
814             // we may be able to optimize.
815             if (isInt32Constant(op2)) {
816                 // If we know we are shifting by a non-zero amount, then since the operation
817                 // zero fills we know the top bit of the result must be zero, and as such the
818                 // result must be within the int32 range. Conversely, if this is a shift by
819                 // zero, then the result may be changed by the conversion to unsigned, but it
820                 // is not necessary to perform the shift!
821                 if (valueOfInt32Constant(op2) & 0x1f)
822                     result = addToGraph(BitURShift, op1, op2);
823                 else
824                     result = makeSafe(addToGraph(UInt32ToNumber, OpInfo(NodeUseBottom), op1));
825             }  else {
826                 // Cannot optimize at this stage; shift & potentially rebox as a double.
827                 result = addToGraph(BitURShift, op1, op2);
828                 result = makeSafe(addToGraph(UInt32ToNumber, OpInfo(NodeUseBottom), result));
829             }
830             set(currentInstruction[1].u.operand, result);
831             NEXT_OPCODE(op_urshift);
832         }
833
834         // === Increment/Decrement opcodes ===
835
836         case op_pre_inc: {
837             unsigned srcDst = currentInstruction[1].u.operand;
838             NodeIndex op = getToNumber(srcDst);
839             set(srcDst, makeSafe(addToGraph(ArithAdd, OpInfo(NodeUseBottom), op, one())));
840             NEXT_OPCODE(op_pre_inc);
841         }
842
843         case op_post_inc: {
844             unsigned result = currentInstruction[1].u.operand;
845             unsigned srcDst = currentInstruction[2].u.operand;
846             NodeIndex op = getToNumber(srcDst);
847             set(result, op);
848             set(srcDst, makeSafe(addToGraph(ArithAdd, OpInfo(NodeUseBottom), op, one())));
849             NEXT_OPCODE(op_post_inc);
850         }
851
852         case op_pre_dec: {
853             unsigned srcDst = currentInstruction[1].u.operand;
854             NodeIndex op = getToNumber(srcDst);
855             set(srcDst, makeSafe(addToGraph(ArithSub, OpInfo(NodeUseBottom), op, one())));
856             NEXT_OPCODE(op_pre_dec);
857         }
858
859         case op_post_dec: {
860             unsigned result = currentInstruction[1].u.operand;
861             unsigned srcDst = currentInstruction[2].u.operand;
862             NodeIndex op = getToNumber(srcDst);
863             set(result, op);
864             set(srcDst, makeSafe(addToGraph(ArithSub, OpInfo(NodeUseBottom), op, one())));
865             NEXT_OPCODE(op_post_dec);
866         }
867
868         // === Arithmetic operations ===
869
870         case op_add: {
871             NodeIndex op1 = get(currentInstruction[2].u.operand);
872             NodeIndex op2 = get(currentInstruction[3].u.operand);
873             if (m_graph[op1].hasNumberResult() && m_graph[op2].hasNumberResult())
874                 set(currentInstruction[1].u.operand, makeSafe(addToGraph(ArithAdd, OpInfo(NodeUseBottom), toNumber(op1), toNumber(op2))));
875             else
876                 set(currentInstruction[1].u.operand, makeSafe(addToGraph(ValueAdd, OpInfo(NodeUseBottom), op1, op2)));
877             NEXT_OPCODE(op_add);
878         }
879
880         case op_sub: {
881             NodeIndex op1 = getToNumber(currentInstruction[2].u.operand);
882             NodeIndex op2 = getToNumber(currentInstruction[3].u.operand);
883             set(currentInstruction[1].u.operand, makeSafe(addToGraph(ArithSub, OpInfo(NodeUseBottom), op1, op2)));
884             NEXT_OPCODE(op_sub);
885         }
886
887         case op_mul: {
888             // Multiply requires that the inputs are not truncated, unfortunately.
889             NodeIndex op1 = getToNumber(currentInstruction[2].u.operand);
890             NodeIndex op2 = getToNumber(currentInstruction[3].u.operand);
891             set(currentInstruction[1].u.operand, makeSafe(addToGraph(ArithMul, OpInfo(NodeUseBottom), op1, op2)));
892             NEXT_OPCODE(op_mul);
893         }
894
895         case op_mod: {
896             NodeIndex op1 = getToNumber(currentInstruction[2].u.operand);
897             NodeIndex op2 = getToNumber(currentInstruction[3].u.operand);
898             set(currentInstruction[1].u.operand, makeSafe(addToGraph(ArithMod, OpInfo(NodeUseBottom), op1, op2)));
899             NEXT_OPCODE(op_mod);
900         }
901
902         case op_div: {
903             NodeIndex op1 = getToNumber(currentInstruction[2].u.operand);
904             NodeIndex op2 = getToNumber(currentInstruction[3].u.operand);
905             set(currentInstruction[1].u.operand, makeDivSafe(addToGraph(ArithDiv, OpInfo(NodeUseBottom), op1, op2)));
906             NEXT_OPCODE(op_div);
907         }
908
909         // === Misc operations ===
910
911 #if ENABLE(DEBUG_WITH_BREAKPOINT)
912         case op_debug:
913             addToGraph(Breakpoint);
914             NEXT_OPCODE(op_debug);
915 #endif
916         case op_mov: {
917             NodeIndex op = get(currentInstruction[2].u.operand);
918             set(currentInstruction[1].u.operand, op);
919             NEXT_OPCODE(op_mov);
920         }
921
922         case op_check_has_instance:
923             addToGraph(CheckHasInstance, get(currentInstruction[1].u.operand));
924             NEXT_OPCODE(op_check_has_instance);
925
926         case op_instanceof: {
927             NodeIndex value = get(currentInstruction[2].u.operand);
928             NodeIndex baseValue = get(currentInstruction[3].u.operand);
929             NodeIndex prototype = get(currentInstruction[4].u.operand);
930             set(currentInstruction[1].u.operand, addToGraph(InstanceOf, value, baseValue, prototype));
931             NEXT_OPCODE(op_instanceof);
932         }
933
934         case op_not: {
935             NodeIndex value = get(currentInstruction[2].u.operand);
936             set(currentInstruction[1].u.operand, addToGraph(LogicalNot, value));
937             NEXT_OPCODE(op_not);
938         }
939             
940         case op_to_primitive: {
941             NodeIndex value = get(currentInstruction[2].u.operand);
942             set(currentInstruction[1].u.operand, addToGraph(ToPrimitive, value));
943             NEXT_OPCODE(op_to_primitive);
944         }
945             
946         case op_strcat: {
947             int startOperand = currentInstruction[2].u.operand;
948             int numOperands = currentInstruction[3].u.operand;
949             for (int operandIdx = startOperand; operandIdx < startOperand + numOperands; ++operandIdx)
950                 addVarArgChild(get(operandIdx));
951             set(currentInstruction[1].u.operand, addToGraph(Node::VarArg, StrCat, OpInfo(0), OpInfo(0)));
952             NEXT_OPCODE(op_strcat);
953         }
954
955         case op_less: {
956             NodeIndex op1 = get(currentInstruction[2].u.operand);
957             NodeIndex op2 = get(currentInstruction[3].u.operand);
958             set(currentInstruction[1].u.operand, addToGraph(CompareLess, op1, op2));
959             NEXT_OPCODE(op_less);
960         }
961
962         case op_lesseq: {
963             NodeIndex op1 = get(currentInstruction[2].u.operand);
964             NodeIndex op2 = get(currentInstruction[3].u.operand);
965             set(currentInstruction[1].u.operand, addToGraph(CompareLessEq, op1, op2));
966             NEXT_OPCODE(op_lesseq);
967         }
968
969         case op_greater: {
970             NodeIndex op1 = get(currentInstruction[2].u.operand);
971             NodeIndex op2 = get(currentInstruction[3].u.operand);
972             set(currentInstruction[1].u.operand, addToGraph(CompareGreater, op1, op2));
973             NEXT_OPCODE(op_greater);
974         }
975
976         case op_greatereq: {
977             NodeIndex op1 = get(currentInstruction[2].u.operand);
978             NodeIndex op2 = get(currentInstruction[3].u.operand);
979             set(currentInstruction[1].u.operand, addToGraph(CompareGreaterEq, op1, op2));
980             NEXT_OPCODE(op_greatereq);
981         }
982
983         case op_eq: {
984             NodeIndex op1 = get(currentInstruction[2].u.operand);
985             NodeIndex op2 = get(currentInstruction[3].u.operand);
986             set(currentInstruction[1].u.operand, addToGraph(CompareEq, op1, op2));
987             NEXT_OPCODE(op_eq);
988         }
989
990         case op_eq_null: {
991             NodeIndex value = get(currentInstruction[2].u.operand);
992             set(currentInstruction[1].u.operand, addToGraph(CompareEq, value, constantNull()));
993             NEXT_OPCODE(op_eq_null);
994         }
995
996         case op_stricteq: {
997             NodeIndex op1 = get(currentInstruction[2].u.operand);
998             NodeIndex op2 = get(currentInstruction[3].u.operand);
999             set(currentInstruction[1].u.operand, addToGraph(CompareStrictEq, op1, op2));
1000             NEXT_OPCODE(op_stricteq);
1001         }
1002
1003         case op_neq: {
1004             NodeIndex op1 = get(currentInstruction[2].u.operand);
1005             NodeIndex op2 = get(currentInstruction[3].u.operand);
1006             set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareEq, op1, op2)));
1007             NEXT_OPCODE(op_neq);
1008         }
1009
1010         case op_neq_null: {
1011             NodeIndex value = get(currentInstruction[2].u.operand);
1012             set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareEq, value, constantNull())));
1013             NEXT_OPCODE(op_neq_null);
1014         }
1015
1016         case op_nstricteq: {
1017             NodeIndex op1 = get(currentInstruction[2].u.operand);
1018             NodeIndex op2 = get(currentInstruction[3].u.operand);
1019             set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareStrictEq, op1, op2)));
1020             NEXT_OPCODE(op_nstricteq);
1021         }
1022
1023         // === Property access operations ===
1024
1025         case op_get_by_val: {
1026             PredictedType prediction = getPrediction();
1027             
1028             NodeIndex base = get(currentInstruction[2].u.operand);
1029             NodeIndex property = get(currentInstruction[3].u.operand);
1030
1031             NodeIndex getByVal = addToGraph(GetByVal, OpInfo(0), OpInfo(prediction), base, property);
1032             set(currentInstruction[1].u.operand, getByVal);
1033
1034             NEXT_OPCODE(op_get_by_val);
1035         }
1036
1037         case op_put_by_val: {
1038             NodeIndex base = get(currentInstruction[1].u.operand);
1039             NodeIndex property = get(currentInstruction[2].u.operand);
1040             NodeIndex value = get(currentInstruction[3].u.operand);
1041
1042             addToGraph(PutByVal, base, property, value);
1043
1044             NEXT_OPCODE(op_put_by_val);
1045         }
1046             
1047         case op_method_check: {
1048             Instruction* getInstruction = currentInstruction + OPCODE_LENGTH(op_method_check);
1049             
1050             PredictedType prediction = getPrediction();
1051             
1052             ASSERT(interpreter->getOpcodeID(getInstruction->u.opcode) == op_get_by_id);
1053             
1054             NodeIndex base = get(getInstruction[2].u.operand);
1055             unsigned identifier = getInstruction[3].u.operand;
1056                 
1057             // Check if the method_check was monomorphic. If so, emit a CheckXYZMethod
1058             // node, which is a lot more efficient.
1059             StructureStubInfo& stubInfo = m_profiledBlock->getStubInfo(m_currentIndex);
1060             MethodCallLinkInfo& methodCall = m_profiledBlock->getMethodCallLinkInfo(m_currentIndex);
1061             
1062             if (methodCall.seen && !!methodCall.cachedStructure && !stubInfo.seen) {
1063                 // It's monomorphic as far as we can tell, since the method_check was linked
1064                 // but the slow path (i.e. the normal get_by_id) never fired.
1065             
1066                 NodeIndex checkMethod = addToGraph(CheckMethod, OpInfo(identifier), OpInfo(m_graph.m_methodCheckData.size()), base);
1067                 set(getInstruction[1].u.operand, checkMethod);
1068                 
1069                 MethodCheckData methodCheckData;
1070                 methodCheckData.structure = methodCall.cachedStructure.get();
1071                 methodCheckData.prototypeStructure = methodCall.cachedPrototypeStructure.get();
1072                 methodCheckData.function = methodCall.cachedFunction.get();
1073                 methodCheckData.prototype = methodCall.cachedPrototype.get();
1074                 m_graph.m_methodCheckData.append(methodCheckData);
1075             } else {
1076                 NodeIndex getMethod = addToGraph(GetMethod, OpInfo(identifier), OpInfo(prediction), base);
1077                 set(getInstruction[1].u.operand, getMethod);
1078             }
1079             
1080             m_currentIndex += OPCODE_LENGTH(op_method_check) + OPCODE_LENGTH(op_get_by_id);
1081             continue;
1082         }
1083         case op_get_scoped_var: {
1084             PredictedType prediction = getPrediction();
1085             int dst = currentInstruction[1].u.operand;
1086             int slot = currentInstruction[2].u.operand;
1087             int depth = currentInstruction[3].u.operand;
1088             NodeIndex getScopeChain = addToGraph(GetScopeChain, OpInfo(depth));
1089             NodeIndex getScopedVar = addToGraph(GetScopedVar, OpInfo(slot), OpInfo(prediction), getScopeChain);
1090             set(dst, getScopedVar);
1091             NEXT_OPCODE(op_get_scoped_var);
1092         }
1093         case op_put_scoped_var: {
1094             int slot = currentInstruction[1].u.operand;
1095             int depth = currentInstruction[2].u.operand;
1096             int source = currentInstruction[3].u.operand;
1097             NodeIndex getScopeChain = addToGraph(GetScopeChain, OpInfo(depth));
1098             addToGraph(PutScopedVar, OpInfo(slot), getScopeChain, get(source));
1099             NEXT_OPCODE(op_put_scoped_var);
1100         }
1101         case op_get_by_id: {
1102             PredictedType prediction = getPrediction();
1103             
1104             NodeIndex base = get(currentInstruction[2].u.operand);
1105             unsigned identifierNumber = currentInstruction[3].u.operand;
1106             
1107             StructureStubInfo& stubInfo = m_profiledBlock->getStubInfo(m_currentIndex);
1108             
1109             NodeIndex getById = NoNode;
1110             if (stubInfo.seen && stubInfo.accessType == access_get_by_id_self) {
1111                 Structure* structure = stubInfo.u.getByIdSelf.baseObjectStructure.get();
1112                 Identifier identifier = m_codeBlock->identifier(identifierNumber);
1113                 size_t offset = structure->get(*m_globalData, identifier);
1114                 
1115                 if (offset != notFound) {
1116                     getById = addToGraph(GetByOffset, OpInfo(m_graph.m_storageAccessData.size()), OpInfo(prediction), addToGraph(CheckStructure, OpInfo(structure), base));
1117                     
1118                     StorageAccessData storageAccessData;
1119                     storageAccessData.offset = offset;
1120                     storageAccessData.identifierNumber = identifierNumber;
1121                     m_graph.m_storageAccessData.append(storageAccessData);
1122                 }
1123             }
1124             
1125             if (getById == NoNode)
1126                 getById = addToGraph(GetById, OpInfo(identifierNumber), OpInfo(prediction), base);
1127             
1128             set(currentInstruction[1].u.operand, getById);
1129
1130             NEXT_OPCODE(op_get_by_id);
1131         }
1132
1133         case op_put_by_id: {
1134             NodeIndex value = get(currentInstruction[3].u.operand);
1135             NodeIndex base = get(currentInstruction[1].u.operand);
1136             unsigned identifier = currentInstruction[2].u.operand;
1137             bool direct = currentInstruction[8].u.operand;
1138
1139             if (direct)
1140                 addToGraph(PutByIdDirect, OpInfo(identifier), base, value);
1141             else
1142                 addToGraph(PutById, OpInfo(identifier), base, value);
1143
1144             NEXT_OPCODE(op_put_by_id);
1145         }
1146
1147         case op_get_global_var: {
1148             PredictedType prediction = getPrediction();
1149             
1150             NodeIndex getGlobalVar = addToGraph(GetGlobalVar, OpInfo(currentInstruction[2].u.operand));
1151             set(currentInstruction[1].u.operand, getGlobalVar);
1152             m_graph.predictGlobalVar(currentInstruction[2].u.operand, prediction);
1153             NEXT_OPCODE(op_get_global_var);
1154         }
1155
1156         case op_put_global_var: {
1157             NodeIndex value = get(currentInstruction[2].u.operand);
1158             addToGraph(PutGlobalVar, OpInfo(currentInstruction[1].u.operand), value);
1159             NEXT_OPCODE(op_put_global_var);
1160         }
1161
1162         // === Block terminators. ===
1163
1164         case op_jmp: {
1165             unsigned relativeOffset = currentInstruction[1].u.operand;
1166             addToGraph(Jump, OpInfo(m_currentIndex + relativeOffset));
1167             LAST_OPCODE(op_jmp);
1168         }
1169
1170         case op_loop: {
1171             unsigned relativeOffset = currentInstruction[1].u.operand;
1172             addToGraph(Jump, OpInfo(m_currentIndex + relativeOffset));
1173             LAST_OPCODE(op_loop);
1174         }
1175
1176         case op_jtrue: {
1177             unsigned relativeOffset = currentInstruction[2].u.operand;
1178             NodeIndex condition = get(currentInstruction[1].u.operand);
1179             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jtrue)), condition);
1180             LAST_OPCODE(op_jtrue);
1181         }
1182
1183         case op_jfalse: {
1184             unsigned relativeOffset = currentInstruction[2].u.operand;
1185             NodeIndex condition = get(currentInstruction[1].u.operand);
1186             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jfalse)), OpInfo(m_currentIndex + relativeOffset), condition);
1187             LAST_OPCODE(op_jfalse);
1188         }
1189
1190         case op_loop_if_true: {
1191             unsigned relativeOffset = currentInstruction[2].u.operand;
1192             NodeIndex condition = get(currentInstruction[1].u.operand);
1193             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_true)), condition);
1194             LAST_OPCODE(op_loop_if_true);
1195         }
1196
1197         case op_loop_if_false: {
1198             unsigned relativeOffset = currentInstruction[2].u.operand;
1199             NodeIndex condition = get(currentInstruction[1].u.operand);
1200             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_false)), OpInfo(m_currentIndex + relativeOffset), condition);
1201             LAST_OPCODE(op_loop_if_false);
1202         }
1203
1204         case op_jeq_null: {
1205             unsigned relativeOffset = currentInstruction[2].u.operand;
1206             NodeIndex value = get(currentInstruction[1].u.operand);
1207             NodeIndex condition = addToGraph(CompareEq, value, constantNull());
1208             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jeq_null)), condition);
1209             LAST_OPCODE(op_jeq_null);
1210         }
1211
1212         case op_jneq_null: {
1213             unsigned relativeOffset = currentInstruction[2].u.operand;
1214             NodeIndex value = get(currentInstruction[1].u.operand);
1215             NodeIndex condition = addToGraph(CompareEq, value, constantNull());
1216             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jneq_null)), OpInfo(m_currentIndex + relativeOffset), condition);
1217             LAST_OPCODE(op_jneq_null);
1218         }
1219
1220         case op_jless: {
1221             unsigned relativeOffset = currentInstruction[3].u.operand;
1222             NodeIndex op1 = get(currentInstruction[1].u.operand);
1223             NodeIndex op2 = get(currentInstruction[2].u.operand);
1224             NodeIndex condition = addToGraph(CompareLess, op1, op2);
1225             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jless)), condition);
1226             LAST_OPCODE(op_jless);
1227         }
1228
1229         case op_jlesseq: {
1230             unsigned relativeOffset = currentInstruction[3].u.operand;
1231             NodeIndex op1 = get(currentInstruction[1].u.operand);
1232             NodeIndex op2 = get(currentInstruction[2].u.operand);
1233             NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
1234             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jlesseq)), condition);
1235             LAST_OPCODE(op_jlesseq);
1236         }
1237
1238         case op_jgreater: {
1239             unsigned relativeOffset = currentInstruction[3].u.operand;
1240             NodeIndex op1 = get(currentInstruction[1].u.operand);
1241             NodeIndex op2 = get(currentInstruction[2].u.operand);
1242             NodeIndex condition = addToGraph(CompareGreater, op1, op2);
1243             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jgreater)), condition);
1244             LAST_OPCODE(op_jgreater);
1245         }
1246
1247         case op_jgreatereq: {
1248             unsigned relativeOffset = currentInstruction[3].u.operand;
1249             NodeIndex op1 = get(currentInstruction[1].u.operand);
1250             NodeIndex op2 = get(currentInstruction[2].u.operand);
1251             NodeIndex condition = addToGraph(CompareGreaterEq, op1, op2);
1252             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jgreatereq)), condition);
1253             LAST_OPCODE(op_jgreatereq);
1254         }
1255
1256         case op_jnless: {
1257             unsigned relativeOffset = currentInstruction[3].u.operand;
1258             NodeIndex op1 = get(currentInstruction[1].u.operand);
1259             NodeIndex op2 = get(currentInstruction[2].u.operand);
1260             NodeIndex condition = addToGraph(CompareLess, op1, op2);
1261             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jnless)), OpInfo(m_currentIndex + relativeOffset), condition);
1262             LAST_OPCODE(op_jnless);
1263         }
1264
1265         case op_jnlesseq: {
1266             unsigned relativeOffset = currentInstruction[3].u.operand;
1267             NodeIndex op1 = get(currentInstruction[1].u.operand);
1268             NodeIndex op2 = get(currentInstruction[2].u.operand);
1269             NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
1270             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jnlesseq)), OpInfo(m_currentIndex + relativeOffset), condition);
1271             LAST_OPCODE(op_jnlesseq);
1272         }
1273
1274         case op_jngreater: {
1275             unsigned relativeOffset = currentInstruction[3].u.operand;
1276             NodeIndex op1 = get(currentInstruction[1].u.operand);
1277             NodeIndex op2 = get(currentInstruction[2].u.operand);
1278             NodeIndex condition = addToGraph(CompareGreater, op1, op2);
1279             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jngreater)), OpInfo(m_currentIndex + relativeOffset), condition);
1280             LAST_OPCODE(op_jngreater);
1281         }
1282
1283         case op_jngreatereq: {
1284             unsigned relativeOffset = currentInstruction[3].u.operand;
1285             NodeIndex op1 = get(currentInstruction[1].u.operand);
1286             NodeIndex op2 = get(currentInstruction[2].u.operand);
1287             NodeIndex condition = addToGraph(CompareGreaterEq, op1, op2);
1288             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jngreatereq)), OpInfo(m_currentIndex + relativeOffset), condition);
1289             LAST_OPCODE(op_jngreatereq);
1290         }
1291
1292         case op_loop_if_less: {
1293             unsigned relativeOffset = currentInstruction[3].u.operand;
1294             NodeIndex op1 = get(currentInstruction[1].u.operand);
1295             NodeIndex op2 = get(currentInstruction[2].u.operand);
1296             NodeIndex condition = addToGraph(CompareLess, op1, op2);
1297             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_less)), condition);
1298             LAST_OPCODE(op_loop_if_less);
1299         }
1300
1301         case op_loop_if_lesseq: {
1302             unsigned relativeOffset = currentInstruction[3].u.operand;
1303             NodeIndex op1 = get(currentInstruction[1].u.operand);
1304             NodeIndex op2 = get(currentInstruction[2].u.operand);
1305             NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
1306             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_lesseq)), condition);
1307             LAST_OPCODE(op_loop_if_lesseq);
1308         }
1309
1310         case op_loop_if_greater: {
1311             unsigned relativeOffset = currentInstruction[3].u.operand;
1312             NodeIndex op1 = get(currentInstruction[1].u.operand);
1313             NodeIndex op2 = get(currentInstruction[2].u.operand);
1314             NodeIndex condition = addToGraph(CompareGreater, op1, op2);
1315             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_greater)), condition);
1316             LAST_OPCODE(op_loop_if_greater);
1317         }
1318
1319         case op_loop_if_greatereq: {
1320             unsigned relativeOffset = currentInstruction[3].u.operand;
1321             NodeIndex op1 = get(currentInstruction[1].u.operand);
1322             NodeIndex op2 = get(currentInstruction[2].u.operand);
1323             NodeIndex condition = addToGraph(CompareGreaterEq, op1, op2);
1324             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_greatereq)), condition);
1325             LAST_OPCODE(op_loop_if_greatereq);
1326         }
1327
1328         case op_ret:
1329             addToGraph(Return, get(currentInstruction[1].u.operand));
1330             LAST_OPCODE(op_ret);
1331             
1332         case op_end:
1333             addToGraph(Return, get(currentInstruction[1].u.operand));
1334             LAST_OPCODE(op_end);
1335
1336         case op_throw:
1337             addToGraph(Throw, get(currentInstruction[1].u.operand));
1338             LAST_OPCODE(op_throw);
1339             
1340         case op_throw_reference_error:
1341             addToGraph(ThrowReferenceError);
1342             LAST_OPCODE(op_throw_reference_error);
1343             
1344 #if USE(JSVALUE64)
1345         case op_call: {
1346             NodeIndex callTarget = get(currentInstruction[1].u.operand);
1347             if (m_graph.isFunctionConstant(m_codeBlock, callTarget)) {
1348                 int argCount = currentInstruction[2].u.operand;
1349                 int registerOffset = currentInstruction[3].u.operand;
1350                 int firstArg = registerOffset - argCount - RegisterFile::CallFrameHeaderSize;
1351                 int lastArg = firstArg + argCount - 1;
1352                 
1353                 // Do we have a result?
1354                 bool usesResult = false;
1355                 int resultOperand = 0; // make compiler happy
1356                 Instruction* putInstruction = currentInstruction + OPCODE_LENGTH(op_call);
1357                 if (interpreter->getOpcodeID(putInstruction->u.opcode) == op_call_put_result) {
1358                     resultOperand = putInstruction[1].u.operand;
1359                     usesResult = true;
1360                 }
1361                 
1362                 DFG::Intrinsic intrinsic = m_graph.valueOfFunctionConstant(m_codeBlock, callTarget)->executable()->intrinsic();
1363                 
1364                 if (handleIntrinsic(usesResult, resultOperand, intrinsic, firstArg, lastArg)) {
1365                     // NEXT_OPCODE() has to be inside braces.
1366                     NEXT_OPCODE(op_call);
1367                 }
1368             }
1369             
1370             addCall(interpreter, currentInstruction, Call);
1371             NEXT_OPCODE(op_call);
1372         }
1373             
1374         case op_construct: {
1375             addCall(interpreter, currentInstruction, Construct);
1376             NEXT_OPCODE(op_construct);
1377         }
1378 #endif
1379             
1380         case op_call_put_result:
1381             NEXT_OPCODE(op_call_put_result);
1382
1383         case op_resolve: {
1384             PredictedType prediction = getPrediction();
1385             
1386             unsigned identifier = currentInstruction[2].u.operand;
1387
1388             NodeIndex resolve = addToGraph(Resolve, OpInfo(identifier), OpInfo(prediction));
1389             set(currentInstruction[1].u.operand, resolve);
1390
1391             NEXT_OPCODE(op_resolve);
1392         }
1393
1394         case op_resolve_base: {
1395             PredictedType prediction = getPrediction();
1396             
1397             unsigned identifier = currentInstruction[2].u.operand;
1398
1399             NodeIndex resolve = addToGraph(currentInstruction[3].u.operand ? ResolveBaseStrictPut : ResolveBase, OpInfo(identifier), OpInfo(prediction));
1400             set(currentInstruction[1].u.operand, resolve);
1401
1402             NEXT_OPCODE(op_resolve_base);
1403         }
1404             
1405         case op_resolve_global: {
1406             PredictedType prediction = getPrediction();
1407             
1408             NodeIndex resolve = addToGraph(ResolveGlobal, OpInfo(m_graph.m_resolveGlobalData.size()), OpInfo(prediction));
1409             m_graph.m_resolveGlobalData.append(ResolveGlobalData());
1410             ResolveGlobalData& data = m_graph.m_resolveGlobalData.last();
1411             data.identifierNumber = currentInstruction[2].u.operand;
1412             data.resolveInfoIndex = m_globalResolveNumber++;
1413             set(currentInstruction[1].u.operand, resolve);
1414
1415             NEXT_OPCODE(op_resolve_global);
1416         }
1417
1418         case op_loop_hint: {
1419             // Baseline->DFG OSR jumps between loop hints. The DFG assumes that Baseline->DFG
1420             // OSR can only happen at basic block boundaries. Assert that these two statements
1421             // are compatible.
1422             ASSERT_UNUSED(blockBegin, m_currentIndex == blockBegin);
1423             
1424             m_currentBlock->isOSRTarget = true;
1425             
1426             NEXT_OPCODE(op_loop_hint);
1427         }
1428
1429         default:
1430             // Parse failed! This should not happen because the capabilities checker
1431             // should have caught it.
1432             ASSERT_NOT_REACHED();
1433             return false;
1434         }
1435         
1436         ASSERT(canCompileOpcode(opcodeID));
1437     }
1438 }
1439
1440 template<ByteCodeParser::PhiStackType stackType>
1441 void ByteCodeParser::processPhiStack()
1442 {
1443     Vector<PhiStackEntry, 16>& phiStack = (stackType == ArgumentPhiStack) ? m_argumentPhiStack : m_localPhiStack;
1444
1445     while (!phiStack.isEmpty()) {
1446         PhiStackEntry entry = phiStack.last();
1447         phiStack.removeLast();
1448         
1449         PredecessorList& predecessors = entry.m_block->m_predecessors;
1450         unsigned varNo = entry.m_varNo;
1451
1452         for (size_t i = 0; i < predecessors.size(); ++i) {
1453             BasicBlock* predecessorBlock = m_graph.m_blocks[predecessors[i]].get();
1454
1455             VariableRecord& var = (stackType == ArgumentPhiStack) ? predecessorBlock->m_arguments[varNo] : predecessorBlock->m_locals[varNo];
1456
1457             NodeIndex valueInPredecessor = var.value;
1458             if (valueInPredecessor == NoNode) {
1459                 valueInPredecessor = addToGraph(Phi);
1460                 var.value = valueInPredecessor;
1461                 phiStack.append(PhiStackEntry(predecessorBlock, valueInPredecessor, varNo));
1462             } else if (m_graph[valueInPredecessor].op == GetLocal)
1463                 valueInPredecessor = m_graph[valueInPredecessor].child1();
1464             ASSERT(m_graph[valueInPredecessor].op == SetLocal || m_graph[valueInPredecessor].op == Phi);
1465
1466             Node* phiNode = &m_graph[entry.m_phi];
1467             if (phiNode->refCount())
1468                 m_graph.ref(valueInPredecessor);
1469
1470             if (phiNode->child1() == NoNode) {
1471                 phiNode->children.fixed.child1 = valueInPredecessor;
1472                 continue;
1473             }
1474             if (phiNode->child2() == NoNode) {
1475                 phiNode->children.fixed.child2 = valueInPredecessor;
1476                 continue;
1477             }
1478             if (phiNode->child3() == NoNode) {
1479                 phiNode->children.fixed.child3 = valueInPredecessor;
1480                 continue;
1481             }
1482
1483             NodeIndex newPhi = addToGraph(Phi);
1484             
1485             phiNode = &m_graph[entry.m_phi]; // reload after vector resize
1486             Node& newPhiNode = m_graph[newPhi];
1487             if (phiNode->refCount())
1488                 m_graph.ref(newPhi);
1489
1490             newPhiNode.children.fixed.child1 = phiNode->child1();
1491             newPhiNode.children.fixed.child2 = phiNode->child2();
1492             newPhiNode.children.fixed.child3 = phiNode->child3();
1493
1494             phiNode->children.fixed.child1 = newPhi;
1495             phiNode->children.fixed.child1 = valueInPredecessor;
1496             phiNode->children.fixed.child3 = NoNode;
1497         }
1498     }
1499 }
1500
1501 void ByteCodeParser::setupPredecessors()
1502 {
1503     for (BlockIndex index = 0; index < m_graph.m_blocks.size(); ++index) {
1504         BasicBlock* block = m_graph.m_blocks[index].get();
1505         ASSERT(block->end != NoNode);
1506         Node& node = m_graph[block->end - 1];
1507         ASSERT(node.isTerminal());
1508
1509         if (node.isJump())
1510             m_graph.blockForBytecodeOffset(node.takenBytecodeOffset()).m_predecessors.append(index);
1511         else if (node.isBranch()) {
1512             m_graph.blockForBytecodeOffset(node.takenBytecodeOffset()).m_predecessors.append(index);
1513             m_graph.blockForBytecodeOffset(node.notTakenBytecodeOffset()).m_predecessors.append(index);
1514         }
1515     }
1516 }
1517
1518 bool ByteCodeParser::parse()
1519 {
1520     // Set during construction.
1521     ASSERT(!m_currentIndex);
1522
1523     for (unsigned jumpTargetIndex = 0; jumpTargetIndex <= m_codeBlock->numberOfJumpTargets(); ++jumpTargetIndex) {
1524         // The maximum bytecode offset to go into the current basicblock is either the next jump target, or the end of the instructions.
1525         unsigned limit = jumpTargetIndex < m_codeBlock->numberOfJumpTargets() ? m_codeBlock->jumpTarget(jumpTargetIndex) : m_codeBlock->instructions().size();
1526         ASSERT(m_currentIndex < limit);
1527
1528         // Loop until we reach the current limit (i.e. next jump target).
1529         do {
1530             OwnPtr<BasicBlock> block = adoptPtr(new BasicBlock(m_currentIndex, m_graph.size(), m_numArguments, m_numLocals));
1531             m_currentBlock = block.get();
1532             m_graph.m_blocks.append(block.release());
1533
1534             if (!parseBlock(limit))
1535                 return false;
1536             // We should not have gone beyond the limit.
1537             ASSERT(m_currentIndex <= limit);
1538
1539             m_currentBlock->end = m_graph.size();
1540         } while (m_currentIndex < limit);
1541     }
1542
1543     // Should have reached the end of the instructions.
1544     ASSERT(m_currentIndex == m_codeBlock->instructions().size());
1545
1546     setupPredecessors();
1547     processPhiStack<LocalPhiStack>();
1548     processPhiStack<ArgumentPhiStack>();
1549     
1550     m_graph.m_preservedVars = m_preservedVars;
1551     m_graph.m_parameterSlots = m_parameterSlots;
1552
1553     return true;
1554 }
1555
1556 bool parse(Graph& graph, JSGlobalData* globalData, CodeBlock* codeBlock)
1557 {
1558 #if DFG_DEBUG_LOCAL_DISBALE
1559     UNUSED_PARAM(graph);
1560     UNUSED_PARAM(globalData);
1561     UNUSED_PARAM(codeBlock);
1562     return false;
1563 #else
1564     return ByteCodeParser(globalData, codeBlock, codeBlock->alternative(), graph).parse();
1565 #endif
1566 }
1567
1568 } } // namespace JSC::DFG
1569
1570 #endif