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