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