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