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