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