2ea6570bafe3816a15ca0f0ac7bfe6decfcb4b4b
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGNode.h
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 #ifndef DFGNode_h
27 #define DFGNode_h
28
29 // Emit various logging information for debugging, including dumping the dataflow graphs.
30 #define DFG_DEBUG_VERBOSE 0
31 // Enable generation of dynamic checks into the instruction stream.
32 #define DFG_JIT_ASSERT 0
33 // Consistency check contents compiler data structures.
34 #define DFG_CONSISTENCY_CHECK 0
35 // Emit a breakpoint into the head of every generated function, to aid debugging in GDB.
36 #define DFG_JIT_BREAK_ON_EVERY_FUNCTION 0
37 // Emit a breakpoint into the head of every generated node, to aid debugging in GDB.
38 #define DFG_JIT_BREAK_ON_EVERY_BLOCK 0
39 // Emit a breakpoint into the head of every generated node, to aid debugging in GDB.
40 #define DFG_JIT_BREAK_ON_EVERY_NODE 0
41 // Emit a breakpoint into the speculation failure code.
42 #define DFG_JIT_BREAK_ON_SPECULATION_FAILURE 0
43 // Disable the DFG JIT without having to touch Platform.h!
44 #define DFG_DEBUG_LOCAL_DISBALE 0
45 // Disable the SpeculativeJIT without having to touch Platform.h!
46 #define DFG_DEBUG_LOCAL_DISBALE_SPECULATIVE 0
47 // Generate stats on how successful we were in making use of the DFG jit, and remaining on the hot path.
48 #define DFG_SUCCESS_STATS 0
49
50
51 #if ENABLE(DFG_JIT)
52
53 #include <wtf/Vector.h>
54
55 namespace JSC { namespace DFG {
56
57 // Type for a virtual register number (spill location).
58 // Using an enum to make this type-checked at compile time, to avert programmer errors.
59 enum VirtualRegister { InvalidVirtualRegister = -1 };
60 COMPILE_ASSERT(sizeof(VirtualRegister) == sizeof(int), VirtualRegister_is_32bit);
61
62 // Type for a reference to another node in the graph.
63 typedef uint32_t NodeIndex;
64 static const NodeIndex NoNode = UINT_MAX;
65
66 // Information used to map back from an exception to any handler/source information.
67 // (Presently implemented as a bytecode index).
68 typedef uint32_t ExceptionInfo;
69
70 // Entries in the NodeType enum (below) are composed of an id, a result type (possibly none)
71 // and some additional informative flags (must generate, is constant, etc).
72 #define NodeIdMask          0xFFF
73 #define NodeResultMask     0xF000
74 #define NodeMustGenerate  0x10000 // set on nodes that have side effects, and may not trivially be removed by DCE.
75 #define NodeIsConstant    0x20000
76 #define NodeIsJump        0x40000
77 #define NodeIsBranch      0x80000
78 #define NodeIsTerminal   0x100000
79
80 // These values record the result type of the node (as checked by NodeResultMask, above), 0 for no result.
81 #define NodeResultJS      0x1000
82 #define NodeResultDouble  0x2000
83 #define NodeResultInt32   0x3000
84
85 // This macro defines a set of information about all known node types, used to populate NodeId, NodeType below.
86 #define FOR_EACH_DFG_OP(macro) \
87     /* Nodes for constants. */\
88     macro(JSConstant, NodeResultJS | NodeIsConstant) \
89     macro(Int32Constant, NodeResultJS | NodeIsConstant) \
90     macro(DoubleConstant, NodeResultJS | NodeIsConstant) \
91     macro(ConvertThis, NodeResultJS) \
92     \
93     /* Nodes for local variable access. */\
94     macro(GetLocal, NodeResultJS) \
95     macro(SetLocal, 0) \
96     macro(Phi, 0) \
97     \
98     /* Nodes for bitwise operations. */\
99     macro(BitAnd, NodeResultInt32) \
100     macro(BitOr, NodeResultInt32) \
101     macro(BitXor, NodeResultInt32) \
102     macro(BitLShift, NodeResultInt32) \
103     macro(BitRShift, NodeResultInt32) \
104     macro(BitURShift, NodeResultInt32) \
105     /* Bitwise operators call ToInt32 on their operands. */\
106     macro(NumberToInt32, NodeResultInt32) \
107     macro(ValueToInt32, NodeResultInt32 | NodeMustGenerate) \
108     /* Used to box the result of URShift nodes (result has range 0..2^32-1). */\
109     macro(UInt32ToNumber, NodeResultDouble) \
110     \
111     /* Nodes for arithmetic operations. */\
112     macro(ArithAdd, NodeResultDouble) \
113     macro(ArithSub, NodeResultDouble) \
114     macro(ArithMul, NodeResultDouble) \
115     macro(ArithDiv, NodeResultDouble) \
116     macro(ArithMod, NodeResultDouble) \
117     /* Arithmetic operators call ToNumber on their operands. */\
118     macro(Int32ToNumber, NodeResultDouble) \
119     macro(ValueToNumber, NodeResultDouble | NodeMustGenerate) \
120     \
121     /* Add of values may either be arithmetic, or result in string concatenation. */\
122     macro(ValueAdd, NodeResultJS | NodeMustGenerate) \
123     \
124     /* Property access. */\
125     /* PutByValAlias indicates a 'put' aliases a prior write to the same property. */\
126     /* Since a put to 'length' may invalidate optimizations here, */\
127     /* this must be the directly subsequent property put. */\
128     macro(GetByVal, NodeResultJS | NodeMustGenerate) \
129     macro(PutByVal, NodeMustGenerate) \
130     macro(PutByValAlias, NodeMustGenerate) \
131     macro(GetById, NodeResultJS | NodeMustGenerate) \
132     macro(PutById, NodeMustGenerate) \
133     macro(PutByIdDirect, NodeMustGenerate) \
134     macro(GetGlobalVar, NodeResultJS | NodeMustGenerate) \
135     macro(PutGlobalVar, NodeMustGenerate) \
136     \
137     /* Nodes for comparison operations. */\
138     macro(CompareLess, NodeResultJS | NodeMustGenerate) \
139     macro(CompareLessEq, NodeResultJS | NodeMustGenerate) \
140     macro(CompareEq, NodeResultJS | NodeMustGenerate) \
141     macro(CompareStrictEq, NodeResultJS) \
142     \
143     /* Nodes for misc operations. */\
144     macro(LogicalNot, NodeResultJS) \
145     \
146     /* Block terminals. */\
147     macro(Jump, NodeMustGenerate | NodeIsTerminal | NodeIsJump) \
148     macro(Branch, NodeMustGenerate | NodeIsTerminal | NodeIsBranch) \
149     macro(Return, NodeMustGenerate | NodeIsTerminal)
150
151 // This enum generates a monotonically increasing id for all Node types,
152 // and is used by the subsequent enum to fill out the id (as accessed via the NodeIdMask).
153 enum NodeId {
154 #define DFG_OP_ENUM(opcode, flags) opcode##_id,
155     FOR_EACH_DFG_OP(DFG_OP_ENUM)
156 #undef DFG_OP_ENUM
157 };
158
159 // Entries in this enum describe all Node types.
160 // The enum value contains a monotonically increasing id, a result type, and additional flags.
161 enum NodeType {
162 #define DFG_OP_ENUM(opcode, flags) opcode = opcode##_id | (flags),
163     FOR_EACH_DFG_OP(DFG_OP_ENUM)
164 #undef DFG_OP_ENUM
165 };
166
167 // This type used in passing an immediate argument to Node constructor;
168 // distinguishes an immediate value (typically an index into a CodeBlock data structure - 
169 // a constant index, argument, or identifier) from a NodeIndex.
170 struct OpInfo {
171     explicit OpInfo(unsigned value) : m_value(value) {}
172     unsigned m_value;
173 };
174
175 // === Node ===
176 //
177 // Node represents a single operation in the data flow graph.
178 struct Node {
179     // Construct a node with up to 3 children, no immediate value.
180     Node(NodeType op, ExceptionInfo exceptionInfo, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
181         : op(op)
182         , exceptionInfo(exceptionInfo)
183         , child1(child1)
184         , child2(child2)
185         , child3(child3)
186         , m_virtualRegister(InvalidVirtualRegister)
187         , m_refCount(0)
188     {
189     }
190
191     // Construct a node with up to 3 children and an immediate value.
192     Node(NodeType op, ExceptionInfo exceptionInfo, OpInfo imm, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
193         : op(op)
194         , exceptionInfo(exceptionInfo)
195         , child1(child1)
196         , child2(child2)
197         , child3(child3)
198         , m_virtualRegister(InvalidVirtualRegister)
199         , m_refCount(0)
200         , m_opInfo(imm.m_value)
201     {
202     }
203
204     // Construct a node with up to 3 children and two immediate values.
205     Node(NodeType op, ExceptionInfo exceptionInfo, OpInfo imm1, OpInfo imm2, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
206         : op(op)
207         , exceptionInfo(exceptionInfo)
208         , child1(child1)
209         , child2(child2)
210         , child3(child3)
211         , m_virtualRegister(InvalidVirtualRegister)
212         , m_refCount(0)
213         , m_opInfo(imm1.m_value)
214     {
215         m_constantValue.opInfo2 = imm2.m_value;
216     }
217
218     bool mustGenerate()
219     {
220         return op & NodeMustGenerate;
221     }
222
223     bool isConstant()
224     {
225         return op & NodeIsConstant;
226     }
227
228     unsigned constantNumber()
229     {
230         ASSERT(isConstant());
231         return m_opInfo;
232     }
233
234     bool hasLocal()
235     {
236         return op == GetLocal || op == SetLocal;
237     }
238
239     VirtualRegister local()
240     {
241         ASSERT(hasLocal());
242         return (VirtualRegister)m_opInfo;
243     }
244
245     bool hasIdentifier()
246     {
247         return op == GetById || op == PutById || op == PutByIdDirect;
248     }
249
250     unsigned identifierNumber()
251     {
252         ASSERT(hasIdentifier());
253         return m_opInfo;
254     }
255
256     bool hasVarNumber()
257     {
258         return op == GetGlobalVar || op == PutGlobalVar;
259     }
260
261     unsigned varNumber()
262     {
263         ASSERT(hasVarNumber());
264         return m_opInfo;
265     }
266
267     bool hasResult()
268     {
269         return op & NodeResultMask;
270     }
271
272     bool hasInt32Result()
273     {
274         return (op & NodeResultMask) == NodeResultInt32;
275     }
276
277     bool hasDoubleResult()
278     {
279         return (op & NodeResultMask) == NodeResultDouble;
280     }
281
282     bool hasJSResult()
283     {
284         return (op & NodeResultMask) == NodeResultJS;
285     }
286
287     // Check for integers or doubles.
288     bool hasNumericResult()
289     {
290         // This check will need updating if more result types are added.
291         ASSERT((hasInt32Result() || hasDoubleResult()) == !hasJSResult());
292         return !hasJSResult();
293     }
294
295     int32_t int32Constant()
296     {
297         ASSERT(op == Int32Constant);
298         return m_constantValue.asInt32;
299     }
300
301     void setInt32Constant(int32_t value)
302     {
303         ASSERT(op == Int32Constant);
304         m_constantValue.asInt32 = value;
305     }
306
307     double numericConstant()
308     {
309         ASSERT(op == DoubleConstant);
310         return m_constantValue.asDouble;
311     }
312
313     void setDoubleConstant(double value)
314     {
315         ASSERT(op == DoubleConstant);
316         m_constantValue.asDouble = value;
317     }
318
319     bool isJump()
320     {
321         return op & NodeIsJump;
322     }
323
324     bool isBranch()
325     {
326         return op & NodeIsBranch;
327     }
328
329     bool isTerminal()
330     {
331         return op & NodeIsTerminal;
332     }
333
334     unsigned takenBytecodeOffset()
335     {
336         ASSERT(isBranch() || isJump());
337         return m_opInfo;
338     }
339
340     unsigned notTakenBytecodeOffset()
341     {
342         ASSERT(isBranch());
343         return m_constantValue.opInfo2;
344     }
345
346     VirtualRegister virtualRegister()
347     {
348         ASSERT(hasResult());
349         ASSERT(m_virtualRegister != InvalidVirtualRegister);
350         return m_virtualRegister;
351     }
352
353     void setVirtualRegister(VirtualRegister virtualRegister)
354     {
355         ASSERT(hasResult());
356         ASSERT(m_virtualRegister == InvalidVirtualRegister);
357         m_virtualRegister = virtualRegister;
358     }
359
360     bool shouldGenerate()
361     {
362         return m_refCount && op != Phi;
363     }
364
365     unsigned refCount()
366     {
367         return m_refCount;
368     }
369
370     // returns true when ref count passes from 0 to 1.
371     bool ref()
372     {
373         return !m_refCount++;
374     }
375
376     unsigned adjustedRefCount()
377     {
378         return mustGenerate() ? m_refCount - 1 : m_refCount;
379     }
380
381     // This enum value describes the type of the node.
382     NodeType op;
383     // Used to look up exception handling information (currently implemented as a bytecode index).
384     ExceptionInfo exceptionInfo;
385     // References to up to 3 children (0 for no child).
386     NodeIndex child1, child2, child3;
387
388 private:
389     // The virtual register number (spill location) associated with this .
390     VirtualRegister m_virtualRegister;
391     // The number of uses of the result of this operation (+1 for 'must generate' nodes, which have side-effects).
392     unsigned m_refCount;
393     // An immediate value, accesses type-checked via accessors above.
394     unsigned m_opInfo;
395     // The value of an int32/double constant.
396     union {
397         int32_t asInt32;
398         double asDouble;
399         unsigned opInfo2;
400     } m_constantValue;
401 };
402
403 } } // namespace JSC::DFG
404
405 #endif
406 #endif