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