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