Home | History | Annotate | Download | only in dfg 
      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 {
    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.
    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)
    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 
    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