[DFG] Introduce ArrayUse
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSafeToExecute.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 DFGSafeToExecute_h
27 #define DFGSafeToExecute_h
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGGraph.h"
32
33 namespace JSC { namespace DFG {
34
35 template<typename AbstractStateType>
36 class SafeToExecuteEdge {
37 public:
38     SafeToExecuteEdge(AbstractStateType& state)
39         : m_state(state)
40         , m_result(true)
41     {
42     }
43     
44     void operator()(Node*, Edge edge)
45     {
46         switch (edge.useKind()) {
47         case UntypedUse:
48         case Int32Use:
49         case DoubleRepUse:
50         case DoubleRepRealUse:
51         case Int52RepUse:
52         case NumberUse:
53         case RealNumberUse:
54         case BooleanUse:
55         case CellUse:
56         case CellOrOtherUse:
57         case ObjectUse:
58         case ArrayUse:
59         case FunctionUse:
60         case FinalObjectUse:
61         case RegExpObjectUse:
62         case MapObjectUse:
63         case SetObjectUse:
64         case ObjectOrOtherUse:
65         case StringIdentUse:
66         case StringUse:
67         case StringOrOtherUse:
68         case SymbolUse:
69         case StringObjectUse:
70         case StringOrStringObjectUse:
71         case NotStringVarUse:
72         case NotCellUse:
73         case OtherUse:
74         case MiscUse:
75         case AnyIntUse:
76         case DoubleRepAnyIntUse:
77             return;
78             
79         case KnownInt32Use:
80             if (m_state.forNode(edge).m_type & ~SpecInt32Only)
81                 m_result = false;
82             return;
83
84         case KnownBooleanUse:
85             if (m_state.forNode(edge).m_type & ~SpecBoolean)
86                 m_result = false;
87             return;
88             
89         case KnownCellUse:
90             if (m_state.forNode(edge).m_type & ~SpecCell)
91                 m_result = false;
92             return;
93             
94         case KnownStringUse:
95             if (m_state.forNode(edge).m_type & ~SpecString)
96                 m_result = false;
97             return;
98
99         case KnownPrimitiveUse:
100             if (m_state.forNode(edge).m_type & ~(SpecHeapTop & ~SpecObject))
101                 m_result = false;
102             return;
103             
104         case LastUseKind:
105             RELEASE_ASSERT_NOT_REACHED();
106             break;
107         }
108         RELEASE_ASSERT_NOT_REACHED();
109     }
110     
111     bool result() const { return m_result; }
112 private:
113     AbstractStateType& m_state;
114     bool m_result;
115 };
116
117 // Determines if it's safe to execute a node within the given abstract state. This may
118 // return false conservatively. If it returns true, then you can hoist the given node
119 // up to the given point and expect that it will not crash. It also guarantees that the
120 // node will not produce a malformed JSValue or object pointer when executed in the
121 // given state. But this doesn't guarantee that the node will produce the result you
122 // wanted. For example, you may have a GetByOffset from a prototype that only makes
123 // semantic sense if you've also checked that some nearer prototype doesn't also have
124 // a property of the same name. This could still return true even if that check hadn't
125 // been performed in the given abstract state. That's fine though: the load can still
126 // safely execute before that check, so long as that check continues to guard any
127 // user-observable things done to the loaded value.
128 template<typename AbstractStateType>
129 bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
130 {
131     SafeToExecuteEdge<AbstractStateType> safeToExecuteEdge(state);
132     DFG_NODE_DO_TO_CHILDREN(graph, node, safeToExecuteEdge);
133     if (!safeToExecuteEdge.result())
134         return false;
135
136     // NOTE: This tends to lie when it comes to effectful nodes, because it knows that they aren't going to
137     // get hoisted anyway.
138
139     switch (node->op()) {
140     case JSConstant:
141     case DoubleConstant:
142     case Int52Constant:
143     case LazyJSConstant:
144     case Identity:
145     case ToThis:
146     case CreateThis:
147     case GetCallee:
148     case GetArgumentCountIncludingThis:
149     case GetRestLength:
150     case GetLocal:
151     case SetLocal:
152     case PutStack:
153     case KillStack:
154     case GetStack:
155     case MovHint:
156     case ZombieHint:
157     case ExitOK:
158     case Phantom:
159     case Upsilon:
160     case Phi:
161     case Flush:
162     case PhantomLocal:
163     case GetLocalUnlinked:
164     case SetArgument:
165     case BitAnd:
166     case BitOr:
167     case BitXor:
168     case BitLShift:
169     case BitRShift:
170     case BitURShift:
171     case ValueToInt32:
172     case UInt32ToNumber:
173     case DoubleAsInt32:
174     case ArithAdd:
175     case ArithClz32:
176     case ArithSub:
177     case ArithNegate:
178     case ArithMul:
179     case ArithIMul:
180     case ArithDiv:
181     case ArithMod:
182     case ArithAbs:
183     case ArithMin:
184     case ArithMax:
185     case ArithPow:
186     case ArithRandom:
187     case ArithSqrt:
188     case ArithFRound:
189     case ArithRound:
190     case ArithFloor:
191     case ArithCeil:
192     case ArithTrunc:
193     case ArithSin:
194     case ArithCos:
195     case ArithTan:
196     case ArithLog:
197     case ValueAdd:
198     case TryGetById:
199     case DeleteById:
200     case DeleteByVal:
201     case GetById:
202     case GetByIdWithThis:
203     case GetByValWithThis:
204     case GetByIdFlush:
205     case PutById:
206     case PutByIdFlush:
207     case PutByIdWithThis:
208     case PutByValWithThis:
209     case PutByIdDirect:
210     case PutGetterById:
211     case PutSetterById:
212     case PutGetterSetterById:
213     case PutGetterByVal:
214     case PutSetterByVal:
215     case CheckStructure:
216     case GetExecutable:
217     case GetButterfly:
218     case CheckArray:
219     case Arrayify:
220     case ArrayifyToStructure:
221     case GetScope:
222     case SkipScope:
223     case GetGlobalObject:
224     case GetClosureVar:
225     case PutClosureVar:
226     case GetGlobalVar:
227     case GetGlobalLexicalVariable:
228     case PutGlobalVariable:
229     case CheckCell:
230     case CheckBadCell:
231     case CheckNotEmpty:
232     case CheckStringIdent:
233     case RegExpExec:
234     case RegExpTest:
235     case CompareLess:
236     case CompareLessEq:
237     case CompareGreater:
238     case CompareGreaterEq:
239     case CompareEq:
240     case CompareStrictEq:
241     case CompareEqPtr:
242     case Call:
243     case TailCallInlinedCaller:
244     case Construct:
245     case CallVarargs:
246     case CallEval:
247     case TailCallVarargsInlinedCaller:
248     case TailCallForwardVarargsInlinedCaller:
249     case ConstructVarargs:
250     case LoadVarargs:
251     case CallForwardVarargs:
252     case ConstructForwardVarargs:
253     case NewObject:
254     case NewArray:
255     case NewArrayWithSize:
256     case NewArrayBuffer:
257     case NewRegexp:
258     case ProfileType:
259     case ProfileControlFlow:
260     case CheckTypeInfoFlags:
261     case OverridesHasInstance:
262     case InstanceOf:
263     case InstanceOfCustom:
264     case IsJSArray:
265     case IsEmpty:
266     case IsUndefined:
267     case IsBoolean:
268     case IsNumber:
269     case IsString:
270     case IsObject:
271     case IsObjectOrNull:
272     case IsFunction:
273     case IsRegExpObject:
274     case IsTypedArrayView:
275     case TypeOf:
276     case LogicalNot:
277     case CallObjectConstructor:
278     case ToPrimitive:
279     case ToString:
280     case ToNumber:
281     case SetFunctionName:
282     case StrCat:
283     case CallStringConstructor:
284     case NewStringObject:
285     case MakeRope:
286     case In:
287     case CreateActivation:
288     case CreateDirectArguments:
289     case CreateScopedArguments:
290     case CreateClonedArguments:
291     case GetFromArguments:
292     case PutToArguments:
293     case NewFunction:
294     case NewGeneratorFunction:
295     case Jump:
296     case Branch:
297     case Switch:
298     case Return:
299     case TailCall:
300     case TailCallVarargs:
301     case TailCallForwardVarargs:
302     case Throw:
303     case ThrowReferenceError:
304     case CountExecution:
305     case ForceOSRExit:
306     case CheckWatchdogTimer:
307     case LogShadowChickenPrologue:
308     case LogShadowChickenTail:
309     case StringFromCharCode:
310     case NewTypedArray:
311     case Unreachable:
312     case ExtractOSREntryLocal:
313     case CheckTierUpInLoop:
314     case CheckTierUpAtReturn:
315     case CheckTierUpAndOSREnter:
316     case LoopHint:
317     case StoreBarrier:
318     case InvalidationPoint:
319     case NotifyWrite:
320     case CheckInBounds:
321     case ConstantStoragePointer:
322     case Check:
323     case MultiPutByOffset:
324     case ValueRep:
325     case DoubleRep:
326     case Int52Rep:
327     case BooleanToNumber:
328     case FiatInt52:
329     case GetGetter:
330     case GetSetter:
331     case GetEnumerableLength:
332     case HasGenericProperty:
333     case HasStructureProperty:
334     case HasIndexedProperty:
335     case GetDirectPname:
336     case GetPropertyEnumerator:
337     case GetEnumeratorStructurePname:
338     case GetEnumeratorGenericPname:
339     case ToIndexString:
340     case PhantomNewObject:
341     case PhantomNewFunction:
342     case PhantomNewGeneratorFunction:
343     case PhantomCreateActivation:
344     case PutHint:
345     case CheckStructureImmediate:
346     case MaterializeNewObject:
347     case MaterializeCreateActivation:
348     case PhantomDirectArguments:
349     case PhantomClonedArguments:
350     case GetMyArgumentByVal:
351     case GetMyArgumentByValOutOfBounds:
352     case ForwardVarargs:
353     case CreateRest:
354     case StringReplace:
355     case StringReplaceRegExp:
356     case GetRegExpObjectLastIndex:
357     case SetRegExpObjectLastIndex:
358     case RecordRegExpCachedResult:
359     case GetDynamicVar:
360     case PutDynamicVar:
361     case ResolveScope:
362     case MapHash:
363     case GetMapBucket:
364     case LoadFromJSMapBucket:
365     case IsNonEmptyMapBucket:
366         return true;
367
368     case BottomValue:
369         // If in doubt, assume that this isn't safe to execute, just because we have no way of
370         // compiling this node.
371         return false;
372
373     case GetByVal:
374     case GetIndexedPropertyStorage:
375     case GetArrayLength:
376     case ArrayPush:
377     case ArrayPop:
378     case StringCharAt:
379     case StringCharCodeAt:
380         return node->arrayMode().alreadyChecked(graph, node, state.forNode(node->child1()));
381         
382     case GetTypedArrayByteOffset:
383         return !(state.forNode(node->child1()).m_type & ~(SpecTypedArrayView));
384             
385     case PutByValDirect:
386     case PutByVal:
387     case PutByValAlias:
388         return node->arrayMode().modeForPut().alreadyChecked(
389             graph, node, state.forNode(graph.varArgChild(node, 0)));
390
391     case PutStructure:
392     case AllocatePropertyStorage:
393     case ReallocatePropertyStorage:
394         return state.forNode(node->child1()).m_structure.isSubsetOf(
395             StructureSet(node->transition()->previous));
396         
397     case GetByOffset:
398     case GetGetterSetterByOffset:
399     case PutByOffset: {
400         PropertyOffset offset = node->storageAccessData().offset;
401
402         if (state.structureClobberState() == StructuresAreWatched) {
403             if (JSObject* knownBase = node->child1()->dynamicCastConstant<JSObject*>()) {
404                 if (graph.isSafeToLoad(knownBase, offset))
405                     return true;
406             }
407         }
408         
409         StructureAbstractValue& value = state.forNode(node->child1()).m_structure;
410         if (value.isInfinite())
411             return false;
412         for (unsigned i = value.size(); i--;) {
413             if (!value[i]->isValidOffset(offset))
414                 return false;
415         }
416         return true;
417     }
418         
419     case MultiGetByOffset: {
420         // We can't always guarantee that the MultiGetByOffset is safe to execute if it
421         // contains loads from prototypes. If the load requires a check in IR, which is rare, then
422         // we currently claim that we don't know if it's safe to execute because finding that
423         // check in the abstract state would be hard. If the load requires watchpoints, we just
424         // check if we're not in a clobbered state (i.e. in between a side effect and an
425         // invalidation point).
426         for (const MultiGetByOffsetCase& getCase : node->multiGetByOffsetData().cases) {
427             GetByOffsetMethod method = getCase.method();
428             switch (method.kind()) {
429             case GetByOffsetMethod::Invalid:
430                 RELEASE_ASSERT_NOT_REACHED();
431                 break;
432             case GetByOffsetMethod::Constant: // OK because constants are always safe to execute.
433             case GetByOffsetMethod::Load: // OK because the MultiGetByOffset has its own checks for loading from self.
434                 break;
435             case GetByOffsetMethod::LoadFromPrototype:
436                 // Only OK if the state isn't clobbered. That's almost always the case.
437                 if (state.structureClobberState() != StructuresAreWatched)
438                     return false;
439                 if (!graph.isSafeToLoad(method.prototype()->cast<JSObject*>(), method.offset()))
440                     return false;
441                 break;
442             }
443         }
444         return true;
445     }
446
447     case LastNodeType:
448         RELEASE_ASSERT_NOT_REACHED();
449         return false;
450     }
451     
452     RELEASE_ASSERT_NOT_REACHED();
453     return false;
454 }
455
456 } } // namespace JSC::DFG
457
458 #endif // ENABLE(DFG_JIT)
459
460 #endif // DFGSafeToExecute_h
461