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