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