implement op_get_rest_length so that we can allocate the rest array with the right...
[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 PutGetterById:
383     case PutSetterById:
384     case PutGetterSetterById:
385     case PutGetterByVal:
386     case PutSetterByVal:
387     case ArrayPush:
388     case ArrayPop:
389     case Call:
390     case TailCallInlinedCaller:
391     case Construct:
392     case CallVarargs:
393     case CallForwardVarargs:
394     case TailCallVarargsInlinedCaller:
395     case TailCallForwardVarargsInlinedCaller:
396     case ConstructVarargs:
397     case ConstructForwardVarargs:
398     case ToPrimitive:
399     case In:
400     case ValueAdd:
401         read(World);
402         write(Heap);
403         return;
404
405     case TailCall:
406     case TailCallVarargs:
407     case TailCallForwardVarargs:
408         read(World);
409         write(SideState);
410         return;
411         
412     case GetGetter:
413         read(GetterSetter_getter);
414         def(HeapLocation(GetterLoc, GetterSetter_getter, node->child1()), LazyNode(node));
415         return;
416         
417     case GetSetter:
418         read(GetterSetter_setter);
419         def(HeapLocation(SetterLoc, GetterSetter_setter, node->child1()), LazyNode(node));
420         return;
421         
422     case GetCallee:
423         read(AbstractHeap(Stack, JSStack::Callee));
424         def(HeapLocation(StackLoc, AbstractHeap(Stack, JSStack::Callee)), LazyNode(node));
425         return;
426         
427     case GetArgumentCount:
428         read(AbstractHeap(Stack, JSStack::ArgumentCount));
429         def(HeapLocation(StackPayloadLoc, AbstractHeap(Stack, JSStack::ArgumentCount)), LazyNode(node));
430         return;
431
432     case GetRestLength:
433         read(Stack);
434         return;
435         
436     case GetLocal:
437         read(AbstractHeap(Stack, node->local()));
438         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->local())), LazyNode(node));
439         return;
440         
441     case SetLocal:
442         write(AbstractHeap(Stack, node->local()));
443         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->local())), LazyNode(node->child1().node()));
444         return;
445         
446     case GetStack: {
447         AbstractHeap heap(Stack, node->stackAccessData()->local);
448         read(heap);
449         def(HeapLocation(StackLoc, heap), LazyNode(node));
450         return;
451     }
452         
453     case PutStack: {
454         AbstractHeap heap(Stack, node->stackAccessData()->local);
455         write(heap);
456         def(HeapLocation(StackLoc, heap), LazyNode(node->child1().node()));
457         return;
458     }
459         
460     case LoadVarargs: {
461         read(World);
462         write(Heap);
463         LoadVarargsData* data = node->loadVarargsData();
464         write(AbstractHeap(Stack, data->count.offset()));
465         for (unsigned i = data->limit; i--;)
466             write(AbstractHeap(Stack, data->start.offset() + static_cast<int>(i)));
467         return;
468     }
469         
470     case ForwardVarargs: {
471         // We could be way more precise here.
472         read(Stack);
473         
474         LoadVarargsData* data = node->loadVarargsData();
475         write(AbstractHeap(Stack, data->count.offset()));
476         for (unsigned i = data->limit; i--;)
477             write(AbstractHeap(Stack, data->start.offset() + static_cast<int>(i)));
478         return;
479     }
480         
481     case GetLocalUnlinked:
482         read(AbstractHeap(Stack, node->unlinkedLocal()));
483         def(HeapLocation(StackLoc, AbstractHeap(Stack, node->unlinkedLocal())), LazyNode(node));
484         return;
485         
486     case GetByVal: {
487         ArrayMode mode = node->arrayMode();
488         switch (mode.type()) {
489         case Array::SelectUsingPredictions:
490         case Array::Unprofiled:
491         case Array::SelectUsingArguments:
492             // Assume the worst since we don't have profiling yet.
493             read(World);
494             write(Heap);
495             return;
496             
497         case Array::ForceExit:
498             write(SideState);
499             return;
500             
501         case Array::Generic:
502             read(World);
503             write(Heap);
504             return;
505             
506         case Array::String:
507             if (mode.isOutOfBounds()) {
508                 read(World);
509                 write(Heap);
510                 return;
511             }
512             // This appears to read nothing because it's only reading immutable data.
513             def(PureValue(node, mode.asWord()));
514             return;
515             
516         case Array::DirectArguments:
517             read(DirectArgumentsProperties);
518             def(HeapLocation(IndexedPropertyLoc, DirectArgumentsProperties, node->child1(), node->child2()), LazyNode(node));
519             return;
520             
521         case Array::ScopedArguments:
522             read(ScopeProperties);
523             def(HeapLocation(IndexedPropertyLoc, ScopeProperties, node->child1(), node->child2()), LazyNode(node));
524             return;
525             
526         case Array::Int32:
527             if (mode.isInBounds()) {
528                 read(Butterfly_publicLength);
529                 read(IndexedInt32Properties);
530                 def(HeapLocation(IndexedPropertyLoc, IndexedInt32Properties, node->child1(), node->child2()), LazyNode(node));
531                 return;
532             }
533             read(World);
534             write(Heap);
535             return;
536             
537         case Array::Double:
538             if (mode.isInBounds()) {
539                 read(Butterfly_publicLength);
540                 read(IndexedDoubleProperties);
541                 def(HeapLocation(IndexedPropertyLoc, IndexedDoubleProperties, node->child1(), node->child2()), LazyNode(node));
542                 return;
543             }
544             read(World);
545             write(Heap);
546             return;
547             
548         case Array::Contiguous:
549             if (mode.isInBounds()) {
550                 read(Butterfly_publicLength);
551                 read(IndexedContiguousProperties);
552                 def(HeapLocation(IndexedPropertyLoc, IndexedContiguousProperties, node->child1(), node->child2()), LazyNode(node));
553                 return;
554             }
555             read(World);
556             write(Heap);
557             return;
558
559         case Array::Undecided:
560             def(PureValue(node));
561             return;
562             
563         case Array::ArrayStorage:
564         case Array::SlowPutArrayStorage:
565             if (mode.isInBounds()) {
566                 read(Butterfly_vectorLength);
567                 read(IndexedArrayStorageProperties);
568                 return;
569             }
570             read(World);
571             write(Heap);
572             return;
573             
574         case Array::Int8Array:
575         case Array::Int16Array:
576         case Array::Int32Array:
577         case Array::Uint8Array:
578         case Array::Uint8ClampedArray:
579         case Array::Uint16Array:
580         case Array::Uint32Array:
581         case Array::Float32Array:
582         case Array::Float64Array:
583             read(TypedArrayProperties);
584             read(MiscFields);
585             def(HeapLocation(IndexedPropertyLoc, TypedArrayProperties, node->child1(), node->child2()), LazyNode(node));
586             return;
587         // We should not get an AnyTypedArray in a GetByVal as AnyTypedArray is only created from intrinsics, which
588         // are only added from Inline Caching a GetById.
589         case Array::AnyTypedArray:
590             DFG_CRASH(graph, node, "impossible array mode for get");
591             return;
592         }
593         RELEASE_ASSERT_NOT_REACHED();
594         return;
595     }
596         
597     case GetMyArgumentByVal: {
598         read(Stack);
599         // FIXME: It would be trivial to have a def here.
600         // https://bugs.webkit.org/show_bug.cgi?id=143077
601         return;
602     }
603
604     case PutByValDirect:
605     case PutByVal:
606     case PutByValAlias: {
607         ArrayMode mode = node->arrayMode();
608         Node* base = graph.varArgChild(node, 0).node();
609         Node* index = graph.varArgChild(node, 1).node();
610         Node* value = graph.varArgChild(node, 2).node();
611         switch (mode.modeForPut().type()) {
612         case Array::SelectUsingPredictions:
613         case Array::SelectUsingArguments:
614         case Array::Unprofiled:
615         case Array::Undecided:
616             // Assume the worst since we don't have profiling yet.
617             read(World);
618             write(Heap);
619             return;
620             
621         case Array::ForceExit:
622             write(SideState);
623             return;
624             
625         case Array::Generic:
626             read(World);
627             write(Heap);
628             return;
629             
630         case Array::Int32:
631             if (node->arrayMode().isOutOfBounds()) {
632                 read(World);
633                 write(Heap);
634                 return;
635             }
636             read(Butterfly_publicLength);
637             read(Butterfly_vectorLength);
638             read(IndexedInt32Properties);
639             write(IndexedInt32Properties);
640             if (node->arrayMode().mayStoreToHole())
641                 write(Butterfly_publicLength);
642             def(HeapLocation(IndexedPropertyLoc, IndexedInt32Properties, base, index), LazyNode(value));
643             return;
644             
645         case Array::Double:
646             if (node->arrayMode().isOutOfBounds()) {
647                 read(World);
648                 write(Heap);
649                 return;
650             }
651             read(Butterfly_publicLength);
652             read(Butterfly_vectorLength);
653             read(IndexedDoubleProperties);
654             write(IndexedDoubleProperties);
655             if (node->arrayMode().mayStoreToHole())
656                 write(Butterfly_publicLength);
657             def(HeapLocation(IndexedPropertyLoc, IndexedDoubleProperties, base, index), LazyNode(value));
658             return;
659             
660         case Array::Contiguous:
661             if (node->arrayMode().isOutOfBounds()) {
662                 read(World);
663                 write(Heap);
664                 return;
665             }
666             read(Butterfly_publicLength);
667             read(Butterfly_vectorLength);
668             read(IndexedContiguousProperties);
669             write(IndexedContiguousProperties);
670             if (node->arrayMode().mayStoreToHole())
671                 write(Butterfly_publicLength);
672             def(HeapLocation(IndexedPropertyLoc, IndexedContiguousProperties, base, index), LazyNode(value));
673             return;
674             
675         case Array::ArrayStorage:
676         case Array::SlowPutArrayStorage:
677             // Give up on life for now.
678             read(World);
679             write(Heap);
680             return;
681
682         case Array::Int8Array:
683         case Array::Int16Array:
684         case Array::Int32Array:
685         case Array::Uint8Array:
686         case Array::Uint8ClampedArray:
687         case Array::Uint16Array:
688         case Array::Uint32Array:
689         case Array::Float32Array:
690         case Array::Float64Array:
691             read(MiscFields);
692             write(TypedArrayProperties);
693             // FIXME: We can't def() anything here because these operations truncate their inputs.
694             // https://bugs.webkit.org/show_bug.cgi?id=134737
695             return;
696         case Array::AnyTypedArray:
697         case Array::String:
698         case Array::DirectArguments:
699         case Array::ScopedArguments:
700             DFG_CRASH(graph, node, "impossible array mode for put");
701             return;
702         }
703         RELEASE_ASSERT_NOT_REACHED();
704         return;
705     }
706         
707     case CheckStructure:
708         read(JSCell_structureID);
709         return;
710
711     case CheckArray:
712         read(JSCell_indexingType);
713         read(JSCell_typeInfoType);
714         read(JSCell_structureID);
715         return;
716
717     case CheckHasInstance:
718         read(JSCell_typeInfoFlags);
719         def(HeapLocation(CheckHasInstanceLoc, JSCell_typeInfoFlags, node->child1()), LazyNode(node));
720         return;
721
722     case InstanceOf:
723         read(JSCell_structureID);
724         def(HeapLocation(InstanceOfLoc, JSCell_structureID, node->child1(), node->child2()), LazyNode(node));
725         return;
726
727     case PutStructure:
728         write(JSCell_structureID);
729         write(JSCell_typeInfoType);
730         write(JSCell_typeInfoFlags);
731         write(JSCell_indexingType);
732         return;
733         
734     case AllocatePropertyStorage:
735         write(JSObject_butterfly);
736         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
737         return;
738         
739     case ReallocatePropertyStorage:
740         read(JSObject_butterfly);
741         write(JSObject_butterfly);
742         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
743         return;
744         
745     case GetButterfly:
746         read(JSObject_butterfly);
747         def(HeapLocation(ButterflyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
748         return;
749
750     case GetButterflyReadOnly:
751         // This rule is separate to prevent CSE of GetButterfly with GetButterflyReadOnly. But in reality,
752         // this works because we don't introduce GetButterflyReadOnly until the bitter end of compilation.
753         read(JSObject_butterfly);
754         def(HeapLocation(ButterflyReadOnlyLoc, JSObject_butterfly, node->child1()), LazyNode(node));
755         return;
756         
757     case Arrayify:
758     case ArrayifyToStructure:
759         read(JSCell_structureID);
760         read(JSCell_indexingType);
761         read(JSObject_butterfly);
762         write(JSCell_structureID);
763         write(JSCell_indexingType);
764         write(JSObject_butterfly);
765         write(Watchpoint_fire);
766         return;
767         
768     case GetIndexedPropertyStorage:
769         if (node->arrayMode().type() == Array::String) {
770             def(PureValue(node, node->arrayMode().asWord()));
771             return;
772         }
773         read(MiscFields);
774         def(HeapLocation(IndexedPropertyStorageLoc, MiscFields, node->child1()), LazyNode(node));
775         return;
776         
777     case GetTypedArrayByteOffset:
778         read(MiscFields);
779         def(HeapLocation(TypedArrayByteOffsetLoc, MiscFields, node->child1()), LazyNode(node));
780         return;
781         
782     case GetByOffset:
783     case GetGetterSetterByOffset: {
784         unsigned identifierNumber = node->storageAccessData().identifierNumber;
785         AbstractHeap heap(NamedProperties, identifierNumber);
786         read(heap);
787         def(HeapLocation(NamedPropertyLoc, heap, node->child2()), LazyNode(node));
788         return;
789     }
790         
791     case MultiGetByOffset: {
792         read(JSCell_structureID);
793         read(JSObject_butterfly);
794         AbstractHeap heap(NamedProperties, node->multiGetByOffsetData().identifierNumber);
795         read(heap);
796         def(HeapLocation(NamedPropertyLoc, heap, node->child1()), LazyNode(node));
797         return;
798     }
799         
800     case MultiPutByOffset: {
801         read(JSCell_structureID);
802         read(JSObject_butterfly);
803         AbstractHeap heap(NamedProperties, node->multiPutByOffsetData().identifierNumber);
804         write(heap);
805         if (node->multiPutByOffsetData().writesStructures())
806             write(JSCell_structureID);
807         if (node->multiPutByOffsetData().reallocatesStorage())
808             write(JSObject_butterfly);
809         def(HeapLocation(NamedPropertyLoc, heap, node->child1()), LazyNode(node->child2().node()));
810         return;
811     }
812         
813     case PutByOffset: {
814         unsigned identifierNumber = node->storageAccessData().identifierNumber;
815         AbstractHeap heap(NamedProperties, identifierNumber);
816         write(heap);
817         def(HeapLocation(NamedPropertyLoc, heap, node->child2()), LazyNode(node->child3().node()));
818         return;
819     }
820         
821     case GetArrayLength: {
822         ArrayMode mode = node->arrayMode();
823         switch (mode.type()) {
824         case Array::Int32:
825         case Array::Double:
826         case Array::Contiguous:
827         case Array::ArrayStorage:
828         case Array::SlowPutArrayStorage:
829             read(Butterfly_publicLength);
830             def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node->child1()), LazyNode(node));
831             return;
832             
833         case Array::String:
834             def(PureValue(node, mode.asWord()));
835             return;
836
837         case Array::DirectArguments:
838         case Array::ScopedArguments:
839             read(MiscFields);
840             def(HeapLocation(ArrayLengthLoc, MiscFields, node->child1()), LazyNode(node));
841             return;
842
843         default:
844             ASSERT(mode.isSomeTypedArrayView());
845             read(MiscFields);
846             def(HeapLocation(ArrayLengthLoc, MiscFields, node->child1()), LazyNode(node));
847             return;
848         }
849     }
850         
851     case GetClosureVar:
852         read(AbstractHeap(ScopeProperties, node->scopeOffset().offset()));
853         def(HeapLocation(ClosureVariableLoc, AbstractHeap(ScopeProperties, node->scopeOffset().offset()), node->child1()), LazyNode(node));
854         return;
855         
856     case PutClosureVar:
857         write(AbstractHeap(ScopeProperties, node->scopeOffset().offset()));
858         def(HeapLocation(ClosureVariableLoc, AbstractHeap(ScopeProperties, node->scopeOffset().offset()), node->child1()), LazyNode(node->child2().node()));
859         return;
860         
861     case GetFromArguments: {
862         AbstractHeap heap(DirectArgumentsProperties, node->capturedArgumentsOffset().offset());
863         read(heap);
864         def(HeapLocation(DirectArgumentsLoc, heap, node->child1()), LazyNode(node));
865         return;
866     }
867         
868     case PutToArguments: {
869         AbstractHeap heap(DirectArgumentsProperties, node->capturedArgumentsOffset().offset());
870         write(heap);
871         def(HeapLocation(DirectArgumentsLoc, heap, node->child1()), LazyNode(node->child2().node()));
872         return;
873     }
874         
875     case GetGlobalVar:
876     case GetGlobalLexicalVariable:
877         read(AbstractHeap(Absolute, node->variablePointer()));
878         def(HeapLocation(GlobalVariableLoc, AbstractHeap(Absolute, node->variablePointer())), LazyNode(node));
879         return;
880         
881     case PutGlobalVariable:
882         write(AbstractHeap(Absolute, node->variablePointer()));
883         def(HeapLocation(GlobalVariableLoc, AbstractHeap(Absolute, node->variablePointer())), LazyNode(node->child2().node()));
884         return;
885
886     case NewArrayWithSize:
887     case NewTypedArray:
888         read(HeapObjectCount);
889         write(HeapObjectCount);
890         return;
891
892     case NewArray: {
893         read(HeapObjectCount);
894         write(HeapObjectCount);
895
896         unsigned numElements = node->numChildren();
897
898         def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node),
899             LazyNode(graph.freeze(jsNumber(numElements))));
900
901         if (!numElements)
902             return;
903
904         AbstractHeap heap;
905         switch (node->indexingType()) {
906         case ALL_DOUBLE_INDEXING_TYPES:
907             heap = IndexedDoubleProperties;
908             break;
909
910         case ALL_INT32_INDEXING_TYPES:
911             heap = IndexedInt32Properties;
912             break;
913
914         case ALL_CONTIGUOUS_INDEXING_TYPES:
915             heap = IndexedContiguousProperties;
916             break;
917
918         default:
919             return;
920         }
921
922         if (numElements < graph.m_uint32ValuesInUse.size()) {
923             for (unsigned operandIdx = 0; operandIdx < numElements; ++operandIdx) {
924                 Edge use = graph.m_varArgChildren[node->firstChild() + operandIdx];
925                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(operandIdx)))),
926                     LazyNode(use.node()));
927             }
928         } else {
929             for (uint32_t operandIdx : graph.m_uint32ValuesInUse) {
930                 if (operandIdx >= numElements)
931                     continue;
932                 Edge use = graph.m_varArgChildren[node->firstChild() + operandIdx];
933                 // operandIdx comes from graph.m_uint32ValuesInUse and thus is guaranteed to be already frozen
934                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(operandIdx)))),
935                     LazyNode(use.node()));
936             }
937         }
938         return;
939     }
940
941     case NewArrayBuffer: {
942         read(HeapObjectCount);
943         write(HeapObjectCount);
944
945         unsigned numElements = node->numConstants();
946         def(HeapLocation(ArrayLengthLoc, Butterfly_publicLength, node),
947             LazyNode(graph.freeze(jsNumber(numElements))));
948
949         AbstractHeap heap;
950         NodeType op = JSConstant;
951         switch (node->indexingType()) {
952         case ALL_DOUBLE_INDEXING_TYPES:
953             heap = IndexedDoubleProperties;
954             op = DoubleConstant;
955             break;
956
957         case ALL_INT32_INDEXING_TYPES:
958             heap = IndexedInt32Properties;
959             break;
960
961         case ALL_CONTIGUOUS_INDEXING_TYPES:
962             heap = IndexedContiguousProperties;
963             break;
964
965         default:
966             return;
967         }
968
969         JSValue* data = graph.m_codeBlock->constantBuffer(node->startConstant());
970         if (numElements < graph.m_uint32ValuesInUse.size()) {
971             for (unsigned index = 0; index < numElements; ++index) {
972                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(index)))),
973                     LazyNode(graph.freeze(data[index]), op));
974             }
975         } else {
976             Vector<uint32_t> possibleIndices;
977             for (uint32_t index : graph.m_uint32ValuesInUse) {
978                 if (index >= numElements)
979                     continue;
980                 possibleIndices.append(index);
981             }
982             for (uint32_t index : possibleIndices) {
983                 def(HeapLocation(IndexedPropertyLoc, heap, node, LazyNode(graph.freeze(jsNumber(index)))),
984                     LazyNode(graph.freeze(data[index]), op));
985             }
986         }
987         return;
988     }
989
990     case CopyRest: {
991         read(Stack);
992         write(Heap);
993         return;
994     }
995
996     case NewObject:
997     case NewRegexp:
998     case NewStringObject:
999     case PhantomNewObject:
1000     case MaterializeNewObject:
1001     case PhantomNewFunction:
1002     case PhantomCreateActivation:
1003     case MaterializeCreateActivation:
1004         read(HeapObjectCount);
1005         write(HeapObjectCount);
1006         return;
1007     
1008     case NewArrowFunction:
1009     case NewFunction:
1010         if (node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid())
1011             write(Watchpoint_fire);
1012         read(HeapObjectCount);
1013         write(HeapObjectCount);
1014         return;
1015
1016     case RegExpExec:
1017     case RegExpTest:
1018         read(RegExpState);
1019         write(RegExpState);
1020         return;
1021
1022     case StringCharAt:
1023         if (node->arrayMode().isOutOfBounds()) {
1024             read(World);
1025             write(Heap);
1026             return;
1027         }
1028         def(PureValue(node));
1029         return;
1030         
1031     case CompareEq:
1032     case CompareLess:
1033     case CompareLessEq:
1034     case CompareGreater:
1035     case CompareGreaterEq:
1036         if (!node->isBinaryUseKind(UntypedUse)) {
1037             def(PureValue(node));
1038             return;
1039         }
1040         read(World);
1041         write(Heap);
1042         return;
1043         
1044     case ToString:
1045     case CallStringConstructor:
1046         switch (node->child1().useKind()) {
1047         case StringObjectUse:
1048         case StringOrStringObjectUse:
1049             // These don't def a pure value, unfortunately. I'll avoid load-eliminating these for
1050             // now.
1051             return;
1052             
1053         case CellUse:
1054         case UntypedUse:
1055             read(World);
1056             write(Heap);
1057             return;
1058             
1059         default:
1060             RELEASE_ASSERT_NOT_REACHED();
1061             return;
1062         }
1063         
1064     case ThrowReferenceError:
1065         write(SideState);
1066         return;
1067         
1068     case CountExecution:
1069     case CheckWatchdogTimer:
1070         read(InternalState);
1071         write(InternalState);
1072         return;
1073         
1074     case LastNodeType:
1075         RELEASE_ASSERT_NOT_REACHED();
1076         return;
1077     }
1078     
1079     DFG_CRASH(graph, node, toCString("Unrecognized node type: ", Graph::opName(node->op())).data());
1080 }
1081
1082 class NoOpClobberize {
1083 public:
1084     NoOpClobberize() { }
1085     template<typename... T>
1086     void operator()(T...) const { }
1087 };
1088
1089 class CheckClobberize {
1090 public:
1091     CheckClobberize()
1092         : m_result(false)
1093     {
1094     }
1095     
1096     template<typename... T>
1097     void operator()(T...) const { m_result = true; }
1098     
1099     bool result() const { return m_result; }
1100     
1101 private:
1102     mutable bool m_result;
1103 };
1104
1105 bool doesWrites(Graph&, Node*);
1106
1107 class AbstractHeapOverlaps {
1108 public:
1109     AbstractHeapOverlaps(AbstractHeap heap)
1110         : m_heap(heap)
1111         , m_result(false)
1112     {
1113     }
1114     
1115     void operator()(AbstractHeap otherHeap) const
1116     {
1117         if (m_result)
1118             return;
1119         m_result = m_heap.overlaps(otherHeap);
1120     }
1121     
1122     bool result() const { return m_result; }
1123
1124 private:
1125     AbstractHeap m_heap;
1126     mutable bool m_result;
1127 };
1128
1129 bool accessesOverlap(Graph&, Node*, AbstractHeap);
1130 bool writesOverlap(Graph&, Node*, AbstractHeap);
1131
1132 bool clobbersHeap(Graph&, Node*);
1133
1134 // We would have used bind() for these, but because of the overlaoding that we are doing,
1135 // it's quite a bit of clearer to just write this out the traditional way.
1136
1137 template<typename T>
1138 class ReadMethodClobberize {
1139 public:
1140     ReadMethodClobberize(T& value)
1141         : m_value(value)
1142     {
1143     }
1144     
1145     void operator()(AbstractHeap heap) const
1146     {
1147         m_value.read(heap);
1148     }
1149 private:
1150     T& m_value;
1151 };
1152
1153 template<typename T>
1154 class WriteMethodClobberize {
1155 public:
1156     WriteMethodClobberize(T& value)
1157         : m_value(value)
1158     {
1159     }
1160     
1161     void operator()(AbstractHeap heap) const
1162     {
1163         m_value.write(heap);
1164     }
1165 private:
1166     T& m_value;
1167 };
1168
1169 template<typename T>
1170 class DefMethodClobberize {
1171 public:
1172     DefMethodClobberize(T& value)
1173         : m_value(value)
1174     {
1175     }
1176     
1177     void operator()(PureValue value) const
1178     {
1179         m_value.def(value);
1180     }
1181     
1182     void operator()(HeapLocation location, LazyNode node) const
1183     {
1184         m_value.def(location, node);
1185     }
1186
1187 private:
1188     T& m_value;
1189 };
1190
1191 template<typename Adaptor>
1192 void clobberize(Graph& graph, Node* node, Adaptor& adaptor)
1193 {
1194     ReadMethodClobberize<Adaptor> read(adaptor);
1195     WriteMethodClobberize<Adaptor> write(adaptor);
1196     DefMethodClobberize<Adaptor> def(adaptor);
1197     clobberize(graph, node, read, write, def);
1198 }
1199
1200 } } // namespace JSC::DFG
1201
1202 #endif // ENABLE(DFG_JIT)
1203
1204 #endif // DFGClobberize_h
1205