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