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