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