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