Source/JavaScriptCore/dfg/DFGClobberize.h

   1 /*
   2  * Copyright (C) 2013-2016 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 DFGClobberize_h
  27 #define DFGClobberize_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGAbstractHeap.h"
  32 #include "DFGEdgeUsesStructure.h"
  33 #include "DFGGraph.h"
  34 #include "DFGHeapLocation.h"
  35 #include "DFGLazyNode.h"
  36 #include "DFGPureValue.h"
  37
  38 namespace JSC { namespace DFG {
  39
  40 template<typename ReadFunctor, typename WriteFunctor, typename DefFunctor>
  41 void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFunctor& write, const DefFunctor& def)
  42 {
  43     // Some notes:
  44     //
  45     // - The canonical way of clobbering the world is to read world and write
  46     //   heap. This is because World subsumes Heap and Stack, and Stack can be
  47     //   read by anyone but only written to by explicit stack writing operations.
  48     //   Of course, claiming to also write World is not wrong; it'll just
  49     //   pessimise some important optimizations.
  50     //
  51     // - We cannot hoist, or sink, anything that has effects. This means that the
  52     //   easiest way of indicating that something cannot be hoisted is to claim
  53     //   that it side-effects some miscellaneous thing.
  54     //
  55     // - We cannot hoist forward-exiting nodes without some additional effort. I
  56     //   believe that what it comes down to is that forward-exiting generally have
  57     //   their NodeExitsForward cleared upon hoist, except for forward-exiting
  58     //   nodes that take bogus state as their input. Those are substantially
  59     //   harder. We disable it for now. In the future we could enable it by having
  60     //   versions of those nodes that backward-exit instead, but I'm not convinced
  61     //   of the soundness.
  62     //
  63     // - Some nodes lie, and claim that they do not read the JSCell_structureID,
  64     //   JSCell_typeInfoFlags, etc. These are nodes that use the structure in a way
  65     //   that does not depend on things that change under structure transitions.
  66     //
  67     // - It's implicitly understood that OSR exits read the world. This is why we
  68     //   generally don't move or eliminate stores. Every node can exit, so the
  69     //   read set does not reflect things that would be read if we exited.
  70     //   Instead, the read set reflects what the node will have to read if it
  71     //   *doesn't* exit.
  72     //
  73     // - Broadly, we don't say that we're reading something if that something is
  74     //   immutable.
  75     //
  76     // - We try to make this work even prior to type inference, just so that we
  77     //   can use it for IR dumps. No promises on whether the answers are sound
  78     //   prior to type inference - though they probably could be if we did some
  79     //   small hacking.
  80     //
  81     // - If you do read(Stack) or read(World), then make sure that readTop() in
  82     //   PreciseLocalClobberize is correct.
  83
  84     // While read() and write() are fairly self-explanatory - they track what sorts of things the
  85     // node may read or write - the def() functor is more tricky. It tells you the heap locations
  86     // (not just abstract heaps) that are defined by a node. A heap location comprises an abstract
  87     // heap, some nodes, and a LocationKind. Briefly, a location defined by a node is a location
  88     // whose value can be deduced from looking at the node itself. The locations returned must obey
  89     // the following properties:
  90     //
  91     // - If someone wants to CSE a load from the heap, then a HeapLocation object should be
  92     //   sufficient to find a single matching node.
  93     //
  94     // - The abstract heap is the only abstract heap that could be clobbered to invalidate any such
  95     //   CSE attempt. I.e. if clobberize() reports that on every path between some node and a node
  96     //   that defines a HeapLocation that it wanted, there were no writes to any abstract heap that
  97     //   overlap the location's heap, then we have a sound match. Effectively, the semantics of
  98     //   write() and def() are intertwined such that for them to be sound they must agree on what
  99     //   is CSEable.
 100     //
 101     // read(), write(), and def() for heap locations is enough to do GCSE on effectful things. To
 102     // keep things simple, this code will also def() pure things. def() must be overloaded to also
 103     // accept PureValue. This way, a client of clobberize() can implement GCSE entirely using the
 104     // information that clobberize() passes to write() and def(). Other clients of clobberize() can
 105     // just ignore def() by using a NoOpClobberize functor.
 106
 107     if (edgesUseStructure(graph, node))
 108         read(JSCell_structureID);
 109
 110     // We allow the runtime to perform a stack scan at any time. We don't model which nodes get implemented
 111     // by calls into the runtime. For debugging we might replace the implementation of any node with a call
 112     // to the runtime, and that call may walk stack. Therefore, each node must read() anything that a stack
 113     // scan would read. That's what this does.
 114     for (InlineCallFrame* inlineCallFrame = node->origin.semantic.inlineCallFrame; inlineCallFrame; inlineCallFrame = inlineCallFrame->directCaller.inlineCallFrame) {
 115         if (inlineCallFrame->isClosureCall)
 116             read(AbstractHeap(Stack, inlineCallFrame->stackOffset + CallFrameSlot::callee));
 117         if (inlineCallFrame->isVarargs())
 118             read(AbstractHeap(Stack, inlineCallFrame->stackOffset + CallFrameSlot::argumentCount));
 119     }
 120
 121     // We don't want to specifically account which nodes can read from the scope
 122     // when the debugger is enabled. It's helpful to just claim all nodes do.
 123     // Specifically, if a node allocates, this may call into the debugger's machinery.
 124     // The debugger's machinery is free to take a stack trace and try to read from
 125     // a scope which is expected to be flushed to the stack.
 126     if (graph.hasDebuggerEnabled()) {
 127         ASSERT(!node->origin.semantic.inlineCallFrame);
 128         read(AbstractHeap(Stack, graph.m_codeBlock->scopeRegister()));
 129     }
 130
 131
 132     switch (node->op()) {
 133     case JSConstant:
 134     case DoubleConstant:
 135     case Int52Constant:
 136         def(PureValue(node, node->constant()));
 137         return;
 138
 139     case Identity:
 140     case Phantom:
 141     case Check:
 142     case ExtractOSREntryLocal:
 143     case CheckStructureImmediate:
 144         return;
 145
 146     case LazyJSConstant:
 147         // We should enable CSE of LazyJSConstant. It's a little annoying since LazyJSValue has
 148         // more bits than we currently have in PureValue.
 149         return;
 150
 151     case ArithIMul:
 152     case ArithMin:
 153     case ArithMax:
 154     case ArithPow:
 155     case GetScope:
 156     case SkipScope:
 157     case GetGlobalObject:
 158     case StringCharCodeAt:
 159     case CompareStrictEq:
 160     case CompareEqPtr:
 161     case IsJSArray:
 162     case IsEmpty:
 163     case IsUndefined:
 164     case IsBoolean:
 165     case IsNumber:
 166     case IsString:
 167     case IsObject:
 168     case IsRegExpObject:
 169     case IsTypedArrayView:
 170     case LogicalNot:
 171     case CheckInBounds:
 172     case DoubleRep:
 173     case ValueRep:
 174     case Int52Rep:
 175     case BooleanToNumber:
 176     case FiatInt52:
 177     case MakeRope:
 178     case StrCat:
 179     case ValueToInt32:
 180     case GetExecutable:
 181     case BottomValue:
 182     case TypeOf:
 183         def(PureValue(node));
 184         return;
 185
 186     case ArithCos:
 187     case ArithFRound:
 188     case ArithLog:
 189     case ArithSin:
 190     case ArithSqrt:
 191         if (node->child1().useKind() == DoubleRepUse)
 192             def(PureValue(node));
 193         else {
 194             read(World);
 195             write(Heap);
 196         }
 197         return;
 198
 199     case ArithAbs:
 200         if (node->child1().useKind() == Int32Use || node->child1().useKind() == DoubleRepUse)
 201             def(PureValue(node));
 202         else {
 203             read(World);
 204             write(Heap);
 205         }
 206         return;
 207
 208     case ArithClz32:
 209         if (node->child1().useKind() == Int32Use || node->child1().useKind() == KnownInt32Use)
 210             def(PureValue(node));
 211         else {
 212             read(World);
 213             write(Heap);
 214         }
 215         return;
 216
 217     case BitAnd:
 218     case BitOr:
 219     case BitXor:
 220     case BitLShift:
 221     case BitRShift:
 222     case BitURShift:
 223         if (node->child1().useKind() == UntypedUse || node->child2().useKind() == UntypedUse) {
 224             read(World);
 225             write(Heap);
 226             return;
 227         }
 228         def(PureValue(node));
 229         return;
 230
 231     case ArithRandom:
 232         read(MathDotRandomState);
 233         write(MathDotRandomState);
 234         return;
 235
 236     case HasGenericProperty:
 237     case HasStructureProperty:
 238     case GetEnumerableLength:
 239     case GetPropertyEnumerator: {
 240         read(Heap);
 241         write(SideState);
 242         return;
 243     }
 244
 245     case GetDirectPname: {
 246         // This reads and writes heap because it can end up calling a generic getByVal
 247         // if the Structure changed, which could in turn end up calling a getter.
 248         read(World);
 249         write(Heap);
 250         return;
 251     }
 252
 253     case ToIndexString:
 254     case GetEnumeratorStructurePname:
 255     case GetEnumeratorGenericPname: {
 256         def(PureValue(node));
 257         return;
 258     }
 259
 260     case HasIndexedProperty: {
 261         read(JSObject_butterfly);
 262         ArrayMode mode = node->arrayMode();
 263         switch (mode.type()) {
 264         case Array::Int32: {
 265             if (mode.isInBounds()) {
 266                 read(Butterfly_publicLength);
 267                 read(IndexedInt32Properties);
 268                 def(HeapLocation(HasIndexedPropertyLoc, IndexedInt32Properties, node->child1(), node->child2()), LazyNode(node));
 269                 return;
 270             }
 271             read(Heap);
 272             return;
 273         }
 274
 275         case Array::Double: {
 276             if (mode.isInBounds()) {
 277                 read(Butterfly_publicLength);
 278                 read(IndexedDoubleProperties);
 279                 def(HeapLocation(HasIndexedPropertyLoc, IndexedDoubleProperties, node->child1(), node->child2()), LazyNode(node));
 280                 return;
 281             }
 282             read(Heap);
 283             return;
 284         }
 285
 286         case Array::Contiguous: {
 287             if (mode.isInBounds()) {
 288                 read(Butterfly_publicLength);
 289                 read(IndexedContiguousProperties);
 290                 def(HeapLocation(HasIndexedPropertyLoc, IndexedContiguousProperties, node->child1(), node->child2()), LazyNode(node));
 291                 return;
 292             }
 293             read(Heap);
 294             return;
 295         }
 296
 297         case Array::ArrayStorage: {
 298             if (mode.isInBounds()) {
 299                 read(Butterfly_vectorLength);
 300                 read(IndexedArrayStorageProperties);
 301                 return;
 302             }
 303             read(Heap);
 304             return;
 305         }
 306
 307         default: {
 308             read(World);
 309             write(Heap);
 310             return;
 311         }
 312         }
 313         RELEASE_ASSERT_NOT_REACHED();
 314         return;
 315     }
 316
 317     case StringFromCharCode:
 318         switch (node->child1().useKind()) {
 319         case Int32Use:
 320             def(PureValue(node));
 321             return;
 322         case UntypedUse:
 323             read(World);
 324             write(Heap);
 325             return;
 326         default:
 327             DFG_CRASH(graph, node, "Bad use kind");
 328         }
 329         return;
 330
 331     case ArithAdd:
 332     case ArithNegate:
 333     case ArithMod:
 334     case DoubleAsInt32:
 335     case UInt32ToNumber:
 336         def(PureValue(node, node->arithMode()));
 337         return;
 338
 339     case ArithDiv:
 340     case ArithMul:
 341     case ArithSub:
 342         switch (node->binaryUseKind()) {
 343         case Int32Use:
 344         case Int52RepUse:
 345         case DoubleRepUse:
 346             def(PureValue(node, node->arithMode()));
 347             return;
 348         case UntypedUse:
 349             read(World);
 350             write(Heap);
 351             return;
 352         default:
 353             DFG_CRASH(graph, node, "Bad use kind");
 354         }
 355
 356     case ArithRound:
 357     case ArithFloor:
 358     case ArithCeil:
 359     case ArithTrunc:
 360         def(PureValue(node, static_cast<uintptr_t>(node->arithRoundingMode())));
 361         return;
 362
 363     case CheckCell:
 364         def(PureValue(CheckCell, AdjacencyList(AdjacencyList::Fixed, node->child1()), node->cellOperand()));
 365         return;
 366
 367     case CheckNotEmpty:
 368         def(PureValue(CheckNotEmpty, AdjacencyList(AdjacencyList::Fixed, node->child1())));
 369         return;
 370
 371     case CheckStringIdent:
 372         def(PureValue(CheckStringIdent, AdjacencyList(AdjacencyList::Fixed, node->child1()), node->uidOperand()));
 373         return;
 374
 375     case ConstantStoragePointer:
 376         def(PureValue(node, node->storagePointer()));
 377         return;
 378
 379     case MovHint:
 380     case ZombieHint:
 381     case ExitOK:
 382     case KillStack:
 383     case Upsilon:
 384     case Phi:
 385     case PhantomLocal:
 386     case SetArgument:
 387     case Jump:
 388     case Branch:
 389     case Switch:
 390     case Throw:
 391     case ForceOSRExit:
 392     case CheckBadCell:
 393     case Return:
 394     case Unreachable:
 395     case CheckTierUpInLoop:
 396     case CheckTierUpAtReturn:
 397     case CheckTierUpAndOSREnter:
 398     case LoopHint:
 399     case ProfileType:
 400     case ProfileControlFlow:
 401     case StoreBarrier:
 402     case PutHint:
 403         write(SideState);
 404         return;
 405
 406     case InvalidationPoint:
 407         write(SideState);
 408         def(HeapLocation(InvalidationPointLoc, Watchpoint_fire), LazyNode(node));
 409         return;
 410
 411     case Flush:
 412         read(AbstractHeap(Stack, node->local()));
 413         write(SideState);
 414         return;
 415
 416     case NotifyWrite:
 417         write(Watchpoint_fire);
 418         write(SideState);
 419         return;
 420
 421     case CreateActivation: {
 422         SymbolTable* table = node->castOperand<SymbolTable*>();
 423         if (table->singletonScope()->isStillValid())
 424             write(Watchpoint_fire);
 425         read(HeapObjectCount);
 426         write(HeapObjectCount);
 427         return;
 428     }
 429
 430     case CreateDirectArguments:
 431     case CreateScopedArguments:
 432     case CreateClonedArguments:
 433         read(Stack);
 434         read(HeapObjectCount);
 435         write(HeapObjectCount);
 436         return;
 437
 438     case PhantomDirectArguments:
 439     case PhantomClonedArguments:
 440         // DFG backend requires that the locals that this reads are flushed. FTL backend can handle those
 441         // locals being promoted.
 442         if (!isFTL(graph.m_plan.mode))
 443             read(Stack);
 444
 445         // Even though it's phantom, it still has the property that one can't be replaced with another.
 446         read(HeapObjectCount);
 447         write(HeapObjectCount);
 448         return;
 449
 450     case CallObjectConstructor:
 451     case ToThis:
 452     case CreateThis:
 453         read(MiscFields);
 454         read(HeapObjectCount);
 455         write(HeapObjectCount);
 456         return;
 457
 458     case IsObjectOrNull:
 459         read(MiscFields);
 460         def(HeapLocation(IsObjectOrNullLoc, MiscFields, node->child1()), LazyNode(node));
 461         return;
 462
 463     case IsFunction:
 464         read(MiscFields);
 465         def(HeapLocation(IsFunctionLoc, MiscFields, node->child1()), LazyNode(node));
 466         return;
 467
 468     case GetById:
 469     case GetByIdFlush:
 470     case GetByIdWithThis:
 471     case GetByValWithThis:
 472     case PutById:
 473     case PutByIdWithThis:
 474     case PutByValWithThis:
 475     case PutByIdFlush:
 476     case PutByIdDirect:
 477     case PutGetterById:
 478     case PutSetterById:
 479     case PutGetterSetterById:
 480     case PutGetterByVal:
 481     case PutSetterByVal:
 482     case DeleteById:
 483     case DeleteByVal:
 484     case ArrayPush:
 485     case ArrayPop:
 486     case Call:
 487     case TailCallInlinedCaller:
 488     case Construct:
 489     case CallVarargs:
 490     case CallForwardVarargs:
 491     case TailCallVarargsInlinedCaller:
 492     case TailCallForwardVarargsInlinedCaller:
 493     case ConstructVarargs:
 494     case ConstructForwardVarargs:
 495     case ToPrimitive:
 496     case In:
 497     case ValueAdd:
 498     case SetFunctionName:
 499     case GetDynamicVar:
 500     case PutDynamicVar:
 501     case ResolveScope:
 502         read(World);
 503         write(Heap);
 504         return;
 505
 506     case CallEval:
 507         ASSERT(!node->origin.semantic.inlineCallFrame);
 508         read(AbstractHeap(Stack, graph.m_codeBlock->scopeRegister()));
 509         read(AbstractHeap(Stack, virtualRegisterForArgument(0)));
 510         read(World);
 511         write(Heap);
 512         return;
 513
 514     case TailCall:
 515     case TailCallVarargs:
 516     case TailCallForwardVarargs:
 517         read(World);
 518         write(SideState);
 519         return;
 520
 521     case GetGetter:
 522         read(GetterSetter_getter);
 523         def(HeapLocation(GetterLoc, GetterSetter_getter, node->child1()), LazyNode(node));
 524         return;
 525
 526     case GetSetter:
 527         read(GetterSetter_setter);
 528         def(HeapLocation(SetterLoc, GetterSetter_setter, node->child1()), LazyNode(node));
 529         return;
 530
 531     case GetCallee:
 532         read(AbstractHeap(Stack, CallFrameSlot::callee));
 533         def(HeapLocation(StackLoc, AbstractHeap(Stack, CallFrameSlot::callee)), LazyNode(node));
 534         return;
 535
 536     case GetArgumentCountIncludingThis:
 537         read(AbstractHeap(Stack, CallFrameSlot::argumentCount));
 538         def(HeapLocation(StackPayloadLoc, AbstractHeap(Stack, CallFrameSlot::argumentCount)), LazyNode(node));
 539         return;
 540
 541     case GetRestLength:
 542         read(Stack);
 543         return;
 544
 545     case GetLocal:
 546         read(AbstractHeap(Stack, node->local()));
 547         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->local())), LazyNode(node));
 548         return;
 549
 550     case SetLocal:
 551         write(AbstractHeap(Stack, node->local()));
 552         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->local())), LazyNode(node->child1().node()));
 553         return;
 554
 555     case GetStack: {
 556         AbstractHeap heap(Stack, node->stackAccessData()->local);
 557         read(heap);
 558         def(HeapLocation(StackLoc, heap), LazyNode(node));
 559         return;
 560     }
 561
 562     case PutStack: {
 563         AbstractHeap heap(Stack, node->stackAccessData()->local);
 564         write(heap);
 565         def(HeapLocation(StackLoc, heap), LazyNode(node->child1().node()));
 566         return;
 567     }
 568
 569     case LoadVarargs: {
 570         read(World);
 571         write(Heap);
 572         LoadVarargsData* data = node->loadVarargsData();
 573         write(AbstractHeap(Stack, data->count.offset()));
 574         for (unsigned i = data->limit; i--;)
 575             write(AbstractHeap(Stack, data->start.offset() + static_cast<int>(i)));
 576         return;
 577     }
 578
 579     case ForwardVarargs: {
 580         // We could be way more precise here.
 581         read(Stack);
 582
 583         LoadVarargsData* data = node->loadVarargsData();
 584         write(AbstractHeap(Stack, data->count.offset()));
 585         for (unsigned i = data->limit; i--;)
 586             write(AbstractHeap(Stack, data->start.offset() + static_cast<int>(i)));
 587         return;
 588     }
 589
 590     case GetLocalUnlinked:
 591         read(AbstractHeap(Stack, node->unlinkedLocal()));
 592         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->unlinkedLocal())), LazyNode(node));
 593         return;
 594
 595     case GetByVal: {
 596         ArrayMode mode = node->arrayMode();
 597         switch (mode.type()) {
 598         case Array::SelectUsingPredictions:
 599         case Array::Unprofiled:
 600         case Array::SelectUsingArguments:
 601             // Assume the worst since we don't have profiling yet.
 602             read(World);
 603             write(Heap);
 604             return;
 605
 606         case Array::ForceExit:
 607             write(SideState);
 608             return;
 609
 610         case Array::Generic:
 611             read(World);
 612             write(Heap);
 613             return;
 614
 615         case Array::String:
 616             if (mode.isOutOfBounds()) {
 617                 read(World);
 618                 write(Heap);
 619                 return;
 620             }
 621             // This appears to read nothing because it's only reading immutable data.
 622             def(PureValue(node, mode.asWord()));
 623             return;
 624
 625         case Array::DirectArguments:
 626             read(DirectArgumentsProperties);
 627             def(HeapLocation(IndexedPropertyLoc, DirectArgumentsProperties, node->child1(), node->child2()), LazyNode(node));
 628             return;
 629
 630         case Array::ScopedArguments:
 631             read(ScopeProperties);
 632             def(HeapLocation(IndexedPropertyLoc, ScopeProperties, node->child1(), node->child2()), LazyNode(node));
 633             return;
 634
 635         case Array::Int32:
 636             if (mode.isInBounds()) {
 637                 read(Butterfly_publicLength);
 638                 read(IndexedInt32Properties);
 639                 def(HeapLocation(IndexedPropertyLoc, IndexedInt32Properties, node->child1(), node->child2()), LazyNode(node));
 640                 return;
 641             }
 642             read(World);
 643             write(Heap);
 644             return;
 645
 646         case Array::Double:
 647             if (mode.isInBounds()) {
 648                 read(Butterfly_publicLength);
 649                 read(IndexedDoubleProperties);
 650                 def(HeapLocation(IndexedPropertyLoc, IndexedDoubleProperties, node->child1(), node->child2()), LazyNode(node));
 651                 return;
 652             }
 653             read(World);
 654             write(Heap);
 655             return;
 656
 657         case Array::Contiguous:
 658             if (mode.isInBounds()) {
 659                 read(Butterfly_publicLength);
 660                 read(IndexedContiguousProperties);
 661                 def(HeapLocation(IndexedPropertyLoc, IndexedContiguousProperties, node->child1(), node->child2()), LazyNode(node));
 662                 return;
 663             }
 664             read(World);
 665             write(Heap);
 666             return;
 667
 668         case Array::Undecided:
 669             def(PureValue(node));
 670             return;
 671
 672         case Array::ArrayStorage:
 673         case Array::SlowPutArrayStorage:
 674             if (mode.isInBounds()) {
 675                 read(Butterfly_vectorLength);
 676                 read(IndexedArrayStorageProperties);
 677                 return;
 678             }
 679             read(World);
 680             write(Heap);
 681             return;
 682
 683         case Array::Int8Array:
 684         case Array::Int16Array:
 685         case Array::Int32Array:
 686         case Array::Uint8Array:
 687         case Array::Uint8ClampedArray:
 688         case Array::Uint16Array:
 689         case Array::Uint32Array:
 690         case Array::Float32Array:
 691         case Array::Float64Array:
 692             read(TypedArrayProperties);
 693             read(MiscFields);
 694             def(HeapLocation(IndexedPropertyLoc, TypedArrayProperties, node->child1(), node->child2()), LazyNode(node));
 695             return;
 696         // We should not get an AnyTypedArray in a GetByVal as AnyTypedArray is only created from intrinsics, which
 697         // are only added from Inline Caching a GetById.
 698         case Array::AnyTypedArray:
 699             DFG_CRASH(graph, node, "impossible array mode for get");
 700             return;
 701         }
 702         RELEASE_ASSERT_NOT_REACHED();
 703         return;
 704     }
 705
 706     case GetMyArgumentByVal:
 707     case GetMyArgumentByValOutOfBounds: {
 708         read(Stack);
 709         // FIXME: It would be trivial to have a def here.
 710         // https://bugs.webkit.org/show_bug.cgi?id=143077
 711         return;
 712     }
 713
 714     case PutByValDirect:
 715     case PutByVal:
 716     case PutByValAlias: {
 717         ArrayMode mode = node->arrayMode();
 718         Node* base = graph.varArgChild(node, 0).node();
 719         Node* index = graph.varArgChild(node, 1).node();
 720         Node* value = graph.varArgChild(node, 2).node();
 721         switch (mode.modeForPut().type()) {
 722         case Array::SelectUsingPredictions:
 723         case Array::SelectUsingArguments:
 724         case Array::Unprofiled:
 725         case Array::Undecided:
 726             // Assume the worst since we don't have profiling yet.
 727             read(World);
 728             write(Heap);
 729             return;
 730
 731         case Array::ForceExit:
 732             write(SideState);
 733             return;
 734
 735         case Array::Generic:
 736             read(World);
 737             write(Heap);
 738             return;
 739
 740         case Array::Int32:
 741             if (node->arrayMode().isOutOfBounds()) {
 742                 read(World);
 743                 write(Heap);
 744                 return;
 745             }
 746             read(Butterfly_publicLength);
 747             read(Butterfly_vectorLength);
 748             read(IndexedInt32Properties);
 749             write(IndexedInt32Properties);
 750             if (node->arrayMode().mayStoreToHole())
 751                 write(Butterfly_publicLength);
 752             def(HeapLocation(IndexedPropertyLoc, IndexedInt32Properties, base, index), LazyNode(value));
 753             return;
 754
 755         case Array::Double:
 756             if (node->arrayMode().isOutOfBounds()) {
 757                 read(World);
 758                 write(Heap);
 759                 return;
 760             }
 761             read(Butterfly_publicLength);
 762             read(Butterfly_vectorLength);
 763             read(IndexedDoubleProperties);
 764             write(IndexedDoubleProperties);
 765             if (node->arrayMode().mayStoreToHole())
 766                 write(Butterfly_publicLength);
 767             def(HeapLocation(IndexedPropertyLoc, IndexedDoubleProperties, base, index), LazyNode(value));
 768             return;
 769
 770         case Array::Contiguous:
 771             if (node->arrayMode().isOutOfBounds()) {
 772                 read(World);
 773                 write(Heap);
 774                 return;
 775             }
 776             read(Butterfly_publicLength);
 777             read(Butterfly_vectorLength);
 778             read(IndexedContiguousProperties);
 779             write(IndexedContiguousProperties);
 780             if (node->arrayMode().mayStoreToHole())
 781                 write(Butterfly_publicLength);
 782             def(HeapLocation(IndexedPropertyLoc, IndexedContiguousProperties, base, index), LazyNode(value));
 783             return;
 784
 785         case Array::ArrayStorage:
 786         case Array::SlowPutArrayStorage:
 787             // Give up on life for now.
 788             read(World);
 789             write(Heap);
 790             return;
 791
 792         case Array::Int8Array:
 793         case Array::Int16Array:
 794         case Array::Int32Array:
 795         case Array::Uint8Array:
 796         case Array::Uint8ClampedArray:
 797         case Array::Uint16Array:
 798         case Array::Uint32Array:
 799         case Array::Float32Array:
 800         case Array::Float64Array:
 801             read(MiscFields);
 802             write(TypedArrayProperties);
 803             // FIXME: We can't def() anything here because these operations truncate their inputs.
 804             // https://bugs.webkit.org/show_bug.cgi?id=134737
 805             return;
 806         case Array::AnyTypedArray:
 807         case Array::String:
 808         case Array::DirectArguments:
 809         case Array::ScopedArguments:
 810             DFG_CRASH(graph, node, "impossible array mode for put");
 811             return;
 812         }
 813         RELEASE_ASSERT_NOT_REACHED();
 814         return;
 815     }
 816
 817     case CheckStructure:
 818         read(JSCell_structureID);
 819         return;
 820
 821     case CheckArray:
 822         read(JSCell_indexingType);
 823         read(JSCell_typeInfoType);
 824         read(JSCell_structureID);
 825         return;
 826
 827     case CheckTypeInfoFlags:
 828         read(JSCell_typeInfoFlags);
 829         def(HeapLocation(CheckTypeInfoFlagsLoc, JSCell_typeInfoFlags, node->child1()), LazyNode(node));
 830         return;
 831
 832     case OverridesHasInstance:
 833         read(JSCell_typeInfoFlags);
 834         def(HeapLocation(OverridesHasInstanceLoc, JSCell_typeInfoFlags, node->child1()), LazyNode(node));
 835         return;
 836
 837     case InstanceOf:
 838         read(JSCell_structureID);
 839         def(HeapLocation(InstanceOfLoc, JSCell_structureID, node->child1(), node->child2()), LazyNode(node));
 840         return;
 841
 842     case InstanceOfCustom:
 843         read(World);
 844         write(Heap);
 845         return;
 846
 847     case PutStructure:
 848         write(JSCell_structureID);
 849         write(JSCell_typeInfoType);
 850         write(JSCell_typeInfoFlags);
 851         write(JSCell_indexingType);
 852         return;
 853
 854     case AllocatePropertyStorage:
 855         write(JSObject_butterfly);
 856         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
 857         return;
 858
 859     case ReallocatePropertyStorage:
 860         read(JSObject_butterfly);
 861         write(JSObject_butterfly);
 862         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
 863         return;
 864
 865     case GetButterfly:
 866         read(JSObject_butterfly);
 867         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
 868         return;
 869
 870     case Arrayify:
 871     case ArrayifyToStructure:
 872         read(JSCell_structureID);
 873         read(JSCell_indexingType);
 874         read(JSObject_butterfly);
 875         write(JSCell_structureID);
 876         write(JSCell_indexingType);
 877         write(JSObject_butterfly);
 878         write(Watchpoint_fire);
 879         return;
 880
 881     case GetIndexedPropertyStorage:
 882         if (node->arrayMode().type() == Array::String) {
 883             def(PureValue(node, node->arrayMode().asWord()));
 884             return;
 885         }
 886         read(MiscFields);
 887         def(HeapLocation(IndexedPropertyStorageLoc, MiscFields, node->child1()), LazyNode(node));
 888         return;
 889
 890     case GetTypedArrayByteOffset:
 891         read(MiscFields);
 892         def(HeapLocation(TypedArrayByteOffsetLoc, MiscFields, node->child1()), LazyNode(node));
 893         return;
 894
 895     case GetByOffset:
 896     case GetGetterSetterByOffset: {
 897         unsigned identifierNumber = node->storageAccessData().identifierNumber;
 898         AbstractHeap heap(NamedProperties, identifierNumber);
 899         read(heap);
 900         def(HeapLocation(NamedPropertyLoc, heap, node->child2()), LazyNode(node));
 901         return;
 902     }
 903
 904     case TryGetById: {
 905         read(Heap);
 906         return;
 907     }
 908
 909     case MultiGetByOffset: {
 910         read(JSCell_structureID);
 911         read(JSObject_butterfly);
 912         AbstractHeap heap(NamedProperties, node->multiGetByOffsetData().identifierNumber);
 913         read(heap);
 914         // FIXME: We cannot def() for MultiGetByOffset because CSE is not smart enough to decay it
 915         // to a CheckStructure.
 916         // https://bugs.webkit.org/show_bug.cgi?id=159859
 917         return;
 918     }
 919
 920     case MultiPutByOffset: {
 921         read(JSCell_structureID);
 922         read(JSObject_butterfly);
 923         AbstractHeap heap(NamedProperties, node->multiPutByOffsetData().identifierNumber);
 924         write(heap);
 925         if (node->multiPutByOffsetData().writesStructures())
 926             write(JSCell_structureID);
 927         if (node->multiPutByOffsetData().reallocatesStorage())
 928             write(JSObject_butterfly);
 929         def(HeapLocation(NamedPropertyLoc, heap, node->child1()), LazyNode(node->child2().node()));
 930         return;
 931     }
 932
 933     case PutByOffset: {
 934         unsigned identifierNumber = node->storageAccessData().identifierNumber;
 935         AbstractHeap heap(NamedProperties, identifierNumber);
 936         write(heap);
 937         def(HeapLocation(NamedPropertyLoc, heap, node->child2()), LazyNode(node->child3().node()));
 938         return;
 939     }
 940
 941     case GetArrayLength: {
 942         ArrayMode mode = node->arrayMode();
 943         switch (mode.type()) {
 944         case Array::Int32:
 945         case Array::Double:
 946         case Array::Contiguous:
 947         case Array::ArrayStorage:
 948         case Array::SlowPutArrayStorage:
 949             read(Butterfly_publicLength);
 950             def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node->child1()), LazyNode(node));
 951             return;
 952
 953         case Array::String:
 954             def(PureValue(node, mode.asWord()));
 955             return;
 956
 957         case Array::DirectArguments:
 958         case Array::ScopedArguments:
 959             read(MiscFields);
 960             def(HeapLocation(ArrayLengthLoc, MiscFields, node->child1()), LazyNode(node));
 961             return;
 962
 963         default:
 964             ASSERT(mode.isSomeTypedArrayView());
 965             read(MiscFields);
 966             def(HeapLocation(ArrayLengthLoc, MiscFields, node->child1()), LazyNode(node));
 967             return;
 968         }
 969     }
 970
 971     case GetClosureVar:
 972         read(AbstractHeap(ScopeProperties, node->scopeOffset().offset()));
 973         def(HeapLocation(ClosureVariableLoc, AbstractHeap(ScopeProperties, node->scopeOffset().offset()), node->child1()), LazyNode(node));
 974         return;
 975
 976     case PutClosureVar:
 977         write(AbstractHeap(ScopeProperties, node->scopeOffset().offset()));
 978         def(HeapLocation(ClosureVariableLoc, AbstractHeap(ScopeProperties, node->scopeOffset().offset()), node->child1()), LazyNode(node->child2().node()));
 979         return;
 980
 981     case GetRegExpObjectLastIndex:
 982         read(RegExpObject_lastIndex);
 983         def(HeapLocation(RegExpObjectLastIndexLoc, RegExpObject_lastIndex, node->child1()), LazyNode(node));
 984         return;
 985
 986     case SetRegExpObjectLastIndex:
 987         write(RegExpObject_lastIndex);
 988         def(HeapLocation(RegExpObjectLastIndexLoc, RegExpObject_lastIndex, node->child1()), LazyNode(node->child2().node()));
 989         return;
 990
 991     case RecordRegExpCachedResult:
 992         write(RegExpState);
 993         return;
 994
 995     case GetFromArguments: {
 996         AbstractHeap heap(DirectArgumentsProperties, node->capturedArgumentsOffset().offset());
 997         read(heap);
 998         def(HeapLocation(DirectArgumentsLoc, heap, node->child1()), LazyNode(node));
 999         return;
1000     }
1001
1002     case PutToArguments: {
1003         AbstractHeap heap(DirectArgumentsProperties, node->capturedArgumentsOffset().offset());
1004         write(heap);
1005         def(HeapLocation(DirectArgumentsLoc, heap, node->child1()), LazyNode(node->child2().node()));
1006         return;
1007     }
1008
1009     case GetGlobalVar:
1010     case GetGlobalLexicalVariable:
1011         read(AbstractHeap(Absolute, node->variablePointer()));
1012         def(HeapLocation(GlobalVariableLoc, AbstractHeap(Absolute, node->variablePointer())), LazyNode(node));
1013         return;
1014
1015     case PutGlobalVariable:
1016         write(AbstractHeap(Absolute, node->variablePointer()));
1017         def(HeapLocation(GlobalVariableLoc, AbstractHeap(Absolute, node->variablePointer())), LazyNode(node->child2().node()));
1018         return;
1019
1020     case NewArrayWithSize:
1021     case NewTypedArray:
1022         read(HeapObjectCount);
1023         write(HeapObjectCount);
1024         return;
1025
1026     case NewArray: {
1027         read(HeapObjectCount);
1028         write(HeapObjectCount);
1029
1030         unsigned numElements = node->numChildren();
1031
1032         def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node),
1033             LazyNode(graph.freeze(jsNumber(numElements))));
1034
1035         if (!numElements)
1036             return;
1037
1038         AbstractHeap heap;
1039         switch (node->indexingType()) {
1040         case ALL_DOUBLE_INDEXING_TYPES:
1041             heap = IndexedDoubleProperties;
1042             break;
1043
1044         case ALL_INT32_INDEXING_TYPES:
1045             heap = IndexedInt32Properties;
1046             break;
1047
1048         case ALL_CONTIGUOUS_INDEXING_TYPES:
1049             heap = IndexedContiguousProperties;
1050             break;
1051
1052         default:
1053             return;
1054         }
1055
1056         if (numElements < graph.m_uint32ValuesInUse.size()) {
1057             for (unsigned operandIdx = 0; operandIdx < numElements; ++operandIdx) {
1058                 Edge use = graph.m_varArgChildren[node->firstChild() + operandIdx];
1059                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(operandIdx)))),
1060                     LazyNode(use.node()));
1061             }
1062         } else {
1063             for (uint32_t operandIdx : graph.m_uint32ValuesInUse) {
1064                 if (operandIdx >= numElements)
1065                     continue;
1066                 Edge use = graph.m_varArgChildren[node->firstChild() + operandIdx];
1067                 // operandIdx comes from graph.m_uint32ValuesInUse and thus is guaranteed to be already frozen
1068                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(operandIdx)))),
1069                     LazyNode(use.node()));
1070             }
1071         }
1072         return;
1073     }
1074
1075     case NewArrayBuffer: {
1076         read(HeapObjectCount);
1077         write(HeapObjectCount);
1078
1079         unsigned numElements = node->numConstants();
1080         def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node),
1081             LazyNode(graph.freeze(jsNumber(numElements))));
1082
1083         AbstractHeap heap;
1084         NodeType op = JSConstant;
1085         switch (node->indexingType()) {
1086         case ALL_DOUBLE_INDEXING_TYPES:
1087             heap = IndexedDoubleProperties;
1088             op = DoubleConstant;
1089             break;
1090
1091         case ALL_INT32_INDEXING_TYPES:
1092             heap = IndexedInt32Properties;
1093             break;
1094
1095         case ALL_CONTIGUOUS_INDEXING_TYPES:
1096             heap = IndexedContiguousProperties;
1097             break;
1098
1099         default:
1100             return;
1101         }
1102
1103         JSValue* data = graph.m_codeBlock->constantBuffer(node->startConstant());
1104         if (numElements < graph.m_uint32ValuesInUse.size()) {
1105             for (unsigned index = 0; index < numElements; ++index) {
1106                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(index)))),
1107                     LazyNode(graph.freeze(data[index]), op));
1108             }
1109         } else {
1110             Vector<uint32_t> possibleIndices;
1111             for (uint32_t index : graph.m_uint32ValuesInUse) {
1112                 if (index >= numElements)
1113                     continue;
1114                 possibleIndices.append(index);
1115             }
1116             for (uint32_t index : possibleIndices) {
1117                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(index)))),
1118                     LazyNode(graph.freeze(data[index]), op));
1119             }
1120         }
1121         return;
1122     }
1123
1124     case CreateRest: {
1125         if (!graph.isWatchingHavingABadTimeWatchpoint(node)) {
1126             // This means we're already having a bad time.
1127             read(World);
1128             write(Heap);
1129             return;
1130         }
1131         read(Stack);
1132         read(HeapObjectCount);
1133         write(HeapObjectCount);
1134         return;
1135     }
1136
1137     case NewObject:
1138     case NewRegexp:
1139     case NewStringObject:
1140     case PhantomNewObject:
1141     case MaterializeNewObject:
1142     case PhantomNewFunction:
1143     case PhantomNewGeneratorFunction:
1144     case PhantomCreateActivation:
1145     case MaterializeCreateActivation:
1146         read(HeapObjectCount);
1147         write(HeapObjectCount);
1148         return;
1149
1150     case NewFunction:
1151     case NewGeneratorFunction:
1152         if (node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid())
1153             write(Watchpoint_fire);
1154         read(HeapObjectCount);
1155         write(HeapObjectCount);
1156         return;
1157
1158     case RegExpExec:
1159     case RegExpTest:
1160         if (node->child2().useKind() == RegExpObjectUse
1161             && node->child3().useKind() == StringUse) {
1162             read(RegExpState);
1163             read(RegExpObject_lastIndex);
1164             write(RegExpState);
1165             write(RegExpObject_lastIndex);
1166             return;
1167         }
1168         read(World);
1169         write(Heap);
1170         return;
1171
1172     case StringReplace:
1173     case StringReplaceRegExp:
1174         if (node->child1().useKind() == StringUse
1175             && node->child2().useKind() == RegExpObjectUse
1176             && node->child3().useKind() == StringUse) {
1177             read(RegExpState);
1178             read(RegExpObject_lastIndex);
1179             write(RegExpState);
1180             write(RegExpObject_lastIndex);
1181             return;
1182         }
1183         read(World);
1184         write(Heap);
1185         return;
1186
1187     case StringCharAt:
1188         if (node->arrayMode().isOutOfBounds()) {
1189             read(World);
1190             write(Heap);
1191             return;
1192         }
1193         def(PureValue(node));
1194         return;
1195
1196     case CompareEq:
1197     case CompareLess:
1198     case CompareLessEq:
1199     case CompareGreater:
1200     case CompareGreaterEq:
1201         if (node->isBinaryUseKind(StringUse)) {
1202             read(HeapObjectCount);
1203             write(HeapObjectCount);
1204             return;
1205         }
1206         if (!node->isBinaryUseKind(UntypedUse)) {
1207             def(PureValue(node));
1208             return;
1209         }
1210         read(World);
1211         write(Heap);
1212         return;
1213
1214     case ToNumber: {
1215         read(World);
1216         write(Heap);
1217         return;
1218     }
1219
1220     case ToString:
1221     case CallStringConstructor:
1222         switch (node->child1().useKind()) {
1223         case StringObjectUse:
1224         case StringOrStringObjectUse:
1225             // These don't def a pure value, unfortunately. I'll avoid load-eliminating these for
1226             // now.
1227             return;
1228
1229         case CellUse:
1230         case UntypedUse:
1231             read(World);
1232             write(Heap);
1233             return;
1234
1235         default:
1236             RELEASE_ASSERT_NOT_REACHED();
1237             return;
1238         }
1239
1240     case ThrowReferenceError:
1241         write(SideState);
1242         return;
1243
1244     case CountExecution:
1245     case CheckWatchdogTimer:
1246         read(InternalState);
1247         write(InternalState);
1248         return;
1249
1250     case LogShadowChickenPrologue:
1251     case LogShadowChickenTail:
1252         write(SideState);
1253         return;
1254
1255     case LastNodeType:
1256         RELEASE_ASSERT_NOT_REACHED();
1257         return;
1258     }
1259
1260     DFG_CRASH(graph, node, toCString("Unrecognized node type: ", Graph::opName(node->op())).data());
1261 }
1262
1263 class NoOpClobberize {
1264 public:
1265     NoOpClobberize() { }
1266     template<typename... T>
1267     void operator()(T...) const { }
1268 };
1269
1270 class CheckClobberize {
1271 public:
1272     CheckClobberize()
1273         : m_result(false)
1274     {
1275     }
1276
1277     template<typename... T>
1278     void operator()(T...) const { m_result = true; }
1279
1280     bool result() const { return m_result; }
1281
1282 private:
1283     mutable bool m_result;
1284 };
1285
1286 bool doesWrites(Graph&, Node*);
1287
1288 class AbstractHeapOverlaps {
1289 public:
1290     AbstractHeapOverlaps(AbstractHeap heap)
1291         : m_heap(heap)
1292         , m_result(false)
1293     {
1294     }
1295
1296     void operator()(AbstractHeap otherHeap) const
1297     {
1298         if (m_result)
1299             return;
1300         m_result = m_heap.overlaps(otherHeap);
1301     }
1302
1303     bool result() const { return m_result; }
1304
1305 private:
1306     AbstractHeap m_heap;
1307     mutable bool m_result;
1308 };
1309
1310 bool accessesOverlap(Graph&, Node*, AbstractHeap);
1311 bool writesOverlap(Graph&, Node*, AbstractHeap);
1312
1313 bool clobbersHeap(Graph&, Node*);
1314
1315 // We would have used bind() for these, but because of the overlaoding that we are doing,
1316 // it's quite a bit of clearer to just write this out the traditional way.
1317
1318 template<typename T>
1319 class ReadMethodClobberize {
1320 public:
1321     ReadMethodClobberize(T& value)
1322         : m_value(value)
1323     {
1324     }
1325
1326     void operator()(AbstractHeap heap) const
1327     {
1328         m_value.read(heap);
1329     }
1330 private:
1331     T& m_value;
1332 };
1333
1334 template<typename T>
1335 class WriteMethodClobberize {
1336 public:
1337     WriteMethodClobberize(T& value)
1338         : m_value(value)
1339     {
1340     }
1341
1342     void operator()(AbstractHeap heap) const
1343     {
1344         m_value.write(heap);
1345     }
1346 private:
1347     T& m_value;
1348 };
1349
1350 template<typename T>
1351 class DefMethodClobberize {
1352 public:
1353     DefMethodClobberize(T& value)
1354         : m_value(value)
1355     {
1356     }
1357
1358     void operator()(PureValue value) const
1359     {
1360         m_value.def(value);
1361     }
1362
1363     void operator()(HeapLocation location, LazyNode node) const
1364     {
1365         m_value.def(location, node);
1366     }
1367
1368 private:
1369     T& m_value;
1370 };
1371
1372 template<typename Adaptor>
1373 void clobberize(Graph& graph, Node* node, Adaptor& adaptor)
1374 {
1375     ReadMethodClobberize<Adaptor> read(adaptor);
1376     WriteMethodClobberize<Adaptor> write(adaptor);
1377     DefMethodClobberize<Adaptor> def(adaptor);
1378     clobberize(graph, node, read, write, def);
1379 }
1380
1381 } } // namespace JSC::DFG
1382
1383 #endif // ENABLE(DFG_JIT)
1384
1385 #endif // DFGClobberize_h
1386