code.vuplus.com Git - vuplus_webkit/blob - 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 #include <wtf/Platform.h>
  30
  31 // Emit various logging information for debugging, including dumping the dataflow graphs.
  32 #define ENABLE_DFG_DEBUG_VERBOSE 0
  33 // Emit logging for OSR exit value recoveries at every node, not just nodes that
  34 // actually has speculation checks.
  35 #define ENABLE_DFG_VERBOSE_VALUE_RECOVERIES 0
  36 // Enable generation of dynamic checks into the instruction stream.
  37 #if !ASSERT_DISABLED
  38 #define ENABLE_DFG_JIT_ASSERT 1
  39 #else
  40 #define ENABLE_DFG_JIT_ASSERT 0
  41 #endif
  42 // Consistency check contents compiler data structures.
  43 #define ENBALE_DFG_CONSISTENCY_CHECK 0
  44 // Emit a breakpoint into the head of every generated function, to aid debugging in GDB.
  45 #define ENABLE_DFG_JIT_BREAK_ON_EVERY_FUNCTION 0
  46 // Emit a breakpoint into the head of every generated node, to aid debugging in GDB.
  47 #define ENABLE_DFG_JIT_BREAK_ON_EVERY_BLOCK 0
  48 // Emit a breakpoint into the head of every generated node, to aid debugging in GDB.
  49 #define ENABLE_DFG_JIT_BREAK_ON_EVERY_NODE 0
  50 // Emit a breakpoint into the speculation failure code.
  51 #define ENABLE_DFG_JIT_BREAK_ON_SPECULATION_FAILURE 0
  52 // Log every speculation failure.
  53 #define ENABLE_DFG_VERBOSE_SPECULATION_FAILURE 0
  54 // Disable the DFG JIT without having to touch Platform.h!
  55 #define DFG_DEBUG_LOCAL_DISBALE 0
  56 // Disable the SpeculativeJIT without having to touch Platform.h!
  57 #define DFG_DEBUG_LOCAL_DISBALE_SPECULATIVE 0
  58 // Enable OSR entry from baseline JIT.
  59 #define ENABLE_DFG_OSR_ENTRY ENABLE_TIERED_COMPILATION
  60 // Disable the non-speculative JIT and use OSR instead.
  61 #define ENABLE_DFG_OSR_EXIT ENABLE_TIERED_COMPILATION
  62 // Generate stats on how successful we were in making use of the DFG jit, and remaining on the hot path.
  63 #define ENABLE_DFG_SUCCESS_STATS 0
  64
  65
  66 #if ENABLE(DFG_JIT)
  67
  68 #include "CodeBlock.h"
  69 #include "JSValue.h"
  70 #include "PredictedType.h"
  71 #include "ValueProfile.h"
  72 #include <wtf/Vector.h>
  73
  74 namespace JSC { namespace DFG {
  75
  76 // Type for a virtual register number (spill location).
  77 // Using an enum to make this type-checked at compile time, to avert programmer errors.
  78 enum VirtualRegister { InvalidVirtualRegister = -1 };
  79 COMPILE_ASSERT(sizeof(VirtualRegister) == sizeof(int), VirtualRegister_is_32bit);
  80
  81 // Type for a reference to another node in the graph.
  82 typedef uint32_t NodeIndex;
  83 static const NodeIndex NoNode = UINT_MAX;
  84
  85 // Information used to map back from an exception to any handler/source information,
  86 // and to implement OSR.
  87 // (Presently implemented as a bytecode index).
  88 class CodeOrigin {
  89 public:
  90     CodeOrigin()
  91         : m_bytecodeIndex(std::numeric_limits<uint32_t>::max())
  92     {
  93     }
  94
  95     explicit CodeOrigin(uint32_t bytecodeIndex)
  96         : m_bytecodeIndex(bytecodeIndex)
  97     {
  98     }
  99
 100     bool isSet() const { return m_bytecodeIndex != std::numeric_limits<uint32_t>::max(); }
 101
 102     uint32_t bytecodeIndex() const
 103     {
 104         ASSERT(isSet());
 105         return m_bytecodeIndex;
 106     }
 107
 108 private:
 109     uint32_t m_bytecodeIndex;
 110 };
 111
 112 // Entries in the NodeType enum (below) are composed of an id, a result type (possibly none)
 113 // and some additional informative flags (must generate, is constant, etc).
 114 #define NodeIdMask          0xFFF
 115 #define NodeResultMask     0xF000
 116 #define NodeMustGenerate  0x10000 // set on nodes that have side effects, and may not trivially be removed by DCE.
 117 #define NodeIsConstant    0x20000
 118 #define NodeIsJump        0x40000
 119 #define NodeIsBranch      0x80000
 120 #define NodeIsTerminal   0x100000
 121 #define NodeHasVarArgs   0x200000
 122
 123 // These values record the result type of the node (as checked by NodeResultMask, above), 0 for no result.
 124 #define NodeResultJS      0x1000
 125 #define NodeResultNumber  0x2000
 126 #define NodeResultInt32   0x3000
 127 #define NodeResultBoolean 0x4000
 128
 129 // This macro defines a set of information about all known node types, used to populate NodeId, NodeType below.
 130 #define FOR_EACH_DFG_OP(macro) \
 131     /* Nodes for constants. */\
 132     macro(JSConstant, NodeResultJS) \
 133     macro(ConvertThis, NodeResultJS) \
 134     \
 135     /* Nodes for local variable access. */\
 136     macro(GetLocal, NodeResultJS) \
 137     macro(SetLocal, 0) \
 138     macro(Phi, 0) \
 139     \
 140     /* Nodes for bitwise operations. */\
 141     macro(BitAnd, NodeResultInt32) \
 142     macro(BitOr, NodeResultInt32) \
 143     macro(BitXor, NodeResultInt32) \
 144     macro(BitLShift, NodeResultInt32) \
 145     macro(BitRShift, NodeResultInt32) \
 146     macro(BitURShift, NodeResultInt32) \
 147     /* Bitwise operators call ToInt32 on their operands. */\
 148     macro(ValueToInt32, NodeResultInt32 | NodeMustGenerate) \
 149     /* Used to box the result of URShift nodes (result has range 0..2^32-1). */\
 150     macro(UInt32ToNumber, NodeResultNumber) \
 151     \
 152     /* Nodes for arithmetic operations. */\
 153     macro(ArithAdd, NodeResultNumber) \
 154     macro(ArithSub, NodeResultNumber) \
 155     macro(ArithMul, NodeResultNumber) \
 156     macro(ArithDiv, NodeResultNumber) \
 157     macro(ArithMod, NodeResultNumber) \
 158     /* Arithmetic operators call ToNumber on their operands. */\
 159     macro(ValueToNumber, NodeResultNumber | NodeMustGenerate) \
 160     \
 161     /* A variant of ValueToNumber, which a hint that the parents will always use this as a double. */\
 162     macro(ValueToDouble, NodeResultNumber | NodeMustGenerate) \
 163     \
 164     /* Add of values may either be arithmetic, or result in string concatenation. */\
 165     macro(ValueAdd, NodeResultJS | NodeMustGenerate) \
 166     \
 167     /* Property access. */\
 168     /* PutByValAlias indicates a 'put' aliases a prior write to the same property. */\
 169     /* Since a put to 'length' may invalidate optimizations here, */\
 170     /* this must be the directly subsequent property put. */\
 171     macro(GetByVal, NodeResultJS | NodeMustGenerate) \
 172     macro(PutByVal, NodeMustGenerate) \
 173     macro(PutByValAlias, NodeMustGenerate) \
 174     macro(GetById, NodeResultJS | NodeMustGenerate) \
 175     macro(PutById, NodeMustGenerate) \
 176     macro(PutByIdDirect, NodeMustGenerate) \
 177     macro(GetMethod, NodeResultJS | NodeMustGenerate) \
 178     macro(GetGlobalVar, NodeResultJS | NodeMustGenerate) \
 179     macro(PutGlobalVar, NodeMustGenerate) \
 180     \
 181     /* Nodes for comparison operations. */\
 182     macro(CompareLess, NodeResultBoolean | NodeMustGenerate) \
 183     macro(CompareLessEq, NodeResultBoolean | NodeMustGenerate) \
 184     macro(CompareGreater, NodeResultBoolean | NodeMustGenerate) \
 185     macro(CompareGreaterEq, NodeResultBoolean | NodeMustGenerate) \
 186     macro(CompareEq, NodeResultBoolean | NodeMustGenerate) \
 187     macro(CompareStrictEq, NodeResultBoolean) \
 188     \
 189     /* Calls. */\
 190     macro(Call, NodeResultJS | NodeMustGenerate | NodeHasVarArgs) \
 191     macro(Construct, NodeResultJS | NodeMustGenerate | NodeHasVarArgs) \
 192     \
 193     /* Resolve nodes. */\
 194     macro(Resolve, NodeResultJS | NodeMustGenerate) \
 195     macro(ResolveBase, NodeResultJS | NodeMustGenerate) \
 196     macro(ResolveBaseStrictPut, NodeResultJS | NodeMustGenerate) \
 197     \
 198     /* Nodes for misc operations. */\
 199     macro(Breakpoint, NodeMustGenerate) \
 200     macro(CheckHasInstance, NodeMustGenerate) \
 201     macro(InstanceOf, NodeResultBoolean) \
 202     macro(LogicalNot, NodeResultBoolean) \
 203     \
 204     /* Block terminals. */\
 205     macro(Jump, NodeMustGenerate | NodeIsTerminal | NodeIsJump) \
 206     macro(Branch, NodeMustGenerate | NodeIsTerminal | NodeIsBranch) \
 207     macro(Return, NodeMustGenerate | NodeIsTerminal)
 208
 209 // This enum generates a monotonically increasing id for all Node types,
 210 // and is used by the subsequent enum to fill out the id (as accessed via the NodeIdMask).
 211 enum NodeId {
 212 #define DFG_OP_ENUM(opcode, flags) opcode##_id,
 213     FOR_EACH_DFG_OP(DFG_OP_ENUM)
 214 #undef DFG_OP_ENUM
 215 };
 216
 217 // Entries in this enum describe all Node types.
 218 // The enum value contains a monotonically increasing id, a result type, and additional flags.
 219 enum NodeType {
 220 #define DFG_OP_ENUM(opcode, flags) opcode = opcode##_id | (flags),
 221     FOR_EACH_DFG_OP(DFG_OP_ENUM)
 222 #undef DFG_OP_ENUM
 223 };
 224
 225 // This type used in passing an immediate argument to Node constructor;
 226 // distinguishes an immediate value (typically an index into a CodeBlock data structure -
 227 // a constant index, argument, or identifier) from a NodeIndex.
 228 struct OpInfo {
 229     explicit OpInfo(unsigned value) : m_value(value) {}
 230     unsigned m_value;
 231 };
 232
 233 // === Node ===
 234 //
 235 // Node represents a single operation in the data flow graph.
 236 struct Node {
 237     enum VarArgTag { VarArg };
 238
 239     // Construct a node with up to 3 children, no immediate value.
 240     Node(NodeType op, CodeOrigin codeOrigin, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
 241         : op(op)
 242         , codeOrigin(codeOrigin)
 243         , m_virtualRegister(InvalidVirtualRegister)
 244         , m_refCount(0)
 245     {
 246         ASSERT(!(op & NodeHasVarArgs));
 247         children.fixed.child1 = child1;
 248         children.fixed.child2 = child2;
 249         children.fixed.child3 = child3;
 250     }
 251
 252     // Construct a node with up to 3 children and an immediate value.
 253     Node(NodeType op, CodeOrigin codeOrigin, OpInfo imm, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
 254         : op(op)
 255         , codeOrigin(codeOrigin)
 256         , m_virtualRegister(InvalidVirtualRegister)
 257         , m_refCount(0)
 258         , m_opInfo(imm.m_value)
 259     {
 260         ASSERT(!(op & NodeHasVarArgs));
 261         children.fixed.child1 = child1;
 262         children.fixed.child2 = child2;
 263         children.fixed.child3 = child3;
 264     }
 265
 266     // Construct a node with up to 3 children and two immediate values.
 267     Node(NodeType op, CodeOrigin codeOrigin, OpInfo imm1, OpInfo imm2, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
 268         : op(op)
 269         , codeOrigin(codeOrigin)
 270         , m_virtualRegister(InvalidVirtualRegister)
 271         , m_refCount(0)
 272         , m_opInfo(imm1.m_value)
 273         , m_opInfo2(imm2.m_value)
 274     {
 275         ASSERT(!(op & NodeHasVarArgs));
 276         children.fixed.child1 = child1;
 277         children.fixed.child2 = child2;
 278         children.fixed.child3 = child3;
 279     }
 280
 281     // Construct a node with a variable number of children and two immediate values.
 282     Node(VarArgTag, NodeType op, CodeOrigin codeOrigin, OpInfo imm1, OpInfo imm2, unsigned firstChild, unsigned numChildren)
 283         : op(op)
 284         , codeOrigin(codeOrigin)
 285         , m_virtualRegister(InvalidVirtualRegister)
 286         , m_refCount(0)
 287         , m_opInfo(imm1.m_value)
 288         , m_opInfo2(imm2.m_value)
 289     {
 290         ASSERT(op & NodeHasVarArgs);
 291         children.variable.firstChild = firstChild;
 292         children.variable.numChildren = numChildren;
 293     }
 294
 295     bool mustGenerate()
 296     {
 297         return op & NodeMustGenerate;
 298     }
 299
 300     bool isConstant()
 301     {
 302         return op == JSConstant;
 303     }
 304
 305     unsigned constantNumber()
 306     {
 307         ASSERT(isConstant());
 308         return m_opInfo;
 309     }
 310
 311     JSValue valueOfJSConstant(CodeBlock* codeBlock)
 312     {
 313         return codeBlock->constantRegister(FirstConstantRegisterIndex + constantNumber()).get();
 314     }
 315
 316     bool isInt32Constant(CodeBlock* codeBlock)
 317     {
 318         return isConstant() && valueOfJSConstant(codeBlock).isInt32();
 319     }
 320
 321     bool isDoubleConstant(CodeBlock* codeBlock)
 322     {
 323         bool result = isConstant() && valueOfJSConstant(codeBlock).isDouble();
 324         if (result)
 325             ASSERT(!isInt32Constant(codeBlock));
 326         return result;
 327     }
 328
 329     bool isNumberConstant(CodeBlock* codeBlock)
 330     {
 331         bool result = isConstant() && valueOfJSConstant(codeBlock).isNumber();
 332         ASSERT(result == (isInt32Constant(codeBlock) || isDoubleConstant(codeBlock)));
 333         return result;
 334     }
 335
 336     bool isBooleanConstant(CodeBlock* codeBlock)
 337     {
 338         return isConstant() && valueOfJSConstant(codeBlock).isBoolean();
 339     }
 340
 341     int32_t valueOfInt32Constant(CodeBlock* codeBlock)
 342     {
 343         ASSERT(isInt32Constant(codeBlock));
 344         return valueOfJSConstant(codeBlock).asInt32();
 345     }
 346
 347     double valueOfNumberConstant(CodeBlock* codeBlock)
 348     {
 349         ASSERT(isNumberConstant(codeBlock));
 350         return valueOfJSConstant(codeBlock).uncheckedGetNumber();
 351     }
 352
 353     bool valueOfBooleanConstant(CodeBlock* codeBlock)
 354     {
 355         ASSERT(isBooleanConstant(codeBlock));
 356         return valueOfJSConstant(codeBlock).getBoolean();
 357     }
 358
 359     bool hasLocal()
 360     {
 361         return op == GetLocal || op == SetLocal;
 362     }
 363
 364     VirtualRegister local()
 365     {
 366         ASSERT(hasLocal());
 367         return (VirtualRegister)m_opInfo;
 368     }
 369
 370 #if !ASSERT_DISABLED
 371     // If we want to use this in production code, should make it faster -
 372     // e.g. make hasIdentifier a flag in the bitfield.
 373     bool hasIdentifier()
 374     {
 375         return op == GetById || op == PutById || op == PutByIdDirect || op == GetMethod
 376             || op == Resolve || op == ResolveBase || op == ResolveBaseStrictPut;
 377     }
 378 #endif
 379
 380     unsigned identifierNumber()
 381     {
 382         ASSERT(hasIdentifier());
 383         return m_opInfo;
 384     }
 385
 386     bool hasVarNumber()
 387     {
 388         return op == GetGlobalVar || op == PutGlobalVar;
 389     }
 390
 391     unsigned varNumber()
 392     {
 393         ASSERT(hasVarNumber());
 394         return m_opInfo;
 395     }
 396
 397     bool hasResult()
 398     {
 399         return op & NodeResultMask;
 400     }
 401
 402     bool hasInt32Result()
 403     {
 404         return (op & NodeResultMask) == NodeResultInt32;
 405     }
 406
 407     bool hasNumberResult()
 408     {
 409         return (op & NodeResultMask) == NodeResultNumber;
 410     }
 411
 412     bool hasJSResult()
 413     {
 414         return (op & NodeResultMask) == NodeResultJS;
 415     }
 416
 417     bool hasBooleanResult()
 418     {
 419         return (op & NodeResultMask) == NodeResultBoolean;
 420     }
 421
 422     bool isJump()
 423     {
 424         return op & NodeIsJump;
 425     }
 426
 427     bool isBranch()
 428     {
 429         return op & NodeIsBranch;
 430     }
 431
 432     bool isTerminal()
 433     {
 434         return op & NodeIsTerminal;
 435     }
 436
 437     unsigned takenBytecodeOffset()
 438     {
 439         ASSERT(isBranch() || isJump());
 440         return m_opInfo;
 441     }
 442
 443     unsigned notTakenBytecodeOffset()
 444     {
 445         ASSERT(isBranch());
 446         return m_opInfo2;
 447     }
 448
 449     bool hasPrediction()
 450     {
 451         switch (op) {
 452         case GetById:
 453         case GetMethod:
 454         case GetByVal:
 455         case Call:
 456         case Construct:
 457             return true;
 458         default:
 459             return false;
 460         }
 461     }
 462
 463     PredictedType getPrediction()
 464     {
 465         ASSERT(hasPrediction());
 466         return static_cast<PredictedType>(m_opInfo2);
 467     }
 468
 469     bool predict(PredictedType prediction, PredictionSource source)
 470     {
 471         ASSERT(hasPrediction());
 472
 473         // We have previously found empirically that ascribing static predictions
 474         // to heap loads as well as calls is not profitable, as these predictions
 475         // are wrong too often. Hence, this completely ignores static predictions.
 476         if (source == WeakPrediction)
 477             return false;
 478
 479         if (prediction == PredictNone)
 480             return false;
 481
 482         ASSERT(source == StrongPrediction);
 483
 484         return mergePrediction(m_opInfo2, makePrediction(prediction, source));
 485     }
 486
 487     VirtualRegister virtualRegister()
 488     {
 489         ASSERT(hasResult());
 490         ASSERT(m_virtualRegister != InvalidVirtualRegister);
 491         return m_virtualRegister;
 492     }
 493
 494     void setVirtualRegister(VirtualRegister virtualRegister)
 495     {
 496         ASSERT(hasResult());
 497         ASSERT(m_virtualRegister == InvalidVirtualRegister);
 498         m_virtualRegister = virtualRegister;
 499     }
 500
 501     bool shouldGenerate()
 502     {
 503         return m_refCount && op != Phi;
 504     }
 505
 506     unsigned refCount()
 507     {
 508         return m_refCount;
 509     }
 510
 511     // returns true when ref count passes from 0 to 1.
 512     bool ref()
 513     {
 514         return !m_refCount++;
 515     }
 516
 517     unsigned adjustedRefCount()
 518     {
 519         return mustGenerate() ? m_refCount - 1 : m_refCount;
 520     }
 521
 522     NodeIndex child1()
 523     {
 524         ASSERT(!(op & NodeHasVarArgs));
 525         return children.fixed.child1;
 526     }
 527
 528     // This is useful if you want to do a fast check on the first child
 529     // before also doing a check on the opcode. Use this with care and
 530     // avoid it if possible.
 531     NodeIndex child1Unchecked()
 532     {
 533         return children.fixed.child1;
 534     }
 535
 536     NodeIndex child2()
 537     {
 538         ASSERT(!(op & NodeHasVarArgs));
 539         return children.fixed.child2;
 540     }
 541
 542     NodeIndex child3()
 543     {
 544         ASSERT(!(op & NodeHasVarArgs));
 545         return children.fixed.child3;
 546     }
 547
 548     unsigned firstChild()
 549     {
 550         ASSERT(op & NodeHasVarArgs);
 551         return children.variable.firstChild;
 552     }
 553
 554     unsigned numChildren()
 555     {
 556         ASSERT(op & NodeHasVarArgs);
 557         return children.variable.numChildren;
 558     }
 559
 560     // This enum value describes the type of the node.
 561     NodeType op;
 562     // Used to look up exception handling information (currently implemented as a bytecode index).
 563     CodeOrigin codeOrigin;
 564     // References to up to 3 children (0 for no child).
 565     union {
 566         struct {
 567             NodeIndex child1, child2, child3;
 568         } fixed;
 569         struct {
 570             unsigned firstChild;
 571             unsigned numChildren;
 572         } variable;
 573     } children;
 574
 575 private:
 576     // The virtual register number (spill location) associated with this .
 577     VirtualRegister m_virtualRegister;
 578     // The number of uses of the result of this operation (+1 for 'must generate' nodes, which have side-effects).
 579     unsigned m_refCount;
 580     // Immediate values, accesses type-checked via accessors above.
 581     unsigned m_opInfo, m_opInfo2;
 582 };
 583
 584 } } // namespace JSC::DFG
 585
 586 #endif
 587 #endif