https://bugs.webkit.org/show_bug.cgi?id=63218
[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     {
66     }
67
68     // Parse a full CodeBlock of bytecode.
69     bool parse();
70
71 private:
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 prediction = PredictNone)
104     {
105         m_graph.predict(operand, prediction);
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             if (v.isNumber())
202                 return getJSConstant(node.constantNumber());
203         }
204
205         return addToGraph(ValueToInt32, index);
206     }
207
208     // Perform an ES5 ToNumber operation - returns a node of type NodeResultDouble.
209     NodeIndex toNumber(NodeIndex index)
210     {
211         Node& node = m_graph[index];
212
213         if (node.hasDoubleResult() || node.hasInt32Result())
214             return index;
215
216         if (node.op == JSConstant) {
217             JSValue v = valueOfJSConstant(index);
218             if (v.isNumber())
219                 return getJSConstant(node.constantNumber());
220         }
221
222         return addToGraph(ValueToNumber, index);
223     }
224
225     NodeIndex getJSConstant(unsigned constant)
226     {
227         NodeIndex index = m_constants[constant].asJSValue;
228         if (index != NoNode)
229             return index;
230
231         NodeIndex resultIndex = addToGraph(JSConstant, OpInfo(constant));
232         m_constants[constant].asJSValue = resultIndex;
233         return resultIndex;
234     }
235
236     // Helper functions to get/set the this value.
237     NodeIndex getThis()
238     {
239         return getArgument(m_codeBlock->thisRegister());
240     }
241     void setThis(NodeIndex value)
242     {
243         setArgument(m_codeBlock->thisRegister(), value);
244     }
245
246     // Convenience methods for checking nodes for constants.
247     bool isJSConstant(NodeIndex index)
248     {
249         return m_graph[index].op == JSConstant;
250     }
251     bool isInt32Constant(NodeIndex nodeIndex)
252     {
253         return isJSConstant(nodeIndex) && valueOfJSConstant(nodeIndex).isInt32();
254     }
255     bool isDoubleConstant(NodeIndex nodeIndex)
256     {
257         return isJSConstant(nodeIndex) && valueOfJSConstant(nodeIndex).isNumber();
258     }
259     // Convenience methods for getting constant values.
260     JSValue valueOfJSConstant(NodeIndex index)
261     {
262         ASSERT(isJSConstant(index));
263         return m_codeBlock->getConstant(FirstConstantRegisterIndex + m_graph[index].constantNumber());
264     }
265     int32_t valueOfInt32Constant(NodeIndex nodeIndex)
266     {
267         ASSERT(isInt32Constant(nodeIndex));
268         return valueOfJSConstant(nodeIndex).asInt32();
269     }
270     double valueOfDoubleConstant(NodeIndex nodeIndex)
271     {
272         ASSERT(isDoubleConstant(nodeIndex));
273         double value;
274         bool okay = valueOfJSConstant(nodeIndex).getNumber(value);
275         ASSERT_UNUSED(okay, okay);
276         return value;
277     }
278
279     // This method returns a JSConstant with the value 'undefined'.
280     NodeIndex constantUndefined()
281     {
282         // Has m_constantUndefined been set up yet?
283         if (m_constantUndefined == UINT_MAX) {
284             // Search the constant pool for undefined, if we find it, we can just reuse this!
285             unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters();
286             for (m_constantUndefined = 0; m_constantUndefined < numberOfConstants; ++m_constantUndefined) {
287                 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantUndefined);
288                 if (testMe.isUndefined())
289                     return getJSConstant(m_constantUndefined);
290             }
291
292             // Add undefined to the CodeBlock's constants, and add a corresponding slot in m_constants.
293             ASSERT(m_constants.size() == numberOfConstants);
294             m_codeBlock->addConstant(jsUndefined());
295             m_constants.append(ConstantRecord());
296             ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters());
297         }
298
299         // m_constantUndefined must refer to an entry in the CodeBlock's constant pool that has the value 'undefined'.
300         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantUndefined).isUndefined());
301         return getJSConstant(m_constantUndefined);
302     }
303
304     // This method returns a JSConstant with the value 'null'.
305     NodeIndex constantNull()
306     {
307         // Has m_constantNull been set up yet?
308         if (m_constantNull == UINT_MAX) {
309             // Search the constant pool for null, if we find it, we can just reuse this!
310             unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters();
311             for (m_constantNull = 0; m_constantNull < numberOfConstants; ++m_constantNull) {
312                 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNull);
313                 if (testMe.isNull())
314                     return getJSConstant(m_constantNull);
315             }
316
317             // Add null to the CodeBlock's constants, and add a corresponding slot in m_constants.
318             ASSERT(m_constants.size() == numberOfConstants);
319             m_codeBlock->addConstant(jsNull());
320             m_constants.append(ConstantRecord());
321             ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters());
322         }
323
324         // m_constantNull must refer to an entry in the CodeBlock's constant pool that has the value 'null'.
325         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNull).isNull());
326         return getJSConstant(m_constantNull);
327     }
328
329     // This method returns a DoubleConstant with the value 1.
330     NodeIndex one()
331     {
332         // Has m_constant1 been set up yet?
333         if (m_constant1 == UINT_MAX) {
334             // Search the constant pool for the value 1, if we find it, we can just reuse this!
335             unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters();
336             for (m_constant1 = 0; m_constant1 < numberOfConstants; ++m_constant1) {
337                 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1);
338                 if (testMe.isInt32() && testMe.asInt32() == 1)
339                     return getJSConstant(m_constant1);
340             }
341
342             // Add the value 1 to the CodeBlock's constants, and add a corresponding slot in m_constants.
343             ASSERT(m_constants.size() == numberOfConstants);
344             m_codeBlock->addConstant(jsNumber(1));
345             m_constants.append(ConstantRecord());
346             ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters());
347         }
348
349         // m_constant1 must refer to an entry in the CodeBlock's constant pool that has the integer value 1.
350         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1).isInt32());
351         ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1).asInt32() == 1);
352         return getJSConstant(m_constant1);
353     }
354
355
356     // These methods create a node and add it to the graph. If nodes of this type are
357     // 'mustGenerate' then the node  will implicitly be ref'ed to ensure generation.
358     NodeIndex addToGraph(NodeType op, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
359     {
360         NodeIndex resultIndex = (NodeIndex)m_graph.size();
361         m_graph.append(Node(op, m_currentIndex, child1, child2, child3));
362
363         if (op & NodeMustGenerate)
364             m_graph.ref(resultIndex);
365         return resultIndex;
366     }
367     NodeIndex addToGraph(NodeType op, OpInfo info, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
368     {
369         NodeIndex resultIndex = (NodeIndex)m_graph.size();
370         m_graph.append(Node(op, m_currentIndex, info, child1, child2, child3));
371
372         if (op & NodeMustGenerate)
373             m_graph.ref(resultIndex);
374         return resultIndex;
375     }
376     NodeIndex addToGraph(NodeType op, OpInfo info1, OpInfo info2, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
377     {
378         NodeIndex resultIndex = (NodeIndex)m_graph.size();
379         m_graph.append(Node(op, m_currentIndex, info1, info2, child1, child2, child3));
380
381         if (op & NodeMustGenerate)
382             m_graph.ref(resultIndex);
383         return resultIndex;
384     }
385
386     void predictArray(NodeIndex nodeIndex)
387     {
388         Node* nodePtr = &m_graph[nodeIndex];
389
390         if (nodePtr->op == GetLocal)
391             m_graph.predict(nodePtr->local(), PredictArray);
392     }
393
394     void predictInt32(NodeIndex nodeIndex)
395     {
396         Node* nodePtr = &m_graph[nodeIndex];
397
398         if (nodePtr->op == ValueToNumber)
399             nodePtr = &m_graph[nodePtr->child1];
400
401         if (nodePtr->op == ValueToInt32)
402             nodePtr = &m_graph[nodePtr->child1];
403
404         if (nodePtr->op == GetLocal)
405             m_graph.predict(nodePtr->local(), PredictInt32);
406     }
407
408     JSGlobalData* m_globalData;
409     CodeBlock* m_codeBlock;
410     Graph& m_graph;
411
412     // The current block being generated.
413     BasicBlock* m_currentBlock;
414     // The bytecode index of the current instruction being generated.
415     unsigned m_currentIndex;
416
417     // Record failures due to unimplemented functionality or regressions.
418     bool m_parseFailed;
419
420     // We use these values during code generation, and to avoid the need for
421     // special handling we make sure they are available as constants in the
422     // CodeBlock's constant pool. These variables are initialized to
423     // UINT_MAX, and lazily updated to hold an index into the CodeBlock's
424     // constant pool, as necessary.
425     unsigned m_constantUndefined;
426     unsigned m_constantNull;
427     unsigned m_constant1;
428
429     // A constant in the constant pool may be represented by more than one
430     // node in the graph, depending on the context in which it is being used.
431     struct ConstantRecord {
432         ConstantRecord()
433             : asInt32(NoNode)
434             , asNumeric(NoNode)
435             , asJSValue(NoNode)
436         {
437         }
438
439         NodeIndex asInt32;
440         NodeIndex asNumeric;
441         NodeIndex asJSValue;
442     };
443
444     // Track the index of the node whose result is the current value for every
445     // register value in the bytecode - argument, local, and temporary.
446     Vector<ConstantRecord, 16> m_constants;
447
448     // The number of arguments passed to the function.
449     unsigned m_numArguments;
450     // The number of locals (vars + temporaries) used in the function.
451     unsigned m_numLocals;
452     // The number of registers we need to preserve across BasicBlock boundaries;
453     // typically equal to the number vars, but we expand this to cover all
454     // temporaries that persist across blocks (dues to ?:, &&, ||, etc).
455     unsigned m_preservedVars;
456
457     struct PhiStackEntry {
458         PhiStackEntry(BasicBlock* block, NodeIndex phi, unsigned varNo)
459             : m_block(block)
460             , m_phi(phi)
461             , m_varNo(varNo)
462         {
463         }
464
465         BasicBlock* m_block;
466         NodeIndex m_phi;
467         unsigned m_varNo;
468     };
469     Vector<PhiStackEntry, 16> m_argumentPhiStack;
470     Vector<PhiStackEntry, 16> m_localPhiStack;
471 };
472
473 #define NEXT_OPCODE(name) \
474     m_currentIndex += OPCODE_LENGTH(name); \
475     continue
476
477 #define LAST_OPCODE(name) \
478     m_currentIndex += OPCODE_LENGTH(name); \
479     return !m_parseFailed
480
481 bool ByteCodeParser::parseBlock(unsigned limit)
482 {
483     // No need to reset state initially, since it has been set by the constructor.
484     if (m_currentIndex) {
485         for (unsigned i = 0; i < m_constants.size(); ++i)
486             m_constants[i] = ConstantRecord();
487     }
488
489     AliasTracker aliases(m_graph);
490
491     Interpreter* interpreter = m_globalData->interpreter;
492     Instruction* instructionsBegin = m_codeBlock->instructions().begin();
493     while (true) {
494         // Don't extend over jump destinations.
495         if (m_currentIndex == limit) {
496             addToGraph(Jump, OpInfo(m_currentIndex));
497             return !m_parseFailed;
498         }
499
500         // Switch on the current bytecode opcode.
501         Instruction* currentInstruction = instructionsBegin + m_currentIndex;
502         switch (interpreter->getOpcodeID(currentInstruction->u.opcode)) {
503
504         // === Function entry opcodes ===
505
506         case op_enter:
507             // Initialize all locals to undefined.
508             for (int i = 0; i < m_codeBlock->m_numVars; ++i)
509                 set(i, constantUndefined());
510             NEXT_OPCODE(op_enter);
511
512         case op_convert_this: {
513             NodeIndex op1 = getThis();
514             setThis(addToGraph(ConvertThis, op1));
515             NEXT_OPCODE(op_convert_this);
516         }
517
518         // === Bitwise operations ===
519
520         case op_bitand: {
521             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
522             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
523             predictInt32(op1);
524             predictInt32(op2);
525             set(currentInstruction[1].u.operand, addToGraph(BitAnd, op1, op2), PredictInt32);
526             NEXT_OPCODE(op_bitand);
527         }
528
529         case op_bitor: {
530             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
531             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
532             predictInt32(op1);
533             predictInt32(op2);
534             set(currentInstruction[1].u.operand, addToGraph(BitOr, op1, op2), PredictInt32);
535             NEXT_OPCODE(op_bitor);
536         }
537
538         case op_bitxor: {
539             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
540             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
541             predictInt32(op1);
542             predictInt32(op2);
543             set(currentInstruction[1].u.operand, addToGraph(BitXor, op1, op2), PredictInt32);
544             NEXT_OPCODE(op_bitxor);
545         }
546
547         case op_rshift: {
548             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
549             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
550             predictInt32(op1);
551             predictInt32(op2);
552             NodeIndex result;
553             // Optimize out shifts by zero.
554             if (isInt32Constant(op2) && !(valueOfInt32Constant(op2) & 0x1f))
555                 result = op1;
556             else
557                 result = addToGraph(BitRShift, op1, op2);
558             set(currentInstruction[1].u.operand, result, PredictInt32);
559             NEXT_OPCODE(op_rshift);
560         }
561
562         case op_lshift: {
563             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
564             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
565             predictInt32(op1);
566             predictInt32(op2);
567             NodeIndex result;
568             // Optimize out shifts by zero.
569             if (isInt32Constant(op2) && !(valueOfInt32Constant(op2) & 0x1f))
570                 result = op1;
571             else
572                 result = addToGraph(BitLShift, op1, op2);
573             set(currentInstruction[1].u.operand, result, PredictInt32);
574             NEXT_OPCODE(op_lshift);
575         }
576
577         case op_urshift: {
578             NodeIndex op1 = getToInt32(currentInstruction[2].u.operand);
579             NodeIndex op2 = getToInt32(currentInstruction[3].u.operand);
580             predictInt32(op1);
581             predictInt32(op2);
582             NodeIndex result;
583             // The result of a zero-extending right shift is treated as an unsigned value.
584             // This means that if the top bit is set, the result is not in the int32 range,
585             // and as such must be stored as a double. If the shift amount is a constant,
586             // we may be able to optimize.
587             if (isInt32Constant(op2)) {
588                 // If we know we are shifting by a non-zero amount, then since the operation
589                 // zero fills we know the top bit of the result must be zero, and as such the
590                 // result must be within the int32 range. Conversely, if this is a shift by
591                 // zero, then the result may be changed by the conversion to unsigned, but it
592                 // is not necessary to perform the shift!
593                 if (valueOfInt32Constant(op2) & 0x1f)
594                     result = addToGraph(BitURShift, op1, op2);
595                 else
596                     result = addToGraph(UInt32ToNumber, op1);
597             }  else {
598                 // Cannot optimize at this stage; shift & potentially rebox as a double.
599                 result = addToGraph(BitURShift, op1, op2);
600                 result = addToGraph(UInt32ToNumber, result);
601             }
602             set(currentInstruction[1].u.operand, result, PredictInt32);
603             NEXT_OPCODE(op_urshift);
604         }
605
606         // === Increment/Decrement opcodes ===
607
608         case op_pre_inc: {
609             unsigned srcDst = currentInstruction[1].u.operand;
610             NodeIndex op = getToNumber(srcDst);
611             predictInt32(op);
612             set(srcDst, addToGraph(ArithAdd, op, one()));
613             NEXT_OPCODE(op_pre_inc);
614         }
615
616         case op_post_inc: {
617             unsigned result = currentInstruction[1].u.operand;
618             unsigned srcDst = currentInstruction[2].u.operand;
619             NodeIndex op = getToNumber(srcDst);
620             predictInt32(op);
621             set(result, op);
622             set(srcDst, addToGraph(ArithAdd, op, one()));
623             NEXT_OPCODE(op_post_inc);
624         }
625
626         case op_pre_dec: {
627             unsigned srcDst = currentInstruction[1].u.operand;
628             NodeIndex op = getToNumber(srcDst);
629             predictInt32(op);
630             set(srcDst, addToGraph(ArithSub, op, one()));
631             NEXT_OPCODE(op_pre_dec);
632         }
633
634         case op_post_dec: {
635             unsigned result = currentInstruction[1].u.operand;
636             unsigned srcDst = currentInstruction[2].u.operand;
637             NodeIndex op = getToNumber(srcDst);
638             predictInt32(op);
639             set(result, op);
640             set(srcDst, addToGraph(ArithSub, op, one()));
641             NEXT_OPCODE(op_post_dec);
642         }
643
644         // === Arithmetic operations ===
645
646         case op_add: {
647             ARITHMETIC_OP();
648             NodeIndex op1 = get(currentInstruction[2].u.operand);
649             NodeIndex op2 = get(currentInstruction[3].u.operand);
650             // If both operands can statically be determined to the numbers, then this is an arithmetic add.
651             // Otherwise, we must assume this may be performing a concatenation to a string.
652             if (m_graph[op1].hasNumericResult() && m_graph[op2].hasNumericResult())
653                 set(currentInstruction[1].u.operand, addToGraph(ArithAdd, toNumber(op1), toNumber(op2)));
654             else
655                 set(currentInstruction[1].u.operand, addToGraph(ValueAdd, op1, op2));
656             NEXT_OPCODE(op_add);
657         }
658
659         case op_sub: {
660             ARITHMETIC_OP();
661             NodeIndex op1 = getToNumber(currentInstruction[2].u.operand);
662             NodeIndex op2 = getToNumber(currentInstruction[3].u.operand);
663             set(currentInstruction[1].u.operand, addToGraph(ArithSub, op1, op2));
664             NEXT_OPCODE(op_sub);
665         }
666
667         case op_mul: {
668             ARITHMETIC_OP();
669             NodeIndex op1 = getToNumber(currentInstruction[2].u.operand);
670             NodeIndex op2 = getToNumber(currentInstruction[3].u.operand);
671             set(currentInstruction[1].u.operand, addToGraph(ArithMul, op1, op2));
672             NEXT_OPCODE(op_mul);
673         }
674
675         case op_mod: {
676             ARITHMETIC_OP();
677             NodeIndex op1 = getToNumber(currentInstruction[2].u.operand);
678             NodeIndex op2 = getToNumber(currentInstruction[3].u.operand);
679             set(currentInstruction[1].u.operand, addToGraph(ArithMod, op1, op2));
680             NEXT_OPCODE(op_mod);
681         }
682
683         case op_div: {
684             ARITHMETIC_OP();
685             NodeIndex op1 = getToNumber(currentInstruction[2].u.operand);
686             NodeIndex op2 = getToNumber(currentInstruction[3].u.operand);
687             set(currentInstruction[1].u.operand, addToGraph(ArithDiv, op1, op2));
688             NEXT_OPCODE(op_div);
689         }
690
691         // === Misc operations ===
692
693         case op_mov: {
694             NodeIndex op = get(currentInstruction[2].u.operand);
695             set(currentInstruction[1].u.operand, op);
696             NEXT_OPCODE(op_mov);
697         }
698
699         case op_not: {
700             ARITHMETIC_OP();
701             NodeIndex value = get(currentInstruction[2].u.operand);
702             set(currentInstruction[1].u.operand, addToGraph(LogicalNot, value));
703             NEXT_OPCODE(op_not);
704         }
705
706         case op_less: {
707             ARITHMETIC_OP();
708             NodeIndex op1 = get(currentInstruction[2].u.operand);
709             NodeIndex op2 = get(currentInstruction[3].u.operand);
710             set(currentInstruction[1].u.operand, addToGraph(CompareLess, op1, op2));
711             NEXT_OPCODE(op_less);
712         }
713
714         case op_lesseq: {
715             ARITHMETIC_OP();
716             NodeIndex op1 = get(currentInstruction[2].u.operand);
717             NodeIndex op2 = get(currentInstruction[3].u.operand);
718             set(currentInstruction[1].u.operand, addToGraph(CompareLessEq, op1, op2));
719             NEXT_OPCODE(op_lesseq);
720         }
721
722         case op_eq: {
723             ARITHMETIC_OP();
724             NodeIndex op1 = get(currentInstruction[2].u.operand);
725             NodeIndex op2 = get(currentInstruction[3].u.operand);
726             set(currentInstruction[1].u.operand, addToGraph(CompareEq, op1, op2));
727             NEXT_OPCODE(op_eq);
728         }
729
730         case op_eq_null: {
731             ARITHMETIC_OP();
732             NodeIndex value = get(currentInstruction[2].u.operand);
733             set(currentInstruction[1].u.operand, addToGraph(CompareEq, value, constantNull()));
734             NEXT_OPCODE(op_eq_null);
735         }
736
737         case op_stricteq: {
738             ARITHMETIC_OP();
739             NodeIndex op1 = get(currentInstruction[2].u.operand);
740             NodeIndex op2 = get(currentInstruction[3].u.operand);
741             set(currentInstruction[1].u.operand, addToGraph(CompareStrictEq, op1, op2));
742             NEXT_OPCODE(op_stricteq);
743         }
744
745         case op_neq: {
746             ARITHMETIC_OP();
747             NodeIndex op1 = get(currentInstruction[2].u.operand);
748             NodeIndex op2 = get(currentInstruction[3].u.operand);
749             set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareEq, op1, op2)));
750             NEXT_OPCODE(op_neq);
751         }
752
753         case op_neq_null: {
754             ARITHMETIC_OP();
755             NodeIndex value = get(currentInstruction[2].u.operand);
756             set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareEq, value, constantNull())));
757             NEXT_OPCODE(op_neq_null);
758         }
759
760         case op_nstricteq: {
761             ARITHMETIC_OP();
762             NodeIndex op1 = get(currentInstruction[2].u.operand);
763             NodeIndex op2 = get(currentInstruction[3].u.operand);
764             set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareStrictEq, op1, op2)));
765             NEXT_OPCODE(op_nstricteq);
766         }
767
768         // === Property access operations ===
769
770         case op_get_by_val: {
771             NodeIndex base = get(currentInstruction[2].u.operand);
772             NodeIndex property = get(currentInstruction[3].u.operand);
773             predictArray(base);
774             predictInt32(property);
775
776             NodeIndex getByVal = addToGraph(GetByVal, base, property, aliases.lookupGetByVal(base, property));
777             set(currentInstruction[1].u.operand, getByVal);
778             aliases.recordGetByVal(getByVal);
779
780             NEXT_OPCODE(op_get_by_val);
781         }
782
783         case op_put_by_val: {
784             NodeIndex base = get(currentInstruction[1].u.operand);
785             NodeIndex property = get(currentInstruction[2].u.operand);
786             NodeIndex value = get(currentInstruction[3].u.operand);
787             predictArray(base);
788             predictInt32(property);
789
790             NodeIndex aliasedGet = aliases.lookupGetByVal(base, property);
791             NodeIndex putByVal = addToGraph(aliasedGet != NoNode ? PutByValAlias : PutByVal, base, property, value);
792             aliases.recordPutByVal(putByVal);
793
794             NEXT_OPCODE(op_put_by_val);
795         }
796
797         case op_get_by_id: {
798             PROPERTY_ACCESS_OP();
799             NodeIndex base = get(currentInstruction[2].u.operand);
800             unsigned identifier = currentInstruction[3].u.operand;
801
802             NodeIndex getById = addToGraph(GetById, OpInfo(identifier), base);
803             set(currentInstruction[1].u.operand, getById);
804             aliases.recordGetById(getById);
805
806             NEXT_OPCODE(op_get_by_id);
807         }
808
809         case op_put_by_id: {
810             PROPERTY_ACCESS_OP();
811             NodeIndex value = get(currentInstruction[3].u.operand);
812             NodeIndex base = get(currentInstruction[1].u.operand);
813             unsigned identifier = currentInstruction[2].u.operand;
814             bool direct = currentInstruction[8].u.operand;
815
816             if (direct) {
817                 NodeIndex putByIdDirect = addToGraph(PutByIdDirect, OpInfo(identifier), base, value);
818                 aliases.recordPutByIdDirect(putByIdDirect);
819             } else {
820                 NodeIndex putById = addToGraph(PutById, OpInfo(identifier), base, value);
821                 aliases.recordPutById(putById);
822             }
823
824             NEXT_OPCODE(op_put_by_id);
825         }
826
827         case op_get_global_var: {
828             NodeIndex getGlobalVar = addToGraph(GetGlobalVar, OpInfo(currentInstruction[2].u.operand));
829             set(currentInstruction[1].u.operand, getGlobalVar);
830             NEXT_OPCODE(op_get_global_var);
831         }
832
833         case op_put_global_var: {
834             NodeIndex value = get(currentInstruction[2].u.operand);
835             addToGraph(PutGlobalVar, OpInfo(currentInstruction[1].u.operand), value);
836             NEXT_OPCODE(op_put_global_var);
837         }
838
839         // === Block terminators. ===
840
841         case op_jmp: {
842             unsigned relativeOffset = currentInstruction[1].u.operand;
843             addToGraph(Jump, OpInfo(m_currentIndex + relativeOffset));
844             LAST_OPCODE(op_jmp);
845         }
846
847         case op_loop: {
848             unsigned relativeOffset = currentInstruction[1].u.operand;
849             addToGraph(Jump, OpInfo(m_currentIndex + relativeOffset));
850             LAST_OPCODE(op_loop);
851         }
852
853         case op_jtrue: {
854             unsigned relativeOffset = currentInstruction[2].u.operand;
855             NodeIndex condition = get(currentInstruction[1].u.operand);
856             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jtrue)), condition);
857             LAST_OPCODE(op_jtrue);
858         }
859
860         case op_jfalse: {
861             unsigned relativeOffset = currentInstruction[2].u.operand;
862             NodeIndex condition = get(currentInstruction[1].u.operand);
863             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jfalse)), OpInfo(m_currentIndex + relativeOffset), condition);
864             LAST_OPCODE(op_jfalse);
865         }
866
867         case op_loop_if_true: {
868             unsigned relativeOffset = currentInstruction[2].u.operand;
869             NodeIndex condition = get(currentInstruction[1].u.operand);
870             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_true)), condition);
871             LAST_OPCODE(op_loop_if_true);
872         }
873
874         case op_loop_if_false: {
875             unsigned relativeOffset = currentInstruction[2].u.operand;
876             NodeIndex condition = get(currentInstruction[1].u.operand);
877             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_false)), OpInfo(m_currentIndex + relativeOffset), condition);
878             LAST_OPCODE(op_loop_if_false);
879         }
880
881         case op_jeq_null: {
882             unsigned relativeOffset = currentInstruction[2].u.operand;
883             NodeIndex value = get(currentInstruction[1].u.operand);
884             NodeIndex condition = addToGraph(CompareEq, value, constantNull());
885             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jeq_null)), condition);
886             LAST_OPCODE(op_jeq_null);
887         }
888
889         case op_jneq_null: {
890             unsigned relativeOffset = currentInstruction[2].u.operand;
891             NodeIndex value = get(currentInstruction[1].u.operand);
892             NodeIndex condition = addToGraph(CompareEq, value, constantNull());
893             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jneq_null)), OpInfo(m_currentIndex + relativeOffset), condition);
894             LAST_OPCODE(op_jneq_null);
895         }
896
897         case op_jnless: {
898             unsigned relativeOffset = currentInstruction[3].u.operand;
899             NodeIndex op1 = get(currentInstruction[1].u.operand);
900             NodeIndex op2 = get(currentInstruction[2].u.operand);
901             NodeIndex condition = addToGraph(CompareLess, op1, op2);
902             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jnless)), OpInfo(m_currentIndex + relativeOffset), condition);
903             LAST_OPCODE(op_jnless);
904         }
905
906         case op_jnlesseq: {
907             unsigned relativeOffset = currentInstruction[3].u.operand;
908             NodeIndex op1 = get(currentInstruction[1].u.operand);
909             NodeIndex op2 = get(currentInstruction[2].u.operand);
910             NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
911             addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jnlesseq)), OpInfo(m_currentIndex + relativeOffset), condition);
912             LAST_OPCODE(op_jnlesseq);
913         }
914
915         case op_jless: {
916             unsigned relativeOffset = currentInstruction[3].u.operand;
917             NodeIndex op1 = get(currentInstruction[1].u.operand);
918             NodeIndex op2 = get(currentInstruction[2].u.operand);
919             NodeIndex condition = addToGraph(CompareLess, op1, op2);
920             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jless)), condition);
921             LAST_OPCODE(op_jless);
922         }
923
924         case op_jlesseq: {
925             unsigned relativeOffset = currentInstruction[3].u.operand;
926             NodeIndex op1 = get(currentInstruction[1].u.operand);
927             NodeIndex op2 = get(currentInstruction[2].u.operand);
928             NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
929             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jlesseq)), condition);
930             LAST_OPCODE(op_jlesseq);
931         }
932
933         case op_loop_if_less: {
934             unsigned relativeOffset = currentInstruction[3].u.operand;
935             NodeIndex op1 = get(currentInstruction[1].u.operand);
936             NodeIndex op2 = get(currentInstruction[2].u.operand);
937             NodeIndex condition = addToGraph(CompareLess, op1, op2);
938             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_less)), condition);
939             LAST_OPCODE(op_loop_if_less);
940         }
941
942         case op_loop_if_lesseq: {
943             unsigned relativeOffset = currentInstruction[3].u.operand;
944             NodeIndex op1 = get(currentInstruction[1].u.operand);
945             NodeIndex op2 = get(currentInstruction[2].u.operand);
946             NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
947             addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_lesseq)), condition);
948             LAST_OPCODE(op_loop_if_lesseq);
949         }
950
951         case op_ret: {
952             addToGraph(Return, get(currentInstruction[1].u.operand));
953             LAST_OPCODE(op_ret);
954         }
955
956         default:
957             // Parse failed!
958             return false;
959         }
960     }
961 }
962
963 template<ByteCodeParser::PhiStackType stackType>
964 void ByteCodeParser::processPhiStack()
965 {
966     Vector<PhiStackEntry, 16>& phiStack = (stackType == ArgumentPhiStack) ? m_argumentPhiStack : m_localPhiStack;
967
968     while (!phiStack.isEmpty()) {
969         PhiStackEntry entry = phiStack.last();
970         phiStack.removeLast();
971         
972         Node& phiNode = m_graph[entry.m_phi];
973         PredecessorList& predecessors = entry.m_block->m_predecessors;
974         unsigned varNo = entry.m_varNo;
975
976         for (size_t i = 0; i < predecessors.size(); ++i) {
977             BasicBlock* predecessorBlock = m_graph.m_blocks[predecessors[i]].get();
978
979             VariableRecord& var = (stackType == ArgumentPhiStack) ? predecessorBlock->m_arguments[varNo] : predecessorBlock->m_locals[varNo];
980
981             NodeIndex valueInPredecessor = var.value;
982             if (valueInPredecessor == NoNode) {
983                 valueInPredecessor = addToGraph(Phi);
984                 var.value = valueInPredecessor;
985                 phiStack.append(PhiStackEntry(predecessorBlock, valueInPredecessor, varNo));
986             } else if (m_graph[valueInPredecessor].op == GetLocal)
987                 valueInPredecessor = m_graph[valueInPredecessor].child1;
988             ASSERT(m_graph[valueInPredecessor].op == SetLocal || m_graph[valueInPredecessor].op == Phi);
989
990             if (phiNode.refCount())
991                 m_graph.ref(valueInPredecessor);
992
993             if (phiNode.child1 == NoNode) {
994                 phiNode.child1 = valueInPredecessor;
995                 continue;
996             }
997             if (phiNode.child2 == NoNode) {
998                 phiNode.child2 = valueInPredecessor;
999                 continue;
1000             }
1001             if (phiNode.child3 == NoNode) {
1002                 phiNode.child3 = valueInPredecessor;
1003                 continue;
1004             }
1005
1006             NodeIndex newPhi = addToGraph(Phi);
1007             Node& newPhiNode = m_graph[newPhi];
1008             if (phiNode.refCount())
1009                 m_graph.ref(newPhi);
1010
1011             newPhiNode.child1 = phiNode.child1;
1012             newPhiNode.child2 = phiNode.child2;
1013             newPhiNode.child3 = phiNode.child3;
1014
1015             phiNode.child1 = newPhi;
1016             phiNode.child1 = valueInPredecessor;
1017             phiNode.child3 = NoNode;
1018         }
1019     }
1020 }
1021
1022 void ByteCodeParser::setupPredecessors()
1023 {
1024     for (BlockIndex index = 0; index < m_graph.m_blocks.size(); ++index) {
1025         BasicBlock* block = m_graph.m_blocks[index].get();
1026         ASSERT(block->end != NoNode);
1027         Node& node = m_graph[block->end - 1];
1028         ASSERT(node.isTerminal());
1029
1030         if (node.isJump())
1031             m_graph.blockForBytecodeOffset(node.takenBytecodeOffset()).m_predecessors.append(index);
1032         else if (node.isBranch()) {
1033             m_graph.blockForBytecodeOffset(node.takenBytecodeOffset()).m_predecessors.append(index);
1034             m_graph.blockForBytecodeOffset(node.notTakenBytecodeOffset()).m_predecessors.append(index);
1035         }
1036     }
1037 }
1038
1039 void ByteCodeParser::allocateVirtualRegisters()
1040 {
1041     ScoreBoard scoreBoard(m_graph, m_preservedVars);
1042     unsigned sizeExcludingPhiNodes = m_graph.m_blocks.last()->end;
1043     for (size_t i = 0; i < sizeExcludingPhiNodes; ++i) {
1044         Node& node = m_graph[i];
1045         if (!node.shouldGenerate())
1046             continue;
1047
1048         // GetLocal nodes are effectively phi nodes in the graph, referencing
1049         // results from prior blocks.
1050         if (node.op != GetLocal) {
1051             // First, call use on all of the current node's children, then
1052             // allocate a VirtualRegister for this node. We do so in this
1053             // order so that if a child is on its last use, and a
1054             // VirtualRegister is freed, then it may be reused for node.
1055             scoreBoard.use(node.child1);
1056             scoreBoard.use(node.child2);
1057             scoreBoard.use(node.child3);
1058         }
1059
1060         if (!node.hasResult())
1061             continue;
1062
1063         node.setVirtualRegister(scoreBoard.allocate());
1064         // 'mustGenerate' nodes have their useCount artificially elevated,
1065         // call use now to account for this.
1066         if (node.mustGenerate())
1067             scoreBoard.use(i);
1068     }
1069
1070     // 'm_numCalleeRegisters' is the number of locals and temporaries allocated
1071     // for the function (and checked for on entry). Since we perform a new and
1072     // different allocation of temporaries, more registers may now be required.
1073     unsigned calleeRegisters = scoreBoard.allocatedCount() + m_preservedVars;
1074     if ((unsigned)m_codeBlock->m_numCalleeRegisters < calleeRegisters)
1075         m_codeBlock->m_numCalleeRegisters = calleeRegisters;
1076 }
1077
1078 bool ByteCodeParser::parse()
1079 {
1080     // Set during construction.
1081     ASSERT(!m_currentIndex);
1082
1083     for (unsigned jumpTargetIndex = 0; jumpTargetIndex <= m_codeBlock->numberOfJumpTargets(); ++jumpTargetIndex) {
1084         // The maximum bytecode offset to go into the current basicblock is either the next jump target, or the end of the instructions.
1085         unsigned limit = jumpTargetIndex < m_codeBlock->numberOfJumpTargets() ? m_codeBlock->jumpTarget(jumpTargetIndex) : m_codeBlock->instructions().size();
1086         ASSERT(m_currentIndex < limit);
1087
1088         // Loop until we reach the current limit (i.e. next jump target).
1089         do {
1090             OwnPtr<BasicBlock> block = adoptPtr(new BasicBlock(m_currentIndex, m_graph.size(), m_numArguments, m_numLocals));
1091             m_currentBlock = block.get();
1092             m_graph.m_blocks.append(block.release());
1093
1094             if (!parseBlock(limit))
1095                 return false;
1096             // We should not have gone beyond the limit.
1097             ASSERT(m_currentIndex <= limit);
1098
1099             m_currentBlock->end = m_graph.size();
1100         } while (m_currentIndex < limit);
1101     }
1102
1103     // Should have reached the end of the instructions.
1104     ASSERT(m_currentIndex == m_codeBlock->instructions().size());
1105
1106     setupPredecessors();
1107     processPhiStack<LocalPhiStack>();
1108     processPhiStack<ArgumentPhiStack>();
1109
1110     allocateVirtualRegisters();
1111
1112 #if DFG_DEBUG_VERBOSE
1113     m_graph.dump(m_codeBlock);
1114 #endif
1115
1116     return true;
1117 }
1118
1119 bool parse(Graph& graph, JSGlobalData* globalData, CodeBlock* codeBlock)
1120 {
1121 #if DFG_DEBUG_LOCAL_DISBALE
1122     UNUSED_PARAM(graph);
1123     UNUSED_PARAM(globalData);
1124     UNUSED_PARAM(codeBlock);
1125     return false;
1126 #else
1127     return ByteCodeParser(globalData, codeBlock, graph).parse();
1128 #endif
1129 }
1130
1131 } } // namespace JSC::DFG
1132
1133 #endif