Source/JavaScriptCore/dfg/DFGClobberize.h

   1 /*
   2  * Copyright (C) 2013-2015 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     switch (node->op()) {
 111     case JSConstant:
 112     case DoubleConstant:
 113     case Int52Constant:
 114         def(PureValue(node, node->constant()));
 115         return;
 116
 117     case Identity:
 118     case Phantom:
 119     case Check:
 120     case ExtractOSREntryLocal:
 121     case CheckStructureImmediate:
 122         return;
 123
 124     case BitAnd:
 125     case BitOr:
 126     case BitXor:
 127     case BitLShift:
 128     case BitRShift:
 129     case BitURShift:
 130     case ArithIMul:
 131     case ArithAbs:
 132     case ArithClz32:
 133     case ArithMin:
 134     case ArithMax:
 135     case ArithPow:
 136     case ArithSqrt:
 137     case ArithFRound:
 138     case ArithSin:
 139     case ArithCos:
 140     case ArithLog:
 141     case GetScope:
 142     case LoadArrowFunctionThis:
 143     case SkipScope:
 144     case StringCharCodeAt:
 145     case StringFromCharCode:
 146     case CompareStrictEq:
 147     case IsUndefined:
 148     case IsBoolean:
 149     case IsNumber:
 150     case IsString:
 151     case IsObject:
 152     case LogicalNot:
 153     case CheckInBounds:
 154     case DoubleRep:
 155     case ValueRep:
 156     case Int52Rep:
 157     case BooleanToNumber:
 158     case FiatInt52:
 159     case MakeRope:
 160     case StrCat:
 161     case ValueToInt32:
 162     case GetExecutable:
 163     case BottomValue:
 164     case TypeOf:
 165         def(PureValue(node));
 166         return;
 167
 168     case HasGenericProperty:
 169     case HasStructureProperty:
 170     case GetEnumerableLength:
 171     case GetPropertyEnumerator: {
 172         read(Heap);
 173         write(SideState);
 174         return;
 175     }
 176
 177     case GetDirectPname: {
 178         // This reads and writes heap because it can end up calling a generic getByVal
 179         // if the Structure changed, which could in turn end up calling a getter.
 180         read(World);
 181         write(Heap);
 182         return;
 183     }
 184
 185     case ToIndexString:
 186     case GetEnumeratorStructurePname:
 187     case GetEnumeratorGenericPname: {
 188         def(PureValue(node));
 189         return;
 190     }
 191
 192     case HasIndexedProperty: {
 193         read(JSObject_butterfly);
 194         ArrayMode mode = node->arrayMode();
 195         switch (mode.type()) {
 196         case Array::Int32: {
 197             if (mode.isInBounds()) {
 198                 read(Butterfly_publicLength);
 199                 read(IndexedInt32Properties);
 200                 def(HeapLocation(HasIndexedPropertyLoc, IndexedInt32Properties, node->child1(), node->child2()), LazyNode(node));
 201                 return;
 202             }
 203             read(Heap);
 204             return;
 205         }
 206
 207         case Array::Double: {
 208             if (mode.isInBounds()) {
 209                 read(Butterfly_publicLength);
 210                 read(IndexedDoubleProperties);
 211                 def(HeapLocation(HasIndexedPropertyLoc, IndexedDoubleProperties, node->child1(), node->child2()), LazyNode(node));
 212                 return;
 213             }
 214             read(Heap);
 215             return;
 216         }
 217
 218         case Array::Contiguous: {
 219             if (mode.isInBounds()) {
 220                 read(Butterfly_publicLength);
 221                 read(IndexedContiguousProperties);
 222                 def(HeapLocation(HasIndexedPropertyLoc, IndexedContiguousProperties, node->child1(), node->child2()), LazyNode(node));
 223                 return;
 224             }
 225             read(Heap);
 226             return;
 227         }
 228
 229         case Array::ArrayStorage: {
 230             if (mode.isInBounds()) {
 231                 read(Butterfly_vectorLength);
 232                 read(IndexedArrayStorageProperties);
 233                 return;
 234             }
 235             read(Heap);
 236             return;
 237         }
 238
 239         default: {
 240             read(World);
 241             write(Heap);
 242             return;
 243         }
 244         }
 245         RELEASE_ASSERT_NOT_REACHED();
 246         return;
 247     }
 248
 249     case ArithAdd:
 250     case ArithNegate:
 251     case ArithMul:
 252     case ArithDiv:
 253     case ArithMod:
 254     case DoubleAsInt32:
 255     case UInt32ToNumber:
 256         def(PureValue(node, node->arithMode()));
 257         return;
 258
 259     case ArithSub:
 260         switch (node->binaryUseKind()) {
 261         case Int32Use:
 262         case Int52RepUse:
 263         case DoubleRepUse:
 264             def(PureValue(node, node->arithMode()));
 265             return;
 266         case UntypedUse:
 267             read(World);
 268             write(Heap);
 269             return;
 270         default:
 271             DFG_CRASH(graph, node, "Bad use kind");
 272         }
 273
 274     case ArithRound:
 275         def(PureValue(node, static_cast<uintptr_t>(node->arithRoundingMode())));
 276         return;
 277
 278     case CheckCell:
 279         def(PureValue(CheckCell, AdjacencyList(AdjacencyList::Fixed, node->child1()), node->cellOperand()));
 280         return;
 281
 282     case CheckNotEmpty:
 283         def(PureValue(CheckNotEmpty, AdjacencyList(AdjacencyList::Fixed, node->child1())));
 284         return;
 285
 286     case CheckIdent:
 287         def(PureValue(CheckIdent, AdjacencyList(AdjacencyList::Fixed, node->child1()), node->uidOperand()));
 288         return;
 289
 290     case ConstantStoragePointer:
 291         def(PureValue(node, node->storagePointer()));
 292         return;
 293
 294     case MovHint:
 295     case ZombieHint:
 296     case ExitOK:
 297     case KillStack:
 298     case Upsilon:
 299     case Phi:
 300     case PhantomLocal:
 301     case SetArgument:
 302     case Jump:
 303     case Branch:
 304     case Switch:
 305     case Throw:
 306     case ForceOSRExit:
 307     case CheckBadCell:
 308     case Return:
 309     case Unreachable:
 310     case CheckTierUpInLoop:
 311     case CheckTierUpAtReturn:
 312     case CheckTierUpAndOSREnter:
 313     case CheckTierUpWithNestedTriggerAndOSREnter:
 314     case LoopHint:
 315     case Breakpoint:
 316     case ProfileWillCall:
 317     case ProfileDidCall:
 318     case ProfileType:
 319     case ProfileControlFlow:
 320     case StoreBarrier:
 321     case PutHint:
 322         write(SideState);
 323         return;
 324
 325     case InvalidationPoint:
 326         write(SideState);
 327         def(HeapLocation(InvalidationPointLoc, Watchpoint_fire), LazyNode(node));
 328         return;
 329
 330     case Flush:
 331         read(AbstractHeap(Stack, node->local()));
 332         write(SideState);
 333         return;
 334
 335     case NotifyWrite:
 336         write(Watchpoint_fire);
 337         write(SideState);
 338         return;
 339
 340     case CreateActivation: {
 341         SymbolTable* table = node->castOperand<SymbolTable*>();
 342         if (table->singletonScope()->isStillValid())
 343             write(Watchpoint_fire);
 344         read(HeapObjectCount);
 345         write(HeapObjectCount);
 346         return;
 347     }
 348
 349     case CreateDirectArguments:
 350     case CreateScopedArguments:
 351     case CreateClonedArguments:
 352         read(Stack);
 353         read(HeapObjectCount);
 354         write(HeapObjectCount);
 355         return;
 356
 357     case PhantomDirectArguments:
 358     case PhantomClonedArguments:
 359         // DFG backend requires that the locals that this reads are flushed. FTL backend can handle those
 360         // locals being promoted.
 361         if (!isFTL(graph.m_plan.mode))
 362             read(Stack);
 363
 364         // Even though it's phantom, it still has the property that one can't be replaced with another.
 365         read(HeapObjectCount);
 366         write(HeapObjectCount);
 367         return;
 368
 369     case ToThis:
 370     case CreateThis:
 371         read(MiscFields);
 372         read(HeapObjectCount);
 373         write(HeapObjectCount);
 374         return;
 375
 376     case VarInjectionWatchpoint:
 377         read(MiscFields);
 378         def(HeapLocation(VarInjectionWatchpointLoc, MiscFields), LazyNode(node));
 379         return;
 380
 381     case IsObjectOrNull:
 382         read(MiscFields);
 383         def(HeapLocation(IsObjectOrNullLoc, MiscFields, node->child1()), LazyNode(node));
 384         return;
 385
 386     case IsFunction:
 387         read(MiscFields);
 388         def(HeapLocation(IsFunctionLoc, MiscFields, node->child1()), LazyNode(node));
 389         return;
 390
 391     case GetById:
 392     case GetByIdFlush:
 393     case PutById:
 394     case PutByIdFlush:
 395     case PutByIdDirect:
 396     case PutGetterById:
 397     case PutSetterById:
 398     case PutGetterSetterById:
 399     case PutGetterByVal:
 400     case PutSetterByVal:
 401     case ArrayPush:
 402     case ArrayPop:
 403     case Call:
 404     case TailCallInlinedCaller:
 405     case Construct:
 406     case CallVarargs:
 407     case CallForwardVarargs:
 408     case TailCallVarargsInlinedCaller:
 409     case TailCallForwardVarargsInlinedCaller:
 410     case ConstructVarargs:
 411     case ConstructForwardVarargs:
 412     case ToPrimitive:
 413     case In:
 414     case ValueAdd:
 415         read(World);
 416         write(Heap);
 417         return;
 418
 419     case TailCall:
 420     case TailCallVarargs:
 421     case TailCallForwardVarargs:
 422         read(World);
 423         write(SideState);
 424         return;
 425
 426     case GetGetter:
 427         read(GetterSetter_getter);
 428         def(HeapLocation(GetterLoc, GetterSetter_getter, node->child1()), LazyNode(node));
 429         return;
 430
 431     case GetSetter:
 432         read(GetterSetter_setter);
 433         def(HeapLocation(SetterLoc, GetterSetter_setter, node->child1()), LazyNode(node));
 434         return;
 435
 436     case GetCallee:
 437         read(AbstractHeap(Stack, JSStack::Callee));
 438         def(HeapLocation(StackLoc, AbstractHeap(Stack, JSStack::Callee)), LazyNode(node));
 439         return;
 440
 441     case GetArgumentCount:
 442         read(AbstractHeap(Stack, JSStack::ArgumentCount));
 443         def(HeapLocation(StackPayloadLoc, AbstractHeap(Stack, JSStack::ArgumentCount)), LazyNode(node));
 444         return;
 445
 446     case GetRestLength:
 447         read(Stack);
 448         return;
 449
 450     case GetLocal:
 451         read(AbstractHeap(Stack, node->local()));
 452         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->local())), LazyNode(node));
 453         return;
 454
 455     case SetLocal:
 456         write(AbstractHeap(Stack, node->local()));
 457         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->local())), LazyNode(node->child1().node()));
 458         return;
 459
 460     case GetStack: {
 461         AbstractHeap heap(Stack, node->stackAccessData()->local);
 462         read(heap);
 463         def(HeapLocation(StackLoc, heap), LazyNode(node));
 464         return;
 465     }
 466
 467     case PutStack: {
 468         AbstractHeap heap(Stack, node->stackAccessData()->local);
 469         write(heap);
 470         def(HeapLocation(StackLoc, heap), LazyNode(node->child1().node()));
 471         return;
 472     }
 473
 474     case LoadVarargs: {
 475         read(World);
 476         write(Heap);
 477         LoadVarargsData* data = node->loadVarargsData();
 478         write(AbstractHeap(Stack, data->count.offset()));
 479         for (unsigned i = data->limit; i--;)
 480             write(AbstractHeap(Stack, data->start.offset() + static_cast<int>(i)));
 481         return;
 482     }
 483
 484     case ForwardVarargs: {
 485         // We could be way more precise here.
 486         read(Stack);
 487
 488         LoadVarargsData* data = node->loadVarargsData();
 489         write(AbstractHeap(Stack, data->count.offset()));
 490         for (unsigned i = data->limit; i--;)
 491             write(AbstractHeap(Stack, data->start.offset() + static_cast<int>(i)));
 492         return;
 493     }
 494
 495     case GetLocalUnlinked:
 496         read(AbstractHeap(Stack, node->unlinkedLocal()));
 497         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->unlinkedLocal())), LazyNode(node));
 498         return;
 499
 500     case GetByVal: {
 501         ArrayMode mode = node->arrayMode();
 502         switch (mode.type()) {
 503         case Array::SelectUsingPredictions:
 504         case Array::Unprofiled:
 505         case Array::SelectUsingArguments:
 506             // Assume the worst since we don't have profiling yet.
 507             read(World);
 508             write(Heap);
 509             return;
 510
 511         case Array::ForceExit:
 512             write(SideState);
 513             return;
 514
 515         case Array::Generic:
 516             read(World);
 517             write(Heap);
 518             return;
 519
 520         case Array::String:
 521             if (mode.isOutOfBounds()) {
 522                 read(World);
 523                 write(Heap);
 524                 return;
 525             }
 526             // This appears to read nothing because it's only reading immutable data.
 527             def(PureValue(node, mode.asWord()));
 528             return;
 529
 530         case Array::DirectArguments:
 531             read(DirectArgumentsProperties);
 532             def(HeapLocation(IndexedPropertyLoc, DirectArgumentsProperties, node->child1(), node->child2()), LazyNode(node));
 533             return;
 534
 535         case Array::ScopedArguments:
 536             read(ScopeProperties);
 537             def(HeapLocation(IndexedPropertyLoc, ScopeProperties, node->child1(), node->child2()), LazyNode(node));
 538             return;
 539
 540         case Array::Int32:
 541             if (mode.isInBounds()) {
 542                 read(Butterfly_publicLength);
 543                 read(IndexedInt32Properties);
 544                 def(HeapLocation(IndexedPropertyLoc, IndexedInt32Properties, node->child1(), node->child2()), LazyNode(node));
 545                 return;
 546             }
 547             read(World);
 548             write(Heap);
 549             return;
 550
 551         case Array::Double:
 552             if (mode.isInBounds()) {
 553                 read(Butterfly_publicLength);
 554                 read(IndexedDoubleProperties);
 555                 def(HeapLocation(IndexedPropertyLoc, IndexedDoubleProperties, node->child1(), node->child2()), LazyNode(node));
 556                 return;
 557             }
 558             read(World);
 559             write(Heap);
 560             return;
 561
 562         case Array::Contiguous:
 563             if (mode.isInBounds()) {
 564                 read(Butterfly_publicLength);
 565                 read(IndexedContiguousProperties);
 566                 def(HeapLocation(IndexedPropertyLoc, IndexedContiguousProperties, node->child1(), node->child2()), LazyNode(node));
 567                 return;
 568             }
 569             read(World);
 570             write(Heap);
 571             return;
 572
 573         case Array::Undecided:
 574             def(PureValue(node));
 575             return;
 576
 577         case Array::ArrayStorage:
 578         case Array::SlowPutArrayStorage:
 579             if (mode.isInBounds()) {
 580                 read(Butterfly_vectorLength);
 581                 read(IndexedArrayStorageProperties);
 582                 return;
 583             }
 584             read(World);
 585             write(Heap);
 586             return;
 587
 588         case Array::Int8Array:
 589         case Array::Int16Array:
 590         case Array::Int32Array:
 591         case Array::Uint8Array:
 592         case Array::Uint8ClampedArray:
 593         case Array::Uint16Array:
 594         case Array::Uint32Array:
 595         case Array::Float32Array:
 596         case Array::Float64Array:
 597             read(TypedArrayProperties);
 598             read(MiscFields);
 599             def(HeapLocation(IndexedPropertyLoc, TypedArrayProperties, node->child1(), node->child2()), LazyNode(node));
 600             return;
 601         // We should not get an AnyTypedArray in a GetByVal as AnyTypedArray is only created from intrinsics, which
 602         // are only added from Inline Caching a GetById.
 603         case Array::AnyTypedArray:
 604             DFG_CRASH(graph, node, "impossible array mode for get");
 605             return;
 606         }
 607         RELEASE_ASSERT_NOT_REACHED();
 608         return;
 609     }
 610
 611     case GetMyArgumentByVal: {
 612         read(Stack);
 613         // FIXME: It would be trivial to have a def here.
 614         // https://bugs.webkit.org/show_bug.cgi?id=143077
 615         return;
 616     }
 617
 618     case PutByValDirect:
 619     case PutByVal:
 620     case PutByValAlias: {
 621         ArrayMode mode = node->arrayMode();
 622         Node* base = graph.varArgChild(node, 0).node();
 623         Node* index = graph.varArgChild(node, 1).node();
 624         Node* value = graph.varArgChild(node, 2).node();
 625         switch (mode.modeForPut().type()) {
 626         case Array::SelectUsingPredictions:
 627         case Array::SelectUsingArguments:
 628         case Array::Unprofiled:
 629         case Array::Undecided:
 630             // Assume the worst since we don't have profiling yet.
 631             read(World);
 632             write(Heap);
 633             return;
 634
 635         case Array::ForceExit:
 636             write(SideState);
 637             return;
 638
 639         case Array::Generic:
 640             read(World);
 641             write(Heap);
 642             return;
 643
 644         case Array::Int32:
 645             if (node->arrayMode().isOutOfBounds()) {
 646                 read(World);
 647                 write(Heap);
 648                 return;
 649             }
 650             read(Butterfly_publicLength);
 651             read(Butterfly_vectorLength);
 652             read(IndexedInt32Properties);
 653             write(IndexedInt32Properties);
 654             if (node->arrayMode().mayStoreToHole())
 655                 write(Butterfly_publicLength);
 656             def(HeapLocation(IndexedPropertyLoc, IndexedInt32Properties, base, index), LazyNode(value));
 657             return;
 658
 659         case Array::Double:
 660             if (node->arrayMode().isOutOfBounds()) {
 661                 read(World);
 662                 write(Heap);
 663                 return;
 664             }
 665             read(Butterfly_publicLength);
 666             read(Butterfly_vectorLength);
 667             read(IndexedDoubleProperties);
 668             write(IndexedDoubleProperties);
 669             if (node->arrayMode().mayStoreToHole())
 670                 write(Butterfly_publicLength);
 671             def(HeapLocation(IndexedPropertyLoc, IndexedDoubleProperties, base, index), LazyNode(value));
 672             return;
 673
 674         case Array::Contiguous:
 675             if (node->arrayMode().isOutOfBounds()) {
 676                 read(World);
 677                 write(Heap);
 678                 return;
 679             }
 680             read(Butterfly_publicLength);
 681             read(Butterfly_vectorLength);
 682             read(IndexedContiguousProperties);
 683             write(IndexedContiguousProperties);
 684             if (node->arrayMode().mayStoreToHole())
 685                 write(Butterfly_publicLength);
 686             def(HeapLocation(IndexedPropertyLoc, IndexedContiguousProperties, base, index), LazyNode(value));
 687             return;
 688
 689         case Array::ArrayStorage:
 690         case Array::SlowPutArrayStorage:
 691             // Give up on life for now.
 692             read(World);
 693             write(Heap);
 694             return;
 695
 696         case Array::Int8Array:
 697         case Array::Int16Array:
 698         case Array::Int32Array:
 699         case Array::Uint8Array:
 700         case Array::Uint8ClampedArray:
 701         case Array::Uint16Array:
 702         case Array::Uint32Array:
 703         case Array::Float32Array:
 704         case Array::Float64Array:
 705             read(MiscFields);
 706             write(TypedArrayProperties);
 707             // FIXME: We can't def() anything here because these operations truncate their inputs.
 708             // https://bugs.webkit.org/show_bug.cgi?id=134737
 709             return;
 710         case Array::AnyTypedArray:
 711         case Array::String:
 712         case Array::DirectArguments:
 713         case Array::ScopedArguments:
 714             DFG_CRASH(graph, node, "impossible array mode for put");
 715             return;
 716         }
 717         RELEASE_ASSERT_NOT_REACHED();
 718         return;
 719     }
 720
 721     case CheckStructure:
 722         read(JSCell_structureID);
 723         return;
 724
 725     case CheckArray:
 726         read(JSCell_indexingType);
 727         read(JSCell_typeInfoType);
 728         read(JSCell_structureID);
 729         return;
 730
 731     case CheckHasInstance:
 732         read(JSCell_typeInfoFlags);
 733         def(HeapLocation(CheckHasInstanceLoc, JSCell_typeInfoFlags, node->child1()), LazyNode(node));
 734         return;
 735
 736     case InstanceOf:
 737         read(JSCell_structureID);
 738         def(HeapLocation(InstanceOfLoc, JSCell_structureID, node->child1(), node->child2()), LazyNode(node));
 739         return;
 740
 741     case PutStructure:
 742         write(JSCell_structureID);
 743         write(JSCell_typeInfoType);
 744         write(JSCell_typeInfoFlags);
 745         write(JSCell_indexingType);
 746         return;
 747
 748     case AllocatePropertyStorage:
 749         write(JSObject_butterfly);
 750         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
 751         return;
 752
 753     case ReallocatePropertyStorage:
 754         read(JSObject_butterfly);
 755         write(JSObject_butterfly);
 756         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
 757         return;
 758
 759     case GetButterfly:
 760         read(JSObject_butterfly);
 761         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
 762         return;
 763
 764     case GetButterflyReadOnly:
 765         // This rule is separate to prevent CSE of GetButterfly with GetButterflyReadOnly. But in reality,
 766         // this works because we don't introduce GetButterflyReadOnly until the bitter end of compilation.
 767         read(JSObject_butterfly);
 768         def(HeapLocation(ButterflyReadOnlyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
 769         return;
 770
 771     case Arrayify:
 772     case ArrayifyToStructure:
 773         read(JSCell_structureID);
 774         read(JSCell_indexingType);
 775         read(JSObject_butterfly);
 776         write(JSCell_structureID);
 777         write(JSCell_indexingType);
 778         write(JSObject_butterfly);
 779         write(Watchpoint_fire);
 780         return;
 781
 782     case GetIndexedPropertyStorage:
 783         if (node->arrayMode().type() == Array::String) {
 784             def(PureValue(node, node->arrayMode().asWord()));
 785             return;
 786         }
 787         read(MiscFields);
 788         def(HeapLocation(IndexedPropertyStorageLoc, MiscFields, node->child1()), LazyNode(node));
 789         return;
 790
 791     case GetTypedArrayByteOffset:
 792         read(MiscFields);
 793         def(HeapLocation(TypedArrayByteOffsetLoc, MiscFields, node->child1()), LazyNode(node));
 794         return;
 795
 796     case GetByOffset:
 797     case GetGetterSetterByOffset: {
 798         unsigned identifierNumber = node->storageAccessData().identifierNumber;
 799         AbstractHeap heap(NamedProperties, identifierNumber);
 800         read(heap);
 801         def(HeapLocation(NamedPropertyLoc, heap, node->child2()), LazyNode(node));
 802         return;
 803     }
 804
 805     case MultiGetByOffset: {
 806         read(JSCell_structureID);
 807         read(JSObject_butterfly);
 808         AbstractHeap heap(NamedProperties, node->multiGetByOffsetData().identifierNumber);
 809         read(heap);
 810         def(HeapLocation(NamedPropertyLoc, heap, node->child1()), LazyNode(node));
 811         return;
 812     }
 813
 814     case MultiPutByOffset: {
 815         read(JSCell_structureID);
 816         read(JSObject_butterfly);
 817         AbstractHeap heap(NamedProperties, node->multiPutByOffsetData().identifierNumber);
 818         write(heap);
 819         if (node->multiPutByOffsetData().writesStructures())
 820             write(JSCell_structureID);
 821         if (node->multiPutByOffsetData().reallocatesStorage())
 822             write(JSObject_butterfly);
 823         def(HeapLocation(NamedPropertyLoc, heap, node->child1()), LazyNode(node->child2().node()));
 824         return;
 825     }
 826
 827     case PutByOffset: {
 828         unsigned identifierNumber = node->storageAccessData().identifierNumber;
 829         AbstractHeap heap(NamedProperties, identifierNumber);
 830         write(heap);
 831         def(HeapLocation(NamedPropertyLoc, heap, node->child2()), LazyNode(node->child3().node()));
 832         return;
 833     }
 834
 835     case GetArrayLength: {
 836         ArrayMode mode = node->arrayMode();
 837         switch (mode.type()) {
 838         case Array::Int32:
 839         case Array::Double:
 840         case Array::Contiguous:
 841         case Array::ArrayStorage:
 842         case Array::SlowPutArrayStorage:
 843             read(Butterfly_publicLength);
 844             def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node->child1()), LazyNode(node));
 845             return;
 846
 847         case Array::String:
 848             def(PureValue(node, mode.asWord()));
 849             return;
 850
 851         case Array::DirectArguments:
 852         case Array::ScopedArguments:
 853             read(MiscFields);
 854             def(HeapLocation(ArrayLengthLoc, MiscFields, node->child1()), LazyNode(node));
 855             return;
 856
 857         default:
 858             ASSERT(mode.isSomeTypedArrayView());
 859             read(MiscFields);
 860             def(HeapLocation(ArrayLengthLoc, MiscFields, node->child1()), LazyNode(node));
 861             return;
 862         }
 863     }
 864
 865     case GetClosureVar:
 866         read(AbstractHeap(ScopeProperties, node->scopeOffset().offset()));
 867         def(HeapLocation(ClosureVariableLoc, AbstractHeap(ScopeProperties, node->scopeOffset().offset()), node->child1()), LazyNode(node));
 868         return;
 869
 870     case PutClosureVar:
 871         write(AbstractHeap(ScopeProperties, node->scopeOffset().offset()));
 872         def(HeapLocation(ClosureVariableLoc, AbstractHeap(ScopeProperties, node->scopeOffset().offset()), node->child1()), LazyNode(node->child2().node()));
 873         return;
 874
 875     case GetFromArguments: {
 876         AbstractHeap heap(DirectArgumentsProperties, node->capturedArgumentsOffset().offset());
 877         read(heap);
 878         def(HeapLocation(DirectArgumentsLoc, heap, node->child1()), LazyNode(node));
 879         return;
 880     }
 881
 882     case PutToArguments: {
 883         AbstractHeap heap(DirectArgumentsProperties, node->capturedArgumentsOffset().offset());
 884         write(heap);
 885         def(HeapLocation(DirectArgumentsLoc, heap, node->child1()), LazyNode(node->child2().node()));
 886         return;
 887     }
 888
 889     case GetGlobalVar:
 890     case GetGlobalLexicalVariable:
 891         read(AbstractHeap(Absolute, node->variablePointer()));
 892         def(HeapLocation(GlobalVariableLoc, AbstractHeap(Absolute, node->variablePointer())), LazyNode(node));
 893         return;
 894
 895     case PutGlobalVariable:
 896         write(AbstractHeap(Absolute, node->variablePointer()));
 897         def(HeapLocation(GlobalVariableLoc, AbstractHeap(Absolute, node->variablePointer())), LazyNode(node->child2().node()));
 898         return;
 899
 900     case NewArrayWithSize:
 901     case NewTypedArray:
 902         read(HeapObjectCount);
 903         write(HeapObjectCount);
 904         return;
 905
 906     case NewArray: {
 907         read(HeapObjectCount);
 908         write(HeapObjectCount);
 909
 910         unsigned numElements = node->numChildren();
 911
 912         def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node),
 913             LazyNode(graph.freeze(jsNumber(numElements))));
 914
 915         if (!numElements)
 916             return;
 917
 918         AbstractHeap heap;
 919         switch (node->indexingType()) {
 920         case ALL_DOUBLE_INDEXING_TYPES:
 921             heap = IndexedDoubleProperties;
 922             break;
 923
 924         case ALL_INT32_INDEXING_TYPES:
 925             heap = IndexedInt32Properties;
 926             break;
 927
 928         case ALL_CONTIGUOUS_INDEXING_TYPES:
 929             heap = IndexedContiguousProperties;
 930             break;
 931
 932         default:
 933             return;
 934         }
 935
 936         if (numElements < graph.m_uint32ValuesInUse.size()) {
 937             for (unsigned operandIdx = 0; operandIdx < numElements; ++operandIdx) {
 938                 Edge use = graph.m_varArgChildren[node->firstChild() + operandIdx];
 939                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(operandIdx)))),
 940                     LazyNode(use.node()));
 941             }
 942         } else {
 943             for (uint32_t operandIdx : graph.m_uint32ValuesInUse) {
 944                 if (operandIdx >= numElements)
 945                     continue;
 946                 Edge use = graph.m_varArgChildren[node->firstChild() + operandIdx];
 947                 // operandIdx comes from graph.m_uint32ValuesInUse and thus is guaranteed to be already frozen
 948                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(operandIdx)))),
 949                     LazyNode(use.node()));
 950             }
 951         }
 952         return;
 953     }
 954
 955     case NewArrayBuffer: {
 956         read(HeapObjectCount);
 957         write(HeapObjectCount);
 958
 959         unsigned numElements = node->numConstants();
 960         def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node),
 961             LazyNode(graph.freeze(jsNumber(numElements))));
 962
 963         AbstractHeap heap;
 964         NodeType op = JSConstant;
 965         switch (node->indexingType()) {
 966         case ALL_DOUBLE_INDEXING_TYPES:
 967             heap = IndexedDoubleProperties;
 968             op = DoubleConstant;
 969             break;
 970
 971         case ALL_INT32_INDEXING_TYPES:
 972             heap = IndexedInt32Properties;
 973             break;
 974
 975         case ALL_CONTIGUOUS_INDEXING_TYPES:
 976             heap = IndexedContiguousProperties;
 977             break;
 978
 979         default:
 980             return;
 981         }
 982
 983         JSValue* data = graph.m_codeBlock->constantBuffer(node->startConstant());
 984         if (numElements < graph.m_uint32ValuesInUse.size()) {
 985             for (unsigned index = 0; index < numElements; ++index) {
 986                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(index)))),
 987                     LazyNode(graph.freeze(data[index]), op));
 988             }
 989         } else {
 990             Vector<uint32_t> possibleIndices;
 991             for (uint32_t index : graph.m_uint32ValuesInUse) {
 992                 if (index >= numElements)
 993                     continue;
 994                 possibleIndices.append(index);
 995             }
 996             for (uint32_t index : possibleIndices) {
 997                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(index)))),
 998                     LazyNode(graph.freeze(data[index]), op));
 999             }
1000         }
1001         return;
1002     }
1003
1004     case CopyRest: {
1005         read(Stack);
1006         write(Heap);
1007         return;
1008     }
1009
1010     case NewObject:
1011     case NewRegexp:
1012     case NewStringObject:
1013     case PhantomNewObject:
1014     case MaterializeNewObject:
1015     case PhantomNewFunction:
1016     case PhantomCreateActivation:
1017     case MaterializeCreateActivation:
1018         read(HeapObjectCount);
1019         write(HeapObjectCount);
1020         return;
1021
1022     case NewArrowFunction:
1023     case NewFunction:
1024         if (node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid())
1025             write(Watchpoint_fire);
1026         read(HeapObjectCount);
1027         write(HeapObjectCount);
1028         return;
1029
1030     case RegExpExec:
1031     case RegExpTest:
1032         read(RegExpState);
1033         write(RegExpState);
1034         return;
1035
1036     case StringCharAt:
1037         if (node->arrayMode().isOutOfBounds()) {
1038             read(World);
1039             write(Heap);
1040             return;
1041         }
1042         def(PureValue(node));
1043         return;
1044
1045     case CompareEq:
1046     case CompareLess:
1047     case CompareLessEq:
1048     case CompareGreater:
1049     case CompareGreaterEq:
1050         if (!node->isBinaryUseKind(UntypedUse)) {
1051             def(PureValue(node));
1052             return;
1053         }
1054         read(World);
1055         write(Heap);
1056         return;
1057
1058     case ToString:
1059     case CallStringConstructor:
1060         switch (node->child1().useKind()) {
1061         case StringObjectUse:
1062         case StringOrStringObjectUse:
1063             // These don't def a pure value, unfortunately. I'll avoid load-eliminating these for
1064             // now.
1065             return;
1066
1067         case CellUse:
1068         case UntypedUse:
1069             read(World);
1070             write(Heap);
1071             return;
1072
1073         default:
1074             RELEASE_ASSERT_NOT_REACHED();
1075             return;
1076         }
1077
1078     case ThrowReferenceError:
1079         write(SideState);
1080         return;
1081
1082     case CountExecution:
1083     case CheckWatchdogTimer:
1084         read(InternalState);
1085         write(InternalState);
1086         return;
1087
1088     case LastNodeType:
1089         RELEASE_ASSERT_NOT_REACHED();
1090         return;
1091     }
1092
1093     DFG_CRASH(graph, node, toCString("Unrecognized node type: ", Graph::opName(node->op())).data());
1094 }
1095
1096 class NoOpClobberize {
1097 public:
1098     NoOpClobberize() { }
1099     template<typename... T>
1100     void operator()(T...) const { }
1101 };
1102
1103 class CheckClobberize {
1104 public:
1105     CheckClobberize()
1106         : m_result(false)
1107     {
1108     }
1109
1110     template<typename... T>
1111     void operator()(T...) const { m_result = true; }
1112
1113     bool result() const { return m_result; }
1114
1115 private:
1116     mutable bool m_result;
1117 };
1118
1119 bool doesWrites(Graph&, Node*);
1120
1121 class AbstractHeapOverlaps {
1122 public:
1123     AbstractHeapOverlaps(AbstractHeap heap)
1124         : m_heap(heap)
1125         , m_result(false)
1126     {
1127     }
1128
1129     void operator()(AbstractHeap otherHeap) const
1130     {
1131         if (m_result)
1132             return;
1133         m_result = m_heap.overlaps(otherHeap);
1134     }
1135
1136     bool result() const { return m_result; }
1137
1138 private:
1139     AbstractHeap m_heap;
1140     mutable bool m_result;
1141 };
1142
1143 bool accessesOverlap(Graph&, Node*, AbstractHeap);
1144 bool writesOverlap(Graph&, Node*, AbstractHeap);
1145
1146 bool clobbersHeap(Graph&, Node*);
1147
1148 // We would have used bind() for these, but because of the overlaoding that we are doing,
1149 // it's quite a bit of clearer to just write this out the traditional way.
1150
1151 template<typename T>
1152 class ReadMethodClobberize {
1153 public:
1154     ReadMethodClobberize(T& value)
1155         : m_value(value)
1156     {
1157     }
1158
1159     void operator()(AbstractHeap heap) const
1160     {
1161         m_value.read(heap);
1162     }
1163 private:
1164     T& m_value;
1165 };
1166
1167 template<typename T>
1168 class WriteMethodClobberize {
1169 public:
1170     WriteMethodClobberize(T& value)
1171         : m_value(value)
1172     {
1173     }
1174
1175     void operator()(AbstractHeap heap) const
1176     {
1177         m_value.write(heap);
1178     }
1179 private:
1180     T& m_value;
1181 };
1182
1183 template<typename T>
1184 class DefMethodClobberize {
1185 public:
1186     DefMethodClobberize(T& value)
1187         : m_value(value)
1188     {
1189     }
1190
1191     void operator()(PureValue value) const
1192     {
1193         m_value.def(value);
1194     }
1195
1196     void operator()(HeapLocation location, LazyNode node) const
1197     {
1198         m_value.def(location, node);
1199     }
1200
1201 private:
1202     T& m_value;
1203 };
1204
1205 template<typename Adaptor>
1206 void clobberize(Graph& graph, Node* node, Adaptor& adaptor)
1207 {
1208     ReadMethodClobberize<Adaptor> read(adaptor);
1209     WriteMethodClobberize<Adaptor> write(adaptor);
1210     DefMethodClobberize<Adaptor> def(adaptor);
1211     clobberize(graph, node, read, write, def);
1212 }
1213
1214 } } // namespace JSC::DFG
1215
1216 #endif // ENABLE(DFG_JIT)
1217
1218 #endif // DFGClobberize_h
1219