[ES6]. Implement Annex B.3.3 function hoisting rules for eval
[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 ToThis:
147     case CreateThis:
148     case GetCallee:
149     case GetArgumentCountIncludingThis:
150     case GetRestLength:
151     case GetLocal:
152     case SetLocal:
153     case PutStack:
154     case KillStack:
155     case GetStack:
156     case MovHint:
157     case ZombieHint:
158     case ExitOK:
159     case Phantom:
160     case Upsilon:
161     case Phi:
162     case Flush:
163     case PhantomLocal:
164     case GetLocalUnlinked:
165     case SetArgument:
166     case BitAnd:
167     case BitOr:
168     case BitXor:
169     case BitLShift:
170     case BitRShift:
171     case BitURShift:
172     case ValueToInt32:
173     case UInt32ToNumber:
174     case DoubleAsInt32:
175     case ArithAdd:
176     case ArithClz32:
177     case ArithSub:
178     case ArithNegate:
179     case ArithMul:
180     case ArithIMul:
181     case ArithDiv:
182     case ArithMod:
183     case ArithAbs:
184     case ArithMin:
185     case ArithMax:
186     case ArithPow:
187     case ArithRandom:
188     case ArithSqrt:
189     case ArithFRound:
190     case ArithRound:
191     case ArithFloor:
192     case ArithCeil:
193     case ArithTrunc:
194     case ArithSin:
195     case ArithCos:
196     case ArithTan:
197     case ArithLog:
198     case ValueAdd:
199     case TryGetById:
200     case DeleteById:
201     case DeleteByVal:
202     case GetById:
203     case GetByIdWithThis:
204     case GetByValWithThis:
205     case GetByIdFlush:
206     case PutById:
207     case PutByIdFlush:
208     case PutByIdWithThis:
209     case PutByValWithThis:
210     case PutByIdDirect:
211     case PutGetterById:
212     case PutSetterById:
213     case PutGetterSetterById:
214     case PutGetterByVal:
215     case PutSetterByVal:
216     case DefineDataProperty:
217     case DefineAccessorProperty:
218     case CheckStructure:
219     case GetExecutable:
220     case GetButterfly:
221     case CallDOMGetter:
222     case CallDOM:
223     case CheckDOM:
224     case CheckArray:
225     case Arrayify:
226     case ArrayifyToStructure:
227     case GetScope:
228     case SkipScope:
229     case GetGlobalObject:
230     case GetClosureVar:
231     case PutClosureVar:
232     case GetGlobalVar:
233     case GetGlobalLexicalVariable:
234     case PutGlobalVariable:
235     case CheckCell:
236     case CheckBadCell:
237     case CheckNotEmpty:
238     case CheckStringIdent:
239     case RegExpExec:
240     case RegExpTest:
241     case CompareLess:
242     case CompareLessEq:
243     case CompareGreater:
244     case CompareGreaterEq:
245     case CompareEq:
246     case CompareStrictEq:
247     case CompareEqPtr:
248     case Call:
249     case DirectCall:
250     case TailCallInlinedCaller:
251     case DirectTailCallInlinedCaller:
252     case Construct:
253     case DirectConstruct:
254     case CallVarargs:
255     case CallEval:
256     case TailCallVarargsInlinedCaller:
257     case TailCallForwardVarargsInlinedCaller:
258     case ConstructVarargs:
259     case LoadVarargs:
260     case CallForwardVarargs:
261     case ConstructForwardVarargs:
262     case NewObject:
263     case NewArray:
264     case NewArrayWithSize:
265     case NewArrayBuffer:
266     case NewArrayWithSpread:
267     case Spread:
268     case NewRegexp:
269     case ProfileType:
270     case ProfileControlFlow:
271     case CheckTypeInfoFlags:
272     case ParseInt:
273     case OverridesHasInstance:
274     case InstanceOf:
275     case InstanceOfCustom:
276     case IsEmpty:
277     case IsUndefined:
278     case IsBoolean:
279     case IsNumber:
280     case IsObject:
281     case IsObjectOrNull:
282     case IsFunction:
283     case IsCellWithType:
284     case IsTypedArrayView:
285     case TypeOf:
286     case LogicalNot:
287     case CallObjectConstructor:
288     case ToPrimitive:
289     case ToString:
290     case ToNumber:
291     case NumberToStringWithRadix:
292     case SetFunctionName:
293     case StrCat:
294     case CallStringConstructor:
295     case NewStringObject:
296     case MakeRope:
297     case In:
298     case HasOwnProperty:
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 NewAsyncFunction:
309     case Jump:
310     case Branch:
311     case Switch:
312     case Return:
313     case TailCall:
314     case DirectTailCall:
315     case TailCallVarargs:
316     case TailCallForwardVarargs:
317     case Throw:
318     case ThrowStaticError:
319     case CountExecution:
320     case ForceOSRExit:
321     case CheckTraps:
322     case LogShadowChickenPrologue:
323     case LogShadowChickenTail:
324     case StringFromCharCode:
325     case NewTypedArray:
326     case Unreachable:
327     case ExtractOSREntryLocal:
328     case CheckTierUpInLoop:
329     case CheckTierUpAtReturn:
330     case CheckTierUpAndOSREnter:
331     case LoopHint:
332     case InvalidationPoint:
333     case NotifyWrite:
334     case CheckInBounds:
335     case ConstantStoragePointer:
336     case Check:
337     case MultiPutByOffset:
338     case ValueRep:
339     case DoubleRep:
340     case Int52Rep:
341     case BooleanToNumber:
342     case FiatInt52:
343     case GetGetter:
344     case GetSetter:
345     case GetEnumerableLength:
346     case HasGenericProperty:
347     case HasStructureProperty:
348     case HasIndexedProperty:
349     case GetDirectPname:
350     case GetPropertyEnumerator:
351     case GetEnumeratorStructurePname:
352     case GetEnumeratorGenericPname:
353     case ToIndexString:
354     case PhantomNewObject:
355     case PhantomNewFunction:
356     case PhantomNewGeneratorFunction:
357     case PhantomNewAsyncFunction:
358     case PhantomCreateActivation:
359     case PutHint:
360     case CheckStructureImmediate:
361     case MaterializeNewObject:
362     case MaterializeCreateActivation:
363     case PhantomDirectArguments:
364     case PhantomCreateRest:
365     case PhantomSpread:
366     case PhantomNewArrayWithSpread:
367     case PhantomClonedArguments:
368     case GetMyArgumentByVal:
369     case GetMyArgumentByValOutOfBounds:
370     case ForwardVarargs:
371     case CreateRest:
372     case StringReplace:
373     case StringReplaceRegExp:
374     case GetRegExpObjectLastIndex:
375     case SetRegExpObjectLastIndex:
376     case RecordRegExpCachedResult:
377     case GetDynamicVar:
378     case PutDynamicVar:
379     case ResolveScopeForHoistingFuncDeclInEval:
380     case ResolveScope:
381     case MapHash:
382     case ToLowerCase:
383     case GetMapBucket:
384     case LoadFromJSMapBucket:
385     case IsNonEmptyMapBucket:
386     case AtomicsAdd:
387     case AtomicsAnd:
388     case AtomicsCompareExchange:
389     case AtomicsExchange:
390     case AtomicsLoad:
391     case AtomicsOr:
392     case AtomicsStore:
393     case AtomicsSub:
394     case AtomicsXor:
395     case AtomicsIsLockFree:
396         return true;
397
398     case ArraySlice: {
399         // You could plausibly move this code around as long as you proved the
400         // incoming array base structure is an original array at the hoisted location.
401         // Instead of doing that extra work, we just conservatively return false.
402         return false;
403     }
404
405     case BottomValue:
406         // If in doubt, assume that this isn't safe to execute, just because we have no way of
407         // compiling this node.
408         return false;
409
410     case StoreBarrier:
411     case FencedStoreBarrier:
412     case PutStructure:
413     case NukeStructureAndSetButterfly:
414         // We conservatively assume that these cannot be put anywhere, which forces the compiler to
415         // keep them exactly where they were. This is sort of overkill since the clobberize effects
416         // already force these things to be ordered precisely. I'm just not confident enough in my
417         // effect based memory model to rely solely on that right now.
418         return false;
419
420     case GetByVal:
421     case GetIndexedPropertyStorage:
422     case GetArrayLength:
423     case ArrayPush:
424     case ArrayPop:
425     case StringCharAt:
426     case StringCharCodeAt:
427         return node->arrayMode().alreadyChecked(graph, node, state.forNode(node->child1()));
428         
429     case GetTypedArrayByteOffset:
430         return !(state.forNode(node->child1()).m_type & ~(SpecTypedArrayView));
431             
432     case PutByValDirect:
433     case PutByVal:
434     case PutByValAlias:
435         return node->arrayMode().modeForPut().alreadyChecked(
436             graph, node, state.forNode(graph.varArgChild(node, 0)));
437
438     case AllocatePropertyStorage:
439     case ReallocatePropertyStorage:
440         return state.forNode(node->child1()).m_structure.isSubsetOf(
441             RegisteredStructureSet(node->transition()->previous));
442         
443     case GetByOffset:
444     case GetGetterSetterByOffset:
445     case PutByOffset: {
446         PropertyOffset offset = node->storageAccessData().offset;
447
448         if (state.structureClobberState() == StructuresAreWatched) {
449             if (JSObject* knownBase = node->child1()->dynamicCastConstant<JSObject*>(graph.m_vm)) {
450                 if (graph.isSafeToLoad(knownBase, offset))
451                     return true;
452             }
453         }
454         
455         StructureAbstractValue& value = state.forNode(node->child1()).m_structure;
456         if (value.isInfinite())
457             return false;
458         for (unsigned i = value.size(); i--;) {
459             if (!value[i]->isValidOffset(offset))
460                 return false;
461         }
462         return true;
463     }
464         
465     case MultiGetByOffset: {
466         // We can't always guarantee that the MultiGetByOffset is safe to execute if it
467         // contains loads from prototypes. If the load requires a check in IR, which is rare, then
468         // we currently claim that we don't know if it's safe to execute because finding that
469         // check in the abstract state would be hard. If the load requires watchpoints, we just
470         // check if we're not in a clobbered state (i.e. in between a side effect and an
471         // invalidation point).
472         for (const MultiGetByOffsetCase& getCase : node->multiGetByOffsetData().cases) {
473             GetByOffsetMethod method = getCase.method();
474             switch (method.kind()) {
475             case GetByOffsetMethod::Invalid:
476                 RELEASE_ASSERT_NOT_REACHED();
477                 break;
478             case GetByOffsetMethod::Constant: // OK because constants are always safe to execute.
479             case GetByOffsetMethod::Load: // OK because the MultiGetByOffset has its own checks for loading from self.
480                 break;
481             case GetByOffsetMethod::LoadFromPrototype:
482                 // Only OK if the state isn't clobbered. That's almost always the case.
483                 if (state.structureClobberState() != StructuresAreWatched)
484                     return false;
485                 if (!graph.isSafeToLoad(method.prototype()->cast<JSObject*>(), method.offset()))
486                     return false;
487                 break;
488             }
489         }
490         return true;
491     }
492
493     case LastNodeType:
494         RELEASE_ASSERT_NOT_REACHED();
495         return false;
496     }
497     
498     RELEASE_ASSERT_NOT_REACHED();
499     return false;
500 }
501
502 } } // namespace JSC::DFG
503
504 #endif // ENABLE(DFG_JIT)