Unreviewed, rolling out r205504.
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSafeToExecute.h
1 /*
2  * Copyright (C) 2013-2016 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 #ifndef DFGSafeToExecute_h
27 #define DFGSafeToExecute_h
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGGraph.h"
32
33 namespace JSC { namespace DFG {
34
35 template<typename AbstractStateType>
36 class SafeToExecuteEdge {
37 public:
38     SafeToExecuteEdge(AbstractStateType& state)
39         : m_state(state)
40         , m_result(true)
41     {
42     }
43     
44     void operator()(Node*, Edge edge)
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 FunctionUse:
59         case FinalObjectUse:
60         case RegExpObjectUse:
61         case ObjectOrOtherUse:
62         case StringIdentUse:
63         case StringUse:
64         case StringOrOtherUse:
65         case SymbolUse:
66         case StringObjectUse:
67         case StringOrStringObjectUse:
68         case NotStringVarUse:
69         case NotCellUse:
70         case OtherUse:
71         case MiscUse:
72         case AnyIntUse:
73         case DoubleRepAnyIntUse:
74             return;
75             
76         case KnownInt32Use:
77             if (m_state.forNode(edge).m_type & ~SpecInt32Only)
78                 m_result = false;
79             return;
80
81         case KnownBooleanUse:
82             if (m_state.forNode(edge).m_type & ~SpecBoolean)
83                 m_result = false;
84             return;
85             
86         case KnownCellUse:
87             if (m_state.forNode(edge).m_type & ~SpecCell)
88                 m_result = false;
89             return;
90             
91         case KnownStringUse:
92             if (m_state.forNode(edge).m_type & ~SpecString)
93                 m_result = false;
94             return;
95
96         case KnownPrimitiveUse:
97             if (m_state.forNode(edge).m_type & ~(SpecHeapTop & ~SpecObject))
98                 m_result = false;
99             return;
100             
101         case LastUseKind:
102             RELEASE_ASSERT_NOT_REACHED();
103             break;
104         }
105         RELEASE_ASSERT_NOT_REACHED();
106     }
107     
108     bool result() const { return m_result; }
109 private:
110     AbstractStateType& m_state;
111     bool m_result;
112 };
113
114 // Determines if it's safe to execute a node within the given abstract state. This may
115 // return false conservatively. If it returns true, then you can hoist the given node
116 // up to the given point and expect that it will not crash. It also guarantees that the
117 // node will not produce a malformed JSValue or object pointer when executed in the
118 // given state. But this doesn't guarantee that the node will produce the result you
119 // wanted. For example, you may have a GetByOffset from a prototype that only makes
120 // semantic sense if you've also checked that some nearer prototype doesn't also have
121 // a property of the same name. This could still return true even if that check hadn't
122 // been performed in the given abstract state. That's fine though: the load can still
123 // safely execute before that check, so long as that check continues to guard any
124 // user-observable things done to the loaded value.
125 template<typename AbstractStateType>
126 bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
127 {
128     SafeToExecuteEdge<AbstractStateType> safeToExecuteEdge(state);
129     DFG_NODE_DO_TO_CHILDREN(graph, node, safeToExecuteEdge);
130     if (!safeToExecuteEdge.result())
131         return false;
132
133     // NOTE: This tends to lie when it comes to effectful nodes, because it knows that they aren't going to
134     // get hoisted anyway.
135
136     switch (node->op()) {
137     case JSConstant:
138     case DoubleConstant:
139     case Int52Constant:
140     case LazyJSConstant:
141     case Identity:
142     case ToThis:
143     case CreateThis:
144     case GetCallee:
145     case GetArgumentCountIncludingThis:
146     case GetRestLength:
147     case GetLocal:
148     case SetLocal:
149     case PutStack:
150     case KillStack:
151     case GetStack:
152     case MovHint:
153     case ZombieHint:
154     case ExitOK:
155     case Phantom:
156     case Upsilon:
157     case Phi:
158     case Flush:
159     case PhantomLocal:
160     case GetLocalUnlinked:
161     case SetArgument:
162     case BitAnd:
163     case BitOr:
164     case BitXor:
165     case BitLShift:
166     case BitRShift:
167     case BitURShift:
168     case ValueToInt32:
169     case UInt32ToNumber:
170     case DoubleAsInt32:
171     case ArithAdd:
172     case ArithClz32:
173     case ArithSub:
174     case ArithNegate:
175     case ArithMul:
176     case ArithIMul:
177     case ArithDiv:
178     case ArithMod:
179     case ArithAbs:
180     case ArithMin:
181     case ArithMax:
182     case ArithPow:
183     case ArithRandom:
184     case ArithSqrt:
185     case ArithFRound:
186     case ArithRound:
187     case ArithFloor:
188     case ArithCeil:
189     case ArithTrunc:
190     case ArithSin:
191     case ArithCos:
192     case ArithLog:
193     case ValueAdd:
194     case TryGetById:
195     case DeleteById:
196     case DeleteByVal:
197     case GetById:
198     case GetByIdWithThis:
199     case GetByValWithThis:
200     case GetByIdFlush:
201     case PutById:
202     case PutByIdFlush:
203     case PutByIdWithThis:
204     case PutByValWithThis:
205     case PutByIdDirect:
206     case PutGetterById:
207     case PutSetterById:
208     case PutGetterSetterById:
209     case PutGetterByVal:
210     case PutSetterByVal:
211     case CheckStructure:
212     case GetExecutable:
213     case GetButterfly:
214     case CheckArray:
215     case Arrayify:
216     case ArrayifyToStructure:
217     case GetScope:
218     case SkipScope:
219     case GetGlobalObject:
220     case GetClosureVar:
221     case PutClosureVar:
222     case GetGlobalVar:
223     case GetGlobalLexicalVariable:
224     case PutGlobalVariable:
225     case CheckCell:
226     case CheckBadCell:
227     case CheckNotEmpty:
228     case CheckStringIdent:
229     case RegExpExec:
230     case RegExpTest:
231     case CompareLess:
232     case CompareLessEq:
233     case CompareGreater:
234     case CompareGreaterEq:
235     case CompareEq:
236     case CompareStrictEq:
237     case CompareEqPtr:
238     case Call:
239     case TailCallInlinedCaller:
240     case Construct:
241     case CallVarargs:
242     case CallEval:
243     case TailCallVarargsInlinedCaller:
244     case TailCallForwardVarargsInlinedCaller:
245     case ConstructVarargs:
246     case LoadVarargs:
247     case CallForwardVarargs:
248     case ConstructForwardVarargs:
249     case NewObject:
250     case NewArray:
251     case NewArrayWithSize:
252     case NewArrayBuffer:
253     case NewRegexp:
254     case ProfileType:
255     case ProfileControlFlow:
256     case CheckTypeInfoFlags:
257     case OverridesHasInstance:
258     case InstanceOf:
259     case InstanceOfCustom:
260     case IsJSArray:
261     case IsEmpty:
262     case IsUndefined:
263     case IsBoolean:
264     case IsNumber:
265     case IsString:
266     case IsObject:
267     case IsObjectOrNull:
268     case IsFunction:
269     case IsRegExpObject:
270     case IsTypedArrayView:
271     case TypeOf:
272     case LogicalNot:
273     case CallObjectConstructor:
274     case ToPrimitive:
275     case ToString:
276     case ToNumber:
277     case SetFunctionName:
278     case StrCat:
279     case CallStringConstructor:
280     case NewStringObject:
281     case MakeRope:
282     case In:
283     case CreateActivation:
284     case CreateDirectArguments:
285     case CreateScopedArguments:
286     case CreateClonedArguments:
287     case GetFromArguments:
288     case PutToArguments:
289     case NewFunction:
290     case NewGeneratorFunction:
291     case Jump:
292     case Branch:
293     case Switch:
294     case Return:
295     case TailCall:
296     case TailCallVarargs:
297     case TailCallForwardVarargs:
298     case Throw:
299     case ThrowReferenceError:
300     case CountExecution:
301     case ForceOSRExit:
302     case CheckWatchdogTimer:
303     case LogShadowChickenPrologue:
304     case LogShadowChickenTail:
305     case StringFromCharCode:
306     case NewTypedArray:
307     case Unreachable:
308     case ExtractOSREntryLocal:
309     case CheckTierUpInLoop:
310     case CheckTierUpAtReturn:
311     case CheckTierUpAndOSREnter:
312     case LoopHint:
313     case StoreBarrier:
314     case InvalidationPoint:
315     case NotifyWrite:
316     case CheckInBounds:
317     case ConstantStoragePointer:
318     case Check:
319     case MultiPutByOffset:
320     case ValueRep:
321     case DoubleRep:
322     case Int52Rep:
323     case BooleanToNumber:
324     case FiatInt52:
325     case GetGetter:
326     case GetSetter:
327     case GetEnumerableLength:
328     case HasGenericProperty:
329     case HasStructureProperty:
330     case HasIndexedProperty:
331     case GetDirectPname:
332     case GetPropertyEnumerator:
333     case GetEnumeratorStructurePname:
334     case GetEnumeratorGenericPname:
335     case ToIndexString:
336     case PhantomNewObject:
337     case PhantomNewFunction:
338     case PhantomNewGeneratorFunction:
339     case PhantomCreateActivation:
340     case PutHint:
341     case CheckStructureImmediate:
342     case MaterializeNewObject:
343     case MaterializeCreateActivation:
344     case PhantomDirectArguments:
345     case PhantomClonedArguments:
346     case GetMyArgumentByVal:
347     case GetMyArgumentByValOutOfBounds:
348     case ForwardVarargs:
349     case CreateRest:
350     case StringReplace:
351     case StringReplaceRegExp:
352     case GetRegExpObjectLastIndex:
353     case SetRegExpObjectLastIndex:
354     case RecordRegExpCachedResult:
355     case GetDynamicVar:
356     case PutDynamicVar:
357     case ResolveScope:
358         return true;
359
360     case BottomValue:
361         // If in doubt, assume that this isn't safe to execute, just because we have no way of
362         // compiling this node.
363         return false;
364
365     case GetByVal:
366     case GetIndexedPropertyStorage:
367     case GetArrayLength:
368     case ArrayPush:
369     case ArrayPop:
370     case StringCharAt:
371     case StringCharCodeAt:
372         return node->arrayMode().alreadyChecked(graph, node, state.forNode(node->child1()));
373         
374     case GetTypedArrayByteOffset:
375         return !(state.forNode(node->child1()).m_type & ~(SpecTypedArrayView));
376             
377     case PutByValDirect:
378     case PutByVal:
379     case PutByValAlias:
380         return node->arrayMode().modeForPut().alreadyChecked(
381             graph, node, state.forNode(graph.varArgChild(node, 0)));
382
383     case PutStructure:
384     case AllocatePropertyStorage:
385     case ReallocatePropertyStorage:
386         return state.forNode(node->child1()).m_structure.isSubsetOf(
387             StructureSet(node->transition()->previous));
388         
389     case GetByOffset:
390     case GetGetterSetterByOffset:
391     case PutByOffset: {
392         PropertyOffset offset = node->storageAccessData().offset;
393
394         if (state.structureClobberState() == StructuresAreWatched) {
395             if (JSObject* knownBase = node->child1()->dynamicCastConstant<JSObject*>()) {
396                 if (graph.isSafeToLoad(knownBase, offset))
397                     return true;
398             }
399         }
400         
401         StructureAbstractValue& value = state.forNode(node->child1()).m_structure;
402         if (value.isInfinite())
403             return false;
404         for (unsigned i = value.size(); i--;) {
405             if (!value[i]->isValidOffset(offset))
406                 return false;
407         }
408         return true;
409     }
410         
411     case MultiGetByOffset: {
412         // We can't always guarantee that the MultiGetByOffset is safe to execute if it
413         // contains loads from prototypes. If the load requires a check in IR, which is rare, then
414         // we currently claim that we don't know if it's safe to execute because finding that
415         // check in the abstract state would be hard. If the load requires watchpoints, we just
416         // check if we're not in a clobbered state (i.e. in between a side effect and an
417         // invalidation point).
418         for (const MultiGetByOffsetCase& getCase : node->multiGetByOffsetData().cases) {
419             GetByOffsetMethod method = getCase.method();
420             switch (method.kind()) {
421             case GetByOffsetMethod::Invalid:
422                 RELEASE_ASSERT_NOT_REACHED();
423                 break;
424             case GetByOffsetMethod::Constant: // OK because constants are always safe to execute.
425             case GetByOffsetMethod::Load: // OK because the MultiGetByOffset has its own checks for loading from self.
426                 break;
427             case GetByOffsetMethod::LoadFromPrototype:
428                 // Only OK if the state isn't clobbered. That's almost always the case.
429                 if (state.structureClobberState() != StructuresAreWatched)
430                     return false;
431                 if (!graph.isSafeToLoad(method.prototype()->cast<JSObject*>(), method.offset()))
432                     return false;
433                 break;
434             }
435         }
436         return true;
437     }
438
439     case LastNodeType:
440         RELEASE_ASSERT_NOT_REACHED();
441         return false;
442     }
443     
444     RELEASE_ASSERT_NOT_REACHED();
445     return false;
446 }
447
448 } } // namespace JSC::DFG
449
450 #endif // ENABLE(DFG_JIT)
451
452 #endif // DFGSafeToExecute_h
453