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