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