cbfae9f12c2e76a26e08ef555e7c88b289c85bbb
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSafeToExecute.h
1 /*
2  * Copyright (C) 2013-2017 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 #pragma once
27
28 #if ENABLE(DFG_JIT)
29
30 #include "DFGGraph.h"
31
32 namespace JSC { namespace DFG {
33
34 template<typename AbstractStateType>
35 class SafeToExecuteEdge {
36 public:
37     SafeToExecuteEdge(AbstractStateType& state)
38         : m_state(state)
39     {
40     }
41     
42     void operator()(Node*, Edge edge)
43     {
44         m_maySeeEmptyChild |= !!(m_state.forNode(edge).m_type & SpecEmpty);
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 ProxyObjectUse:
63         case DerivedArrayUse:
64         case MapObjectUse:
65         case SetObjectUse:
66         case WeakMapObjectUse:
67         case WeakSetObjectUse:
68         case ObjectOrOtherUse:
69         case StringIdentUse:
70         case StringUse:
71         case StringOrOtherUse:
72         case SymbolUse:
73         case StringObjectUse:
74         case StringOrStringObjectUse:
75         case NotStringVarUse:
76         case NotSymbolUse:
77         case NotCellUse:
78         case OtherUse:
79         case MiscUse:
80         case AnyIntUse:
81         case DoubleRepAnyIntUse:
82             return;
83             
84         case KnownInt32Use:
85             if (m_state.forNode(edge).m_type & ~SpecInt32Only)
86                 m_result = false;
87             return;
88
89         case KnownBooleanUse:
90             if (m_state.forNode(edge).m_type & ~SpecBoolean)
91                 m_result = false;
92             return;
93             
94         case KnownCellUse:
95             if (m_state.forNode(edge).m_type & ~SpecCell)
96                 m_result = false;
97             return;
98             
99         case KnownStringUse:
100             if (m_state.forNode(edge).m_type & ~SpecString)
101                 m_result = false;
102             return;
103
104         case KnownPrimitiveUse:
105             if (m_state.forNode(edge).m_type & ~(SpecHeapTop & ~SpecObject))
106                 m_result = false;
107             return;
108             
109         case LastUseKind:
110             RELEASE_ASSERT_NOT_REACHED();
111             break;
112         }
113         RELEASE_ASSERT_NOT_REACHED();
114     }
115     
116     bool result() const { return m_result; }
117     bool maySeeEmptyChild() const { return m_maySeeEmptyChild; }
118 private:
119     AbstractStateType& m_state;
120     bool m_result { true };
121     bool m_maySeeEmptyChild { false };
122 };
123
124 // Determines if it's safe to execute a node within the given abstract state. This may
125 // return false conservatively. If it returns true, then you can hoist the given node
126 // up to the given point and expect that it will not crash. It also guarantees that the
127 // node will not produce a malformed JSValue or object pointer when executed in the
128 // given state. But this doesn't guarantee that the node will produce the result you
129 // wanted. For example, you may have a GetByOffset from a prototype that only makes
130 // semantic sense if you've also checked that some nearer prototype doesn't also have
131 // a property of the same name. This could still return true even if that check hadn't
132 // been performed in the given abstract state. That's fine though: the load can still
133 // safely execute before that check, so long as that check continues to guard any
134 // user-observable things done to the loaded value.
135 template<typename AbstractStateType>
136 bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
137 {
138     SafeToExecuteEdge<AbstractStateType> safeToExecuteEdge(state);
139     DFG_NODE_DO_TO_CHILDREN(graph, node, safeToExecuteEdge);
140     if (!safeToExecuteEdge.result())
141         return false;
142
143     if (safeToExecuteEdge.maySeeEmptyChild()) {
144         // We conservatively assume if the empty value flows into a node,
145         // it might not be able to handle it (e.g, crash). In general, the bytecode generator
146         // emits code in such a way that most node types don't need to worry about the empty value
147         // because they will never see it. However, code motion has to consider the empty
148         // value so it does not insert/move nodes to a place where they will crash. E.g, the
149         // type check hoisting phase needs to insert CheckStructureOrEmpty instead of CheckStructure
150         // for hoisted structure checks because it can not guarantee that a particular local is not
151         // the empty value.
152         switch (node->op()) {
153         case CheckNotEmpty:
154         case CheckStructureOrEmpty:
155             break;
156         default:
157             return false;
158         }
159     }
160
161     // NOTE: This tends to lie when it comes to effectful nodes, because it knows that they aren't going to
162     // get hoisted anyway.
163
164     switch (node->op()) {
165     case JSConstant:
166     case DoubleConstant:
167     case Int52Constant:
168     case LazyJSConstant:
169     case Identity:
170     case IdentityWithProfile:
171     case ToThis:
172     case CreateThis:
173     case GetCallee:
174     case GetArgumentCountIncludingThis:
175     case GetRestLength:
176     case GetLocal:
177     case SetLocal:
178     case PutStack:
179     case KillStack:
180     case GetStack:
181     case MovHint:
182     case ZombieHint:
183     case ExitOK:
184     case Phantom:
185     case Upsilon:
186     case Phi:
187     case Flush:
188     case PhantomLocal:
189     case SetArgument:
190     case BitAnd:
191     case BitOr:
192     case BitXor:
193     case BitLShift:
194     case BitRShift:
195     case BitURShift:
196     case ValueToInt32:
197     case UInt32ToNumber:
198     case DoubleAsInt32:
199     case ArithAdd:
200     case ArithClz32:
201     case ArithSub:
202     case ArithNegate:
203     case ArithMul:
204     case ArithIMul:
205     case ArithDiv:
206     case ArithMod:
207     case ArithAbs:
208     case ArithMin:
209     case ArithMax:
210     case ArithPow:
211     case ArithRandom:
212     case ArithSqrt:
213     case ArithFRound:
214     case ArithRound:
215     case ArithFloor:
216     case ArithCeil:
217     case ArithTrunc:
218     case ArithUnary:
219     case ValueAdd:
220     case TryGetById:
221     case DeleteById:
222     case DeleteByVal:
223     case GetById:
224     case GetByIdWithThis:
225     case GetByValWithThis:
226     case GetByIdFlush:
227     case PutById:
228     case PutByIdFlush:
229     case PutByIdWithThis:
230     case PutByValWithThis:
231     case PutByIdDirect:
232     case PutGetterById:
233     case PutSetterById:
234     case PutGetterSetterById:
235     case PutGetterByVal:
236     case PutSetterByVal:
237     case DefineDataProperty:
238     case DefineAccessorProperty:
239     case CheckStructure:
240     case CheckStructureOrEmpty:
241     case GetExecutable:
242     case GetButterfly:
243     case CallDOMGetter:
244     case CallDOM:
245     case CheckSubClass:
246     case CheckArray:
247     case Arrayify:
248     case ArrayifyToStructure:
249     case GetScope:
250     case SkipScope:
251     case GetGlobalObject:
252     case GetGlobalThis:
253     case GetClosureVar:
254     case PutClosureVar:
255     case GetGlobalVar:
256     case GetGlobalLexicalVariable:
257     case PutGlobalVariable:
258     case CheckCell:
259     case CheckBadCell:
260     case CheckNotEmpty:
261     case CheckStringIdent:
262     case RegExpExec:
263     case RegExpTest:
264     case CompareLess:
265     case CompareLessEq:
266     case CompareGreater:
267     case CompareGreaterEq:
268     case CompareBelow:
269     case CompareBelowEq:
270     case CompareEq:
271     case CompareStrictEq:
272     case CompareEqPtr:
273     case Call:
274     case DirectCall:
275     case TailCallInlinedCaller:
276     case DirectTailCallInlinedCaller:
277     case Construct:
278     case DirectConstruct:
279     case CallVarargs:
280     case CallEval:
281     case TailCallVarargsInlinedCaller:
282     case TailCallForwardVarargsInlinedCaller:
283     case ConstructVarargs:
284     case LoadVarargs:
285     case CallForwardVarargs:
286     case ConstructForwardVarargs:
287     case NewObject:
288     case NewArray:
289     case NewArrayWithSize:
290     case NewArrayBuffer:
291     case NewArrayWithSpread:
292     case Spread:
293     case NewRegexp:
294     case ProfileType:
295     case ProfileControlFlow:
296     case CheckTypeInfoFlags:
297     case ParseInt:
298     case OverridesHasInstance:
299     case InstanceOf:
300     case InstanceOfCustom:
301     case IsEmpty:
302     case IsUndefined:
303     case IsBoolean:
304     case IsNumber:
305     case IsObject:
306     case IsObjectOrNull:
307     case IsFunction:
308     case IsCellWithType:
309     case IsTypedArrayView:
310     case TypeOf:
311     case LogicalNot:
312     case CallObjectConstructor:
313     case ToPrimitive:
314     case ToString:
315     case ToNumber:
316     case ToObject:
317     case NumberToStringWithRadix:
318     case NumberToStringWithValidRadixConstant:
319     case SetFunctionName:
320     case StrCat:
321     case CallStringConstructor:
322     case NewStringObject:
323     case MakeRope:
324     case In:
325     case HasOwnProperty:
326     case PushWithScope:
327     case CreateActivation:
328     case CreateDirectArguments:
329     case CreateScopedArguments:
330     case CreateClonedArguments:
331     case GetFromArguments:
332     case GetArgument:
333     case PutToArguments:
334     case NewFunction:
335     case NewGeneratorFunction:
336     case NewAsyncGeneratorFunction:
337     case NewAsyncFunction:
338     case Jump:
339     case Branch:
340     case Switch:
341     case EntrySwitch:
342     case Return:
343     case TailCall:
344     case DirectTailCall:
345     case TailCallVarargs:
346     case TailCallForwardVarargs:
347     case Throw:
348     case ThrowStaticError:
349     case CountExecution:
350     case SuperSamplerBegin:
351     case SuperSamplerEnd:
352     case ForceOSRExit:
353     case CPUIntrinsic:
354     case CheckTraps:
355     case LogShadowChickenPrologue:
356     case LogShadowChickenTail:
357     case StringFromCharCode:
358     case NewTypedArray:
359     case Unreachable:
360     case ExtractOSREntryLocal:
361     case ExtractCatchLocal:
362     case CheckTierUpInLoop:
363     case CheckTierUpAtReturn:
364     case CheckTierUpAndOSREnter:
365     case LoopHint:
366     case InvalidationPoint:
367     case NotifyWrite:
368     case CheckInBounds:
369     case ConstantStoragePointer:
370     case Check:
371     case MultiPutByOffset:
372     case ValueRep:
373     case DoubleRep:
374     case Int52Rep:
375     case BooleanToNumber:
376     case FiatInt52:
377     case GetGetter:
378     case GetSetter:
379     case GetEnumerableLength:
380     case HasGenericProperty:
381     case HasStructureProperty:
382     case HasIndexedProperty:
383     case GetDirectPname:
384     case GetPropertyEnumerator:
385     case GetEnumeratorStructurePname:
386     case GetEnumeratorGenericPname:
387     case ToIndexString:
388     case PhantomNewObject:
389     case PhantomNewFunction:
390     case PhantomNewGeneratorFunction:
391     case PhantomNewAsyncGeneratorFunction:
392     case PhantomNewAsyncFunction:
393     case PhantomCreateActivation:
394     case PutHint:
395     case CheckStructureImmediate:
396     case MaterializeNewObject:
397     case MaterializeCreateActivation:
398     case PhantomDirectArguments:
399     case PhantomCreateRest:
400     case PhantomSpread:
401     case PhantomNewArrayWithSpread:
402     case PhantomClonedArguments:
403     case GetMyArgumentByVal:
404     case GetMyArgumentByValOutOfBounds:
405     case ForwardVarargs:
406     case CreateRest:
407     case GetPrototypeOf:
408     case StringReplace:
409     case StringReplaceRegExp:
410     case GetRegExpObjectLastIndex:
411     case SetRegExpObjectLastIndex:
412     case RecordRegExpCachedResult:
413     case GetDynamicVar:
414     case PutDynamicVar:
415     case ResolveScopeForHoistingFuncDeclInEval:
416     case ResolveScope:
417     case MapHash:
418     case NormalizeMapKey:
419     case StringSlice:
420     case ToLowerCase:
421     case GetMapBucket:
422     case GetMapBucketHead:
423     case GetMapBucketNext:
424     case LoadKeyFromMapBucket:
425     case LoadValueFromMapBucket:
426     case ExtractValueFromWeakMapGet:
427     case WeakMapGet:
428     case AtomicsAdd:
429     case AtomicsAnd:
430     case AtomicsCompareExchange:
431     case AtomicsExchange:
432     case AtomicsLoad:
433     case AtomicsOr:
434     case AtomicsStore:
435     case AtomicsSub:
436     case AtomicsXor:
437     case AtomicsIsLockFree:
438     case InitializeEntrypointArguments:
439         return true;
440
441     case ArraySlice:
442     case ArrayIndexOf: {
443         // You could plausibly move this code around as long as you proved the
444         // incoming array base structure is an original array at the hoisted location.
445         // Instead of doing that extra work, we just conservatively return false.
446         return false;
447     }
448
449     case BottomValue:
450         // If in doubt, assume that this isn't safe to execute, just because we have no way of
451         // compiling this node.
452         return false;
453
454     case StoreBarrier:
455     case FencedStoreBarrier:
456     case PutStructure:
457     case NukeStructureAndSetButterfly:
458         // We conservatively assume that these cannot be put anywhere, which forces the compiler to
459         // keep them exactly where they were. This is sort of overkill since the clobberize effects
460         // already force these things to be ordered precisely. I'm just not confident enough in my
461         // effect based memory model to rely solely on that right now.
462         return false;
463
464     case GetByVal:
465     case GetIndexedPropertyStorage:
466     case GetArrayLength:
467     case GetVectorLength:
468     case ArrayPop:
469     case StringCharAt:
470     case StringCharCodeAt:
471         return node->arrayMode().alreadyChecked(graph, node, state.forNode(node->child1()));
472
473     case ArrayPush:
474         return node->arrayMode().alreadyChecked(graph, node, state.forNode(graph.varArgChild(node, 1)));
475
476     case GetTypedArrayByteOffset:
477         return !(state.forNode(node->child1()).m_type & ~(SpecTypedArrayView));
478             
479     case PutByValDirect:
480     case PutByVal:
481     case PutByValAlias:
482         return node->arrayMode().modeForPut().alreadyChecked(
483             graph, node, state.forNode(graph.varArgChild(node, 0)));
484
485     case AllocatePropertyStorage:
486     case ReallocatePropertyStorage:
487         return state.forNode(node->child1()).m_structure.isSubsetOf(
488             RegisteredStructureSet(node->transition()->previous));
489         
490     case GetByOffset:
491     case GetGetterSetterByOffset:
492     case PutByOffset: {
493         PropertyOffset offset = node->storageAccessData().offset;
494
495         if (state.structureClobberState() == StructuresAreWatched) {
496             if (JSObject* knownBase = node->child1()->dynamicCastConstant<JSObject*>(graph.m_vm)) {
497                 if (graph.isSafeToLoad(knownBase, offset))
498                     return true;
499             }
500         }
501         
502         StructureAbstractValue& value = state.forNode(node->child1()).m_structure;
503         if (value.isInfinite())
504             return false;
505         for (unsigned i = value.size(); i--;) {
506             if (!value[i]->isValidOffset(offset))
507                 return false;
508         }
509         return true;
510     }
511         
512     case MultiGetByOffset: {
513         // We can't always guarantee that the MultiGetByOffset is safe to execute if it
514         // contains loads from prototypes. If the load requires a check in IR, which is rare, then
515         // we currently claim that we don't know if it's safe to execute because finding that
516         // check in the abstract state would be hard. If the load requires watchpoints, we just
517         // check if we're not in a clobbered state (i.e. in between a side effect and an
518         // invalidation point).
519         for (const MultiGetByOffsetCase& getCase : node->multiGetByOffsetData().cases) {
520             GetByOffsetMethod method = getCase.method();
521             switch (method.kind()) {
522             case GetByOffsetMethod::Invalid:
523                 RELEASE_ASSERT_NOT_REACHED();
524                 break;
525             case GetByOffsetMethod::Constant: // OK because constants are always safe to execute.
526             case GetByOffsetMethod::Load: // OK because the MultiGetByOffset has its own checks for loading from self.
527                 break;
528             case GetByOffsetMethod::LoadFromPrototype:
529                 // Only OK if the state isn't clobbered. That's almost always the case.
530                 if (state.structureClobberState() != StructuresAreWatched)
531                     return false;
532                 if (!graph.isSafeToLoad(method.prototype()->cast<JSObject*>(), method.offset()))
533                     return false;
534                 break;
535             }
536         }
537         return true;
538     }
539
540     case SetAdd:
541     case MapSet:
542         return false;
543
544     case LastNodeType:
545         RELEASE_ASSERT_NOT_REACHED();
546         return false;
547     }
548     
549     RELEASE_ASSERT_NOT_REACHED();
550     return false;
551 }
552
553 } } // namespace JSC::DFG
554
555 #endif // ENABLE(DFG_JIT)