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