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