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