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