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