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 51 namespace 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. 55 enum VirtualRegister { InvalidVirtualRegister = -1 }; 56 COMPILE_ASSERT(sizeof(VirtualRegister) == sizeof(int), VirtualRegister_is_32bit); 57 58 // Type for a reference to another node in the graph. 59 typedef uint32_t NodeIndex; 60 static 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). 64 typedef 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). 147 enum 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. 155 enum 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. 164 struct OpInfo { OpInfoOpInfo165 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. 172 struct 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) opNode175 : 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) opNode187 : 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) opNode200 : 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 mustGenerateNode212 bool mustGenerate() 213 { 214 return op & NodeMustGenerate; 215 } 216 isConstantNode217 bool isConstant() 218 { 219 return op & NodeIsConstant; 220 } 221 constantNumberNode222 unsigned constantNumber() 223 { 224 ASSERT(isConstant()); 225 return m_opInfo; 226 } 227 hasLocalNode228 bool hasLocal() 229 { 230 return op == GetLocal || op == SetLocal; 231 } 232 localNode233 VirtualRegister local() 234 { 235 ASSERT(hasLocal()); 236 return (VirtualRegister)m_opInfo; 237 } 238 hasIdentifierNode239 bool hasIdentifier() 240 { 241 return op == GetById || op == PutById || op == PutByIdDirect; 242 } 243 identifierNumberNode244 unsigned identifierNumber() 245 { 246 ASSERT(hasIdentifier()); 247 return m_opInfo; 248 } 249 hasVarNumberNode250 bool hasVarNumber() 251 { 252 return op == GetGlobalVar || op == PutGlobalVar; 253 } 254 varNumberNode255 unsigned varNumber() 256 { 257 ASSERT(hasVarNumber()); 258 return m_opInfo; 259 } 260 hasInt32ResultNode261 bool hasInt32Result() 262 { 263 return (op & NodeResultMask) == NodeResultInt32; 264 } 265 hasDoubleResultNode266 bool hasDoubleResult() 267 { 268 return (op & NodeResultMask) == NodeResultDouble; 269 } 270 hasJSResultNode271 bool hasJSResult() 272 { 273 return (op & NodeResultMask) == NodeResultJS; 274 } 275 276 // Check for integers or doubles. hasNumericResultNode277 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 int32ConstantNode284 int32_t int32Constant() 285 { 286 ASSERT(op == Int32Constant); 287 return m_constantValue.asInt32; 288 } 289 setInt32ConstantNode290 void setInt32Constant(int32_t value) 291 { 292 ASSERT(op == Int32Constant); 293 m_constantValue.asInt32 = value; 294 } 295 numericConstantNode296 double numericConstant() 297 { 298 ASSERT(op == DoubleConstant); 299 return m_constantValue.asDouble; 300 } 301 setDoubleConstantNode302 void setDoubleConstant(double value) 303 { 304 ASSERT(op == DoubleConstant); 305 m_constantValue.asDouble = value; 306 } 307 isJumpNode308 bool isJump() 309 { 310 return op & NodeIsJump; 311 } 312 isBranchNode313 bool isBranch() 314 { 315 return op & NodeIsBranch; 316 } 317 takenBytecodeOffsetNode318 unsigned takenBytecodeOffset() 319 { 320 ASSERT(isBranch() || isJump()); 321 return m_opInfo; 322 } 323 notTakenBytecodeOffsetNode324 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 341 private: 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