The DFG should be able to tier-up and OSR enter into the FTL
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGClobberize.h
1 /*
2  * Copyright (C) 2013 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 #include <wtf/Platform.h>
30
31 #if ENABLE(DFG_JIT)
32
33 #include "DFGAbstractHeap.h"
34 #include "DFGEdgeUsesStructure.h"
35 #include "DFGGraph.h"
36
37 namespace JSC { namespace DFG {
38
39 template<typename ReadFunctor, typename WriteFunctor>
40 void clobberize(Graph& graph, Node* node, ReadFunctor& read, WriteFunctor& write)
41 {
42     // Some notes:
43     //
44     // - We cannot hoist, or sink, anything that has effects. This means that the
45     //   easiest way of indicating that something cannot be hoisted is to claim
46     //   that it side-effects some miscellaneous thing.
47     //
48     // - We cannot hoist forward-exiting nodes without some additional effort. I
49     //   believe that what it comes down to is that forward-exiting generally have
50     //   their NodeExitsForward cleared upon hoist, except for forward-exiting
51     //   nodes that take bogus state as their input. Those are substantially
52     //   harder. We disable it for now. In the future we could enable it by having
53     //   versions of those nodes that backward-exit instead, but I'm not convinced
54     //   of the soundness.
55     //
56     // - Some nodes lie, and claim that they do not read the JSCell_structure.
57     //   These are nodes that use the structure in a way that does not depend on
58     //   things that change under structure transitions.
59     //
60     // - It's implicitly understood that OSR exits read the world. This is why we
61     //   generally don't move or eliminate stores. Every node can exit, so the
62     //   read set does not reflect things that would be read if we exited.
63     //   Instead, the read set reflects what the node will have to read if it
64     //   *doesn't* exit.
65     //
66     // - Broadly, we don't say that we're reading something if that something is
67     //   immutable.
68     //
69     // - We try to make this work even prior to type inference, just so that we
70     //   can use it for IR dumps. No promises on whether the answers are sound
71     //   prior to type inference - though they probably could be if we did some
72     //   small hacking.
73     
74     if (edgesUseStructure(graph, node))
75         read(JSCell_structure);
76     
77     switch (node->op()) {
78     case JSConstant:
79     case WeakJSConstant:
80     case Identity:
81     case Phantom:
82     case BitAnd:
83     case BitOr:
84     case BitXor:
85     case BitLShift:
86     case BitRShift:
87     case BitURShift:
88     case ValueToInt32:
89     case ArithAdd:
90     case ArithSub:
91     case ArithNegate:
92     case ArithMul:
93     case ArithIMul:
94     case ArithDiv:
95     case ArithMod:
96     case ArithAbs:
97     case ArithMin:
98     case ArithMax:
99     case ArithSqrt:
100     case GetScope:
101     case SkipScope:
102     case CheckFunction:
103     case StringCharCodeAt:
104     case StringFromCharCode:
105     case CompareEqConstant:
106     case CompareStrictEqConstant:
107     case CompareStrictEq:
108     case IsUndefined:
109     case IsBoolean:
110     case IsNumber:
111     case IsString:
112     case LogicalNot:
113     case Int32ToDouble:
114     case ExtractOSREntryLocal:
115         return;
116         
117     case MovHintAndCheck:
118     case MovHint:
119     case ZombieHint:
120     case Upsilon:
121     case Phi:
122     case Flush:
123     case PhantomLocal:
124     case SetArgument:
125     case InlineStart:
126     case Breakpoint:
127     case CreateActivation:
128     case CreateArguments:
129     case PhantomArguments:
130     case Jump:
131     case Branch:
132     case Switch:
133     case Throw:
134     case ForceOSRExit:
135     case Return:
136     case Unreachable:
137     case CheckTierUpInLoop:
138     case CheckTierUpAtReturn:
139     case CheckTierUpAndOSREnter:
140     case LoopHint:
141         write(SideState);
142         return;
143
144     // These are forward-exiting nodes that assume that the subsequent instruction
145     // is a MovHint, and they try to roll forward over this MovHint in their
146     // execution. This makes hoisting them impossible without additional magic. We
147     // may add such magic eventually, but just not yet.
148     case UInt32ToNumber:
149     case DoubleAsInt32:
150         write(SideState);
151         return;
152         
153     case CreateThis:
154     case ToThis:
155     case VarInjectionWatchpoint:
156     case AllocationProfileWatchpoint:
157     case IsObject:
158     case IsFunction:
159     case TypeOf:
160         read(MiscFields);
161         return;
162         
163     case GetById:
164     case GetByIdFlush:
165     case PutById:
166     case PutByIdDirect:
167     case ArrayPush:
168     case ArrayPop:
169     case Call:
170     case Construct:
171     case ToPrimitive:
172     case In:
173     case GetMyArgumentsLengthSafe:
174     case GetMyArgumentByValSafe:
175         read(World);
176         write(World);
177         return;
178         
179     case ValueAdd:
180         switch (node->binaryUseKind()) {
181         case Int32Use:
182         case NumberUse:
183             return;
184         case UntypedUse:
185             read(World);
186             write(World);
187             return;
188         default:
189             RELEASE_ASSERT_NOT_REACHED();
190             return;
191         }
192         
193     case GetCallee:
194         read(AbstractHeap(Variables, JSStack::Callee));
195         return;
196         
197     case SetCallee:
198         write(AbstractHeap(Variables, JSStack::Callee));
199         return;
200         
201     case GetLocal:
202     case GetArgument:
203         read(AbstractHeap(Variables, node->local()));
204         return;
205         
206     case SetLocal:
207         write(AbstractHeap(Variables, node->local()));
208         return;
209         
210     case GetLocalUnlinked:
211         read(AbstractHeap(Variables, node->unlinkedLocal()));
212         return;
213         
214     case GetByVal: {
215         ArrayMode mode = node->arrayMode();
216         switch (mode.type()) {
217         case Array::SelectUsingPredictions:
218         case Array::Unprofiled:
219         case Array::Undecided:
220             // Assume the worst since we don't have profiling yet.
221             read(World);
222             write(World);
223             return;
224             
225         case Array::ForceExit:
226             write(SideState);
227             return;
228             
229         case Array::Generic:
230             read(World);
231             write(World);
232             return;
233             
234         case Array::String:
235             if (mode.isOutOfBounds()) {
236                 read(World);
237                 write(World);
238                 return;
239             }
240             // This appears to read nothing because it's only reading immutable data.
241             return;
242             
243         case Array::Arguments:
244             read(Arguments_registers);
245             read(Variables);
246             return;
247             
248         case Array::Int32:
249             if (mode.isInBounds()) {
250                 read(Butterfly_publicLength);
251                 read(Butterfly_vectorLength);
252                 read(IndexedInt32Properties);
253                 return;
254             }
255             read(World);
256             write(World);
257             return;
258             
259         case Array::Double:
260             if (mode.isInBounds()) {
261                 read(Butterfly_publicLength);
262                 read(Butterfly_vectorLength);
263                 read(IndexedDoubleProperties);
264                 return;
265             }
266             read(World);
267             write(World);
268             return;
269             
270         case Array::Contiguous:
271             if (mode.isInBounds()) {
272                 read(Butterfly_publicLength);
273                 read(Butterfly_vectorLength);
274                 read(IndexedContiguousProperties);
275                 return;
276             }
277             read(World);
278             write(World);
279             return;
280             
281         case Array::ArrayStorage:
282         case Array::SlowPutArrayStorage:
283             // Give up on life for now.
284             read(World);
285             write(World);
286             return;
287             
288         case Array::Int8Array:
289         case Array::Int16Array:
290         case Array::Int32Array:
291         case Array::Uint8Array:
292         case Array::Uint8ClampedArray:
293         case Array::Uint16Array:
294         case Array::Uint32Array:
295         case Array::Float32Array:
296         case Array::Float64Array:
297             read(TypedArrayProperties);
298             read(JSArrayBufferView_vector);
299             read(JSArrayBufferView_length);
300             return;
301         }
302         RELEASE_ASSERT_NOT_REACHED();
303         return;
304     }
305         
306     case PutByVal:
307     case PutByValAlias: {
308         ArrayMode mode = node->arrayMode();
309         switch (mode.modeForPut().type()) {
310         case Array::SelectUsingPredictions:
311         case Array::Unprofiled:
312         case Array::Undecided:
313         case Array::String:
314             // Assume the worst since we don't have profiling yet.
315             read(World);
316             write(World);
317             return;
318             
319         case Array::ForceExit:
320             write(SideState);
321             return;
322             
323         case Array::Generic:
324             read(World);
325             write(World);
326             return;
327             
328         case Array::Arguments:
329             read(Arguments_registers);
330             read(Arguments_numArguments);
331             read(Arguments_slowArguments);
332             write(Variables);
333             return;
334             
335         case Array::Int32:
336             if (node->arrayMode().isOutOfBounds()) {
337                 read(World);
338                 write(World);
339                 return;
340             }
341             read(Butterfly_publicLength);
342             read(Butterfly_vectorLength);
343             read(IndexedInt32Properties);
344             write(IndexedInt32Properties);
345             return;
346             
347         case Array::Double:
348             if (node->arrayMode().isOutOfBounds()) {
349                 read(World);
350                 write(World);
351                 return;
352             }
353             read(Butterfly_publicLength);
354             read(Butterfly_vectorLength);
355             read(IndexedDoubleProperties);
356             write(IndexedDoubleProperties);
357             return;
358             
359         case Array::Contiguous:
360             if (node->arrayMode().isOutOfBounds()) {
361                 read(World);
362                 write(World);
363                 return;
364             }
365             read(Butterfly_publicLength);
366             read(Butterfly_vectorLength);
367             read(IndexedContiguousProperties);
368             write(IndexedContiguousProperties);
369             return;
370             
371         case Array::ArrayStorage:
372         case Array::SlowPutArrayStorage:
373             // Give up on life for now.
374             read(World);
375             write(World);
376             return;
377
378         case Array::Int8Array:
379         case Array::Int16Array:
380         case Array::Int32Array:
381         case Array::Uint8Array:
382         case Array::Uint8ClampedArray:
383         case Array::Uint16Array:
384         case Array::Uint32Array:
385         case Array::Float32Array:
386         case Array::Float64Array:
387             read(JSArrayBufferView_vector);
388             read(JSArrayBufferView_length);
389             write(TypedArrayProperties);
390             return;
391         }
392         RELEASE_ASSERT_NOT_REACHED();
393         return;
394     }
395         
396     case CheckStructure:
397     case StructureTransitionWatchpoint:
398     case CheckArray:
399     case CheckHasInstance:
400     case InstanceOf:
401         read(JSCell_structure);
402         return;
403         
404     case CheckExecutable:
405         read(JSFunction_executable);
406         return;
407         
408     case PutStructure:
409     case PhantomPutStructure:
410         write(JSCell_structure);
411         return;
412         
413     case AllocatePropertyStorage:
414         write(JSObject_butterfly);
415         return;
416         
417     case ReallocatePropertyStorage:
418         read(JSObject_butterfly);
419         write(JSObject_butterfly);
420         return;
421         
422     case GetButterfly:
423         read(JSObject_butterfly);
424         return;
425         
426     case Arrayify:
427     case ArrayifyToStructure:
428         read(JSCell_structure);
429         read(JSObject_butterfly);
430         write(JSCell_structure);
431         write(JSObject_butterfly);
432         return;
433         
434     case GetIndexedPropertyStorage:
435         if (node->arrayMode().type() == Array::String)
436             return;
437         read(JSArrayBufferView_vector);
438         return;
439         
440     case GetTypedArrayByteOffset:
441         read(JSArrayBufferView_vector);
442         read(JSArrayBufferView_mode);
443         read(Butterfly_arrayBuffer);
444         read(ArrayBuffer_data);
445         return;
446         
447     case GetByOffset:
448         read(AbstractHeap(NamedProperties, graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber));
449         return;
450         
451     case PutByOffset:
452         write(AbstractHeap(NamedProperties, graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber));
453         return;
454         
455     case GetArrayLength: {
456         ArrayMode mode = node->arrayMode();
457         switch (mode.type()) {
458         case Array::Int32:
459         case Array::Double:
460         case Array::Contiguous:
461         case Array::ArrayStorage:
462         case Array::SlowPutArrayStorage:
463             read(Butterfly_publicLength);
464             return;
465             
466         case Array::String:
467             return;
468             
469         case Array::Arguments:
470             read(Arguments_overrideLength);
471             read(Arguments_numArguments);
472             return;
473             
474         default:
475             read(JSArrayBufferView_length);
476             return;
477         }
478     }
479         
480     case GetMyScope:
481         read(AbstractHeap(Variables, JSStack::ScopeChain));
482         return;
483         
484     case SetMyScope:
485         write(AbstractHeap(Variables, JSStack::ScopeChain));
486         return;
487         
488     case SkipTopScope:
489         read(AbstractHeap(Variables, graph.m_codeBlock->activationRegister()));
490         return;
491         
492     case GetClosureRegisters:
493         read(JSVariableObject_registers);
494         return;
495         
496     case GetClosureVar:
497         read(AbstractHeap(Variables, node->varNumber()));
498         return;
499         
500     case PutClosureVar:
501         write(AbstractHeap(Variables, node->varNumber()));
502         return;
503         
504     case GetGlobalVar:
505     case GlobalVarWatchpoint:
506         read(AbstractHeap(Absolute, node->registerPointer()));
507         return;
508         
509     case PutGlobalVar:
510         write(AbstractHeap(Absolute, node->registerPointer()));
511         return;
512
513     case NewObject:
514     case NewArray:
515     case NewArrayWithSize:
516     case NewArrayBuffer:
517     case NewRegexp:
518     case NewStringObject:
519     case MakeRope:
520     case NewFunctionNoCheck:
521     case NewFunction:
522     case NewFunctionExpression:
523         read(GCState);
524         write(GCState);
525         return;
526         
527     case NewTypedArray:
528         switch (node->child1().useKind()) {
529         case Int32Use:
530             read(GCState);
531             write(GCState);
532             return;
533         case UntypedUse:
534             read(World);
535             write(World);
536             return;
537         default:
538             RELEASE_ASSERT_NOT_REACHED();
539             return;
540         }
541         
542     case RegExpExec:
543     case RegExpTest:
544         read(RegExpState);
545         write(RegExpState);
546         return;
547
548     case StringCharAt:
549         if (node->arrayMode().isOutOfBounds()) {
550             read(World);
551             write(World);
552             return;
553         }
554         return;
555         
556     case CompareLess:
557     case CompareLessEq:
558     case CompareGreater:
559     case CompareGreaterEq:
560         if (graph.isPredictedNumerical(node))
561             return;
562         read(World);
563         write(World);
564         return;
565         
566     case CompareEq:
567         if (graph.isPredictedNumerical(node)
568             || node->isBinaryUseKind(StringUse)
569             || node->isBinaryUseKind(StringIdentUse))
570             return;
571         
572         if ((node->child1().useKind() == ObjectUse || node->child1().useKind() == ObjectOrOtherUse)
573             && (node->child2().useKind() == ObjectUse || node->child2().useKind() == ObjectOrOtherUse))
574             return;
575         
576         read(World);
577         write(World);
578         return;
579         
580     case ToString:
581         switch (node->child1().useKind()) {
582         case StringObjectUse:
583         case StringOrStringObjectUse:
584             return;
585             
586         case CellUse:
587         case UntypedUse:
588             read(World);
589             write(World);
590             return;
591             
592         default:
593             RELEASE_ASSERT_NOT_REACHED();
594             return;
595         }
596
597     case TearOffActivation:
598         write(JSVariableObject_registers);
599         return;
600         
601     case TearOffArguments:
602         write(Arguments_registers);
603         return;
604         
605     case GetMyArgumentsLength:
606         read(AbstractHeap(Variables, graph.argumentsRegisterFor(node->codeOrigin)));
607         read(AbstractHeap(Variables, JSStack::ArgumentCount));
608         return;
609         
610     case GetMyArgumentByVal:
611         read(Variables);
612         return;
613         
614     case CheckArgumentsNotCreated:
615         read(AbstractHeap(Variables, graph.argumentsRegisterFor(node->codeOrigin)));
616         return;
617
618     case ThrowReferenceError:
619         write(SideState);
620         read(GCState);
621         write(GCState);
622         return;
623         
624     case CountExecution:
625     case CheckWatchdogTimer:
626         read(InternalState);
627         write(InternalState);
628         return;
629         
630     case LastNodeType:
631         RELEASE_ASSERT_NOT_REACHED();
632         return;
633     }
634     
635     RELEASE_ASSERT_NOT_REACHED();
636 }
637
638 class NoOpClobberize {
639 public:
640     NoOpClobberize() { }
641     void operator()(AbstractHeap) { }
642 };
643
644 class CheckClobberize {
645 public:
646     CheckClobberize()
647         : m_result(false)
648     {
649     }
650     
651     void operator()(AbstractHeap) { m_result = true; }
652     
653     bool result() const { return m_result; }
654     
655 private:
656     bool m_result;
657 };
658
659 bool doesWrites(Graph&, Node*);
660
661 } } // namespace JSC::DFG
662
663 #endif // ENABLE(DFG_JIT)
664
665 #endif // DFGClobberize_h
666