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
35namespace JSC { namespace DFG {
36
37template<typename ReadFunctor, typename WriteFunctor>
38void clobberizeForAllocation(ReadFunctor& read, WriteFunctor& write)
39{
40    read(GCState);
41    read(BarrierState);
42    write(GCState);
43    write(BarrierState);
44}
45
46template<typename ReadFunctor, typename WriteFunctor>
47void clobberize(Graph& graph, Node* node, ReadFunctor& read, WriteFunctor& write)
48{
49    // Some notes:
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, JSCell_typeInfoFlags, etc.
64    //   These are nodes that use the structure in a way that does not depend on
65    //   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 (edgesUseStructure(graph, node))
82        read(JSCell_structureID);
83
84    switch (node->op()) {
85    case JSConstant:
86    case DoubleConstant:
87    case Int52Constant:
88    case WeakJSConstant:
89    case Identity:
90    case Phantom:
91    case HardPhantom:
92    case BitAnd:
93    case BitOr:
94    case BitXor:
95    case BitLShift:
96    case BitRShift:
97    case BitURShift:
98    case ValueToInt32:
99    case ArithAdd:
100    case ArithSub:
101    case ArithNegate:
102    case ArithMul:
103    case ArithIMul:
104    case ArithDiv:
105    case ArithMod:
106    case ArithAbs:
107    case ArithMin:
108    case ArithMax:
109    case ArithSqrt:
110    case ArithFRound:
111    case ArithSin:
112    case ArithCos:
113    case GetScope:
114    case SkipScope:
115    case CheckFunction:
116    case StringCharCodeAt:
117    case StringFromCharCode:
118    case CompareEqConstant:
119    case CompareStrictEq:
120    case IsUndefined:
121    case IsBoolean:
122    case IsNumber:
123    case IsString:
124    case LogicalNot:
125    case ExtractOSREntryLocal:
126    case CheckInBounds:
127    case ConstantStoragePointer:
128    case UInt32ToNumber:
129    case DoubleAsInt32:
130    case Check:
131    case DoubleRep:
132    case ValueRep:
133    case Int52Rep:
134    case BooleanToNumber:
135    case FiatInt52:
136        return;
137
138    case MovHint:
139    case ZombieHint:
140    case Upsilon:
141    case Phi:
142    case Flush:
143    case PhantomLocal:
144    case SetArgument:
145    case PhantomArguments:
146    case Jump:
147    case Branch:
148    case Switch:
149    case Throw:
150    case ForceOSRExit:
151    case Return:
152    case Unreachable:
153    case CheckTierUpInLoop:
154    case CheckTierUpAtReturn:
155    case CheckTierUpAndOSREnter:
156    case LoopHint:
157    case InvalidationPoint:
158    case Breakpoint:
159    case ProfileWillCall:
160    case ProfileDidCall:
161        write(SideState);
162        return;
163
164    case VariableWatchpoint:
165    case TypedArrayWatchpoint:
166        read(Watchpoint_fire);
167        write(SideState);
168        return;
169
170    case NotifyWrite:
171        write(Watchpoint_fire);
172        write(SideState);
173        return;
174
175    case CreateActivation:
176    case CreateArguments:
177        clobberizeForAllocation(read, write);
178        write(SideState);
179        write(Watchpoint_fire);
180        return;
181
182    case FunctionReentryWatchpoint:
183        read(Watchpoint_fire);
184        return;
185
186    case ToThis:
187    case CreateThis:
188        read(MiscFields);
189        clobberizeForAllocation(read, write);
190        return;
191
192    case VarInjectionWatchpoint:
193    case AllocationProfileWatchpoint:
194    case IsObject:
195    case IsFunction:
196    case TypeOf:
197        read(MiscFields);
198        return;
199
200    case GetById:
201    case GetByIdFlush:
202    case PutById:
203    case PutByIdFlush:
204    case PutByIdDirect:
205    case ArrayPush:
206    case ArrayPop:
207    case Call:
208    case Construct:
209    case ToPrimitive:
210    case In:
211    case GetMyArgumentsLengthSafe:
212    case GetMyArgumentByValSafe:
213    case ValueAdd:
214        read(World);
215        write(World);
216        return;
217
218    case GetCallee:
219        read(AbstractHeap(Variables, JSStack::Callee));
220        return;
221
222    case GetLocal:
223    case GetArgument:
224        read(AbstractHeap(Variables, node->local()));
225        return;
226
227    case SetLocal:
228        write(AbstractHeap(Variables, node->local()));
229        return;
230
231    case GetLocalUnlinked:
232        read(AbstractHeap(Variables, node->unlinkedLocal()));
233        return;
234
235    case GetByVal: {
236        ArrayMode mode = node->arrayMode();
237        switch (mode.type()) {
238        case Array::SelectUsingPredictions:
239        case Array::Unprofiled:
240        case Array::Undecided:
241            // Assume the worst since we don't have profiling yet.
242            read(World);
243            write(World);
244            return;
245
246        case Array::ForceExit:
247            write(SideState);
248            return;
249
250        case Array::Generic:
251            read(World);
252            write(World);
253            return;
254
255        case Array::String:
256            if (mode.isOutOfBounds()) {
257                read(World);
258                write(World);
259                return;
260            }
261            // This appears to read nothing because it's only reading immutable data.
262            return;
263
264        case Array::Arguments:
265            read(Arguments_registers);
266            read(Variables);
267            return;
268
269        case Array::Int32:
270            if (mode.isInBounds()) {
271                read(Butterfly_publicLength);
272                read(Butterfly_vectorLength);
273                read(IndexedInt32Properties);
274                return;
275            }
276            read(World);
277            write(World);
278            return;
279
280        case Array::Double:
281            if (mode.isInBounds()) {
282                read(Butterfly_publicLength);
283                read(Butterfly_vectorLength);
284                read(IndexedDoubleProperties);
285                return;
286            }
287            read(World);
288            write(World);
289            return;
290
291        case Array::Contiguous:
292            if (mode.isInBounds()) {
293                read(Butterfly_publicLength);
294                read(Butterfly_vectorLength);
295                read(IndexedContiguousProperties);
296                return;
297            }
298            read(World);
299            write(World);
300            return;
301
302        case Array::ArrayStorage:
303        case Array::SlowPutArrayStorage:
304            // Give up on life for now.
305            read(World);
306            write(World);
307            return;
308
309        case Array::Int8Array:
310        case Array::Int16Array:
311        case Array::Int32Array:
312        case Array::Uint8Array:
313        case Array::Uint8ClampedArray:
314        case Array::Uint16Array:
315        case Array::Uint32Array:
316        case Array::Float32Array:
317        case Array::Float64Array:
318            read(TypedArrayProperties);
319            read(JSArrayBufferView_vector);
320            read(JSArrayBufferView_length);
321            return;
322        }
323        RELEASE_ASSERT_NOT_REACHED();
324        return;
325    }
326
327    case PutByValDirect:
328    case PutByVal:
329    case PutByValAlias: {
330        ArrayMode mode = node->arrayMode();
331        switch (mode.modeForPut().type()) {
332        case Array::SelectUsingPredictions:
333        case Array::Unprofiled:
334        case Array::Undecided:
335        case Array::String:
336            // Assume the worst since we don't have profiling yet.
337            read(World);
338            write(World);
339            return;
340
341        case Array::ForceExit:
342            write(SideState);
343            return;
344
345        case Array::Generic:
346            read(World);
347            write(World);
348            return;
349
350        case Array::Arguments:
351            read(Arguments_registers);
352            read(Arguments_numArguments);
353            read(Arguments_slowArguments);
354            write(Variables);
355            return;
356
357        case Array::Int32:
358            if (node->arrayMode().isOutOfBounds()) {
359                read(World);
360                write(World);
361                return;
362            }
363            read(Butterfly_publicLength);
364            read(Butterfly_vectorLength);
365            read(IndexedInt32Properties);
366            write(IndexedInt32Properties);
367            return;
368
369        case Array::Double:
370            if (node->arrayMode().isOutOfBounds()) {
371                read(World);
372                write(World);
373                return;
374            }
375            read(Butterfly_publicLength);
376            read(Butterfly_vectorLength);
377            read(IndexedDoubleProperties);
378            write(IndexedDoubleProperties);
379            return;
380
381        case Array::Contiguous:
382            if (node->arrayMode().isOutOfBounds()) {
383                read(World);
384                write(World);
385                return;
386            }
387            read(Butterfly_publicLength);
388            read(Butterfly_vectorLength);
389            read(IndexedContiguousProperties);
390            write(IndexedContiguousProperties);
391            return;
392
393        case Array::ArrayStorage:
394        case Array::SlowPutArrayStorage:
395            // Give up on life for now.
396            read(World);
397            write(World);
398            return;
399
400        case Array::Int8Array:
401        case Array::Int16Array:
402        case Array::Int32Array:
403        case Array::Uint8Array:
404        case Array::Uint8ClampedArray:
405        case Array::Uint16Array:
406        case Array::Uint32Array:
407        case Array::Float32Array:
408        case Array::Float64Array:
409            read(JSArrayBufferView_vector);
410            read(JSArrayBufferView_length);
411            write(TypedArrayProperties);
412            return;
413        }
414        RELEASE_ASSERT_NOT_REACHED();
415        return;
416    }
417
418    case CheckStructure:
419    case StructureTransitionWatchpoint:
420    case InstanceOf:
421        read(JSCell_structureID);
422        return;
423
424    case CheckArray:
425        read(JSCell_indexingType);
426        read(JSCell_typeInfoType);
427        read(JSCell_structureID);
428        return;
429
430    case CheckHasInstance:
431        read(JSCell_typeInfoFlags);
432        return;
433
434    case CheckExecutable:
435        read(JSFunction_executable);
436        return;
437
438    case PutStructure:
439    case PhantomPutStructure:
440        write(JSCell_structureID);
441        write(JSCell_typeInfoType);
442        write(JSCell_typeInfoFlags);
443        write(JSCell_indexingType);
444        return;
445
446    case AllocatePropertyStorage:
447        write(JSObject_butterfly);
448        clobberizeForAllocation(read, write);
449        return;
450
451    case ReallocatePropertyStorage:
452        read(JSObject_butterfly);
453        write(JSObject_butterfly);
454        clobberizeForAllocation(read, write);
455        return;
456
457    case GetButterfly:
458        read(JSObject_butterfly);
459        return;
460
461    case Arrayify:
462    case ArrayifyToStructure:
463        read(JSCell_structureID);
464        read(JSCell_indexingType);
465        read(JSObject_butterfly);
466        write(JSCell_structureID);
467        write(JSCell_indexingType);
468        write(JSObject_butterfly);
469        write(Watchpoint_fire);
470        clobberizeForAllocation(read, write);
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        read(AbstractHeap(NamedProperties, graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber));
488        return;
489
490    case MultiGetByOffset:
491        read(JSCell_structureID);
492        read(JSObject_butterfly);
493        read(AbstractHeap(NamedProperties, node->multiGetByOffsetData().identifierNumber));
494        return;
495
496    case MultiPutByOffset:
497        read(JSCell_structureID);
498        read(JSObject_butterfly);
499        write(AbstractHeap(NamedProperties, node->multiPutByOffsetData().identifierNumber));
500        if (node->multiPutByOffsetData().writesStructures())
501            write(JSCell_structureID);
502        if (node->multiPutByOffsetData().reallocatesStorage()) {
503            write(JSObject_butterfly);
504            clobberizeForAllocation(read, write);
505        }
506        return;
507
508    case PutByOffset:
509        write(AbstractHeap(NamedProperties, graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber));
510        return;
511
512    case GetArrayLength: {
513        ArrayMode mode = node->arrayMode();
514        switch (mode.type()) {
515        case Array::Int32:
516        case Array::Double:
517        case Array::Contiguous:
518        case Array::ArrayStorage:
519        case Array::SlowPutArrayStorage:
520            read(Butterfly_publicLength);
521            return;
522
523        case Array::String:
524            return;
525
526        case Array::Arguments:
527            read(Arguments_overrideLength);
528            read(Arguments_numArguments);
529            return;
530
531        default:
532            read(JSArrayBufferView_length);
533            return;
534        }
535    }
536
537    case GetMyScope:
538        read(AbstractHeap(Variables, JSStack::ScopeChain));
539        return;
540
541    case SkipTopScope:
542        read(AbstractHeap(Variables, graph.activationRegister()));
543        return;
544
545    case GetClosureRegisters:
546        read(JSVariableObject_registers);
547        return;
548
549    case GetClosureVar:
550        read(AbstractHeap(Variables, node->varNumber()));
551        return;
552
553    case PutClosureVar:
554        write(AbstractHeap(Variables, node->varNumber()));
555        return;
556
557    case GetGlobalVar:
558        read(AbstractHeap(Absolute, node->registerPointer()));
559        return;
560
561    case PutGlobalVar:
562        write(AbstractHeap(Absolute, node->registerPointer()));
563        return;
564
565    case NewObject:
566    case NewArray:
567    case NewArrayWithSize:
568    case NewArrayBuffer:
569    case NewRegexp:
570    case NewStringObject:
571    case MakeRope:
572    case NewFunctionNoCheck:
573    case NewFunction:
574    case NewFunctionExpression:
575        clobberizeForAllocation(read, write);
576        return;
577
578    case NewTypedArray:
579        clobberizeForAllocation(read, write);
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        clobberizeForAllocation(read, write);
658        return;
659
660    case CountExecution:
661    case CheckWatchdogTimer:
662        read(InternalState);
663        write(InternalState);
664        return;
665
666    case StoreBarrier:
667    case StoreBarrierWithNullCheck:
668        read(BarrierState);
669        write(BarrierState);
670        return;
671
672    case LastNodeType:
673        RELEASE_ASSERT_NOT_REACHED();
674        return;
675    }
676
677    RELEASE_ASSERT_NOT_REACHED();
678}
679
680class NoOpClobberize {
681public:
682    NoOpClobberize() { }
683    void operator()(AbstractHeap) { }
684};
685
686class CheckClobberize {
687public:
688    CheckClobberize()
689        : m_result(false)
690    {
691    }
692
693    void operator()(AbstractHeap) { m_result = true; }
694
695    bool result() const { return m_result; }
696
697private:
698    bool m_result;
699};
700
701bool doesWrites(Graph&, Node*);
702
703class AbstractHeapOverlaps {
704public:
705    AbstractHeapOverlaps(AbstractHeap heap)
706        : m_heap(heap)
707        , m_result(false)
708    {
709    }
710
711    void operator()(AbstractHeap otherHeap)
712    {
713        if (m_result)
714            return;
715        m_result = m_heap.overlaps(otherHeap);
716    }
717
718    bool result() const { return m_result; }
719
720private:
721    AbstractHeap m_heap;
722    bool m_result;
723};
724
725bool writesOverlap(Graph&, Node*, AbstractHeap);
726
727} } // namespace JSC::DFG
728
729#endif // ENABLE(DFG_JIT)
730
731#endif // DFGClobberize_h
732
733