[DFG] DFG should handle String#toString
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSafeToExecute.h
1 /*
2  * Copyright (C) 2013-2018 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     {
40     }
41     
42     void operator()(Node*, Edge edge)
43     {
44         m_maySeeEmptyChild |= !!(m_state.forNode(edge).m_type & SpecEmpty);
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 ArrayUse:
59         case FunctionUse:
60         case FinalObjectUse:
61         case RegExpObjectUse:
62         case ProxyObjectUse:
63         case DerivedArrayUse:
64         case MapObjectUse:
65         case SetObjectUse:
66         case WeakMapObjectUse:
67         case WeakSetObjectUse:
68         case DataViewObjectUse:
69         case ObjectOrOtherUse:
70         case StringIdentUse:
71         case StringUse:
72         case StringOrOtherUse:
73         case SymbolUse:
74         case BigIntUse:
75         case StringObjectUse:
76         case StringOrStringObjectUse:
77         case NotStringVarUse:
78         case NotSymbolUse:
79         case NotCellUse:
80         case OtherUse:
81         case MiscUse:
82         case AnyIntUse:
83         case DoubleRepAnyIntUse:
84             return;
85             
86         case KnownInt32Use:
87             if (m_state.forNode(edge).m_type & ~SpecInt32Only)
88                 m_result = false;
89             return;
90
91         case KnownBooleanUse:
92             if (m_state.forNode(edge).m_type & ~SpecBoolean)
93                 m_result = false;
94             return;
95             
96         case KnownCellUse:
97             if (m_state.forNode(edge).m_type & ~SpecCell)
98                 m_result = false;
99             return;
100             
101         case KnownStringUse:
102             if (m_state.forNode(edge).m_type & ~SpecString)
103                 m_result = false;
104             return;
105
106         case KnownPrimitiveUse:
107             if (m_state.forNode(edge).m_type & ~(SpecHeapTop & ~SpecObject))
108                 m_result = false;
109             return;
110
111         case KnownOtherUse:
112             if (m_state.forNode(edge).m_type & ~SpecOther)
113                 m_result = false;
114             return;
115             
116         case LastUseKind:
117             RELEASE_ASSERT_NOT_REACHED();
118             break;
119         }
120         RELEASE_ASSERT_NOT_REACHED();
121     }
122     
123     bool result() const { return m_result; }
124     bool maySeeEmptyChild() const { return m_maySeeEmptyChild; }
125 private:
126     AbstractStateType& m_state;
127     bool m_result { true };
128     bool m_maySeeEmptyChild { false };
129 };
130
131 // Determines if it's safe to execute a node within the given abstract state. This may
132 // return false conservatively. If it returns true, then you can hoist the given node
133 // up to the given point and expect that it will not crash. It also guarantees that the
134 // node will not produce a malformed JSValue or object pointer when executed in the
135 // given state. But this doesn't guarantee that the node will produce the result you
136 // wanted. For example, you may have a GetByOffset from a prototype that only makes
137 // semantic sense if you've also checked that some nearer prototype doesn't also have
138 // a property of the same name. This could still return true even if that check hadn't
139 // been performed in the given abstract state. That's fine though: the load can still
140 // safely execute before that check, so long as that check continues to guard any
141 // user-observable things done to the loaded value.
142 template<typename AbstractStateType>
143 bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node, bool ignoreEmptyChildren = false)
144 {
145     SafeToExecuteEdge<AbstractStateType> safeToExecuteEdge(state);
146     DFG_NODE_DO_TO_CHILDREN(graph, node, safeToExecuteEdge);
147     if (!safeToExecuteEdge.result())
148         return false;
149
150     if (!ignoreEmptyChildren && safeToExecuteEdge.maySeeEmptyChild()) {
151         // We conservatively assume if the empty value flows into a node,
152         // it might not be able to handle it (e.g, crash). In general, the bytecode generator
153         // emits code in such a way that most node types don't need to worry about the empty value
154         // because they will never see it. However, code motion has to consider the empty
155         // value so it does not insert/move nodes to a place where they will crash. E.g, the
156         // type check hoisting phase needs to insert CheckStructureOrEmpty instead of CheckStructure
157         // for hoisted structure checks because it can not guarantee that a particular local is not
158         // the empty value.
159         switch (node->op()) {
160         case CheckNotEmpty:
161         case CheckStructureOrEmpty:
162             break;
163         default:
164             return false;
165         }
166     }
167
168     // NOTE: This tends to lie when it comes to effectful nodes, because it knows that they aren't going to
169     // get hoisted anyway.
170
171     switch (node->op()) {
172     case JSConstant:
173     case DoubleConstant:
174     case Int52Constant:
175     case LazyJSConstant:
176     case Identity:
177     case IdentityWithProfile:
178     case ToThis:
179     case CreateThis:
180     case ObjectCreate:
181     case GetCallee:
182     case SetCallee:
183     case GetArgumentCountIncludingThis:
184     case SetArgumentCountIncludingThis:
185     case GetRestLength:
186     case GetLocal:
187     case SetLocal:
188     case PutStack:
189     case KillStack:
190     case GetStack:
191     case MovHint:
192     case ZombieHint:
193     case ExitOK:
194     case Phantom:
195     case Upsilon:
196     case Phi:
197     case Flush:
198     case PhantomLocal:
199     case SetArgument:
200     case BitAnd:
201     case BitOr:
202     case BitXor:
203     case BitLShift:
204     case BitRShift:
205     case BitURShift:
206     case ValueToInt32:
207     case UInt32ToNumber:
208     case DoubleAsInt32:
209     case ArithAdd:
210     case ArithClz32:
211     case ArithSub:
212     case ArithNegate:
213     case ArithMul:
214     case ArithIMul:
215     case ArithDiv:
216     case ArithMod:
217     case ArithAbs:
218     case ArithMin:
219     case ArithMax:
220     case ArithPow:
221     case ArithRandom:
222     case ArithSqrt:
223     case ArithFRound:
224     case ArithRound:
225     case ArithFloor:
226     case ArithCeil:
227     case ArithTrunc:
228     case ArithUnary:
229     case ValueNegate:
230     case ValueAdd:
231     case TryGetById:
232     case DeleteById:
233     case DeleteByVal:
234     case GetById:
235     case GetByIdWithThis:
236     case GetByValWithThis:
237     case GetByIdFlush:
238     case GetByIdDirect:
239     case GetByIdDirectFlush:
240     case PutById:
241     case PutByIdFlush:
242     case PutByIdWithThis:
243     case PutByValWithThis:
244     case PutByIdDirect:
245     case PutGetterById:
246     case PutSetterById:
247     case PutGetterSetterById:
248     case PutGetterByVal:
249     case PutSetterByVal:
250     case DefineDataProperty:
251     case DefineAccessorProperty:
252     case CheckStructure:
253     case CheckStructureOrEmpty:
254     case GetExecutable:
255     case GetButterfly:
256     case CallDOMGetter:
257     case CallDOM:
258     case CheckSubClass:
259     case CheckArray:
260     case Arrayify:
261     case ArrayifyToStructure:
262     case GetScope:
263     case SkipScope:
264     case GetGlobalObject:
265     case GetGlobalThis:
266     case GetClosureVar:
267     case PutClosureVar:
268     case GetGlobalVar:
269     case GetGlobalLexicalVariable:
270     case PutGlobalVariable:
271     case CheckCell:
272     case CheckBadCell:
273     case CheckNotEmpty:
274     case AssertNotEmpty:
275     case CheckStringIdent:
276     case RegExpExec:
277     case RegExpExecNonGlobalOrSticky:
278     case RegExpTest:
279     case RegExpMatchFast:
280     case RegExpMatchFastGlobal:
281     case CompareLess:
282     case CompareLessEq:
283     case CompareGreater:
284     case CompareGreaterEq:
285     case CompareBelow:
286     case CompareBelowEq:
287     case CompareEq:
288     case CompareStrictEq:
289     case CompareEqPtr:
290     case SameValue:
291     case Call:
292     case DirectCall:
293     case TailCallInlinedCaller:
294     case DirectTailCallInlinedCaller:
295     case Construct:
296     case DirectConstruct:
297     case CallVarargs:
298     case CallEval:
299     case TailCallVarargsInlinedCaller:
300     case TailCallForwardVarargsInlinedCaller:
301     case ConstructVarargs:
302     case LoadVarargs:
303     case CallForwardVarargs:
304     case ConstructForwardVarargs:
305     case NewObject:
306     case NewArray:
307     case NewArrayWithSize:
308     case NewArrayBuffer:
309     case NewArrayWithSpread:
310     case Spread:
311     case NewRegexp:
312     case ProfileType:
313     case ProfileControlFlow:
314     case CheckTypeInfoFlags:
315     case ParseInt:
316     case OverridesHasInstance:
317     case InstanceOf:
318     case InstanceOfCustom:
319     case IsEmpty:
320     case IsUndefined:
321     case IsBoolean:
322     case IsNumber:
323     case NumberIsInteger:
324     case IsObject:
325     case IsObjectOrNull:
326     case IsFunction:
327     case IsCellWithType:
328     case IsTypedArrayView:
329     case TypeOf:
330     case LogicalNot:
331     case CallObjectConstructor:
332     case ToPrimitive:
333     case ToString:
334     case ToNumber:
335     case ToObject:
336     case NumberToStringWithRadix:
337     case NumberToStringWithValidRadixConstant:
338     case SetFunctionName:
339     case StrCat:
340     case CallStringConstructor:
341     case NewStringObject:
342     case MakeRope:
343     case InByVal:
344     case InById:
345     case HasOwnProperty:
346     case PushWithScope:
347     case CreateActivation:
348     case CreateDirectArguments:
349     case CreateScopedArguments:
350     case CreateClonedArguments:
351     case GetFromArguments:
352     case GetArgument:
353     case PutToArguments:
354     case NewFunction:
355     case NewGeneratorFunction:
356     case NewAsyncGeneratorFunction:
357     case NewAsyncFunction:
358     case Jump:
359     case Branch:
360     case Switch:
361     case EntrySwitch:
362     case Return:
363     case TailCall:
364     case DirectTailCall:
365     case TailCallVarargs:
366     case TailCallForwardVarargs:
367     case Throw:
368     case ThrowStaticError:
369     case CountExecution:
370     case SuperSamplerBegin:
371     case SuperSamplerEnd:
372     case ForceOSRExit:
373     case CPUIntrinsic:
374     case CheckTraps:
375     case LogShadowChickenPrologue:
376     case LogShadowChickenTail:
377     case StringFromCharCode:
378     case NewTypedArray:
379     case Unreachable:
380     case ExtractOSREntryLocal:
381     case ExtractCatchLocal:
382     case ClearCatchLocals:
383     case CheckTierUpInLoop:
384     case CheckTierUpAtReturn:
385     case CheckTierUpAndOSREnter:
386     case LoopHint:
387     case InvalidationPoint:
388     case NotifyWrite:
389     case CheckInBounds:
390     case ConstantStoragePointer:
391     case Check:
392     case CheckVarargs:
393     case MultiPutByOffset:
394     case ValueRep:
395     case DoubleRep:
396     case Int52Rep:
397     case BooleanToNumber:
398     case FiatInt52:
399     case GetGetter:
400     case GetSetter:
401     case GetEnumerableLength:
402     case HasGenericProperty:
403     case HasStructureProperty:
404     case HasIndexedProperty:
405     case GetDirectPname:
406     case GetPropertyEnumerator:
407     case GetEnumeratorStructurePname:
408     case GetEnumeratorGenericPname:
409     case ToIndexString:
410     case PhantomNewObject:
411     case PhantomNewFunction:
412     case PhantomNewGeneratorFunction:
413     case PhantomNewAsyncGeneratorFunction:
414     case PhantomNewAsyncFunction:
415     case PhantomCreateActivation:
416     case PhantomNewRegexp:
417     case PutHint:
418     case CheckStructureImmediate:
419     case MaterializeNewObject:
420     case MaterializeCreateActivation:
421     case PhantomDirectArguments:
422     case PhantomCreateRest:
423     case PhantomSpread:
424     case PhantomNewArrayWithSpread:
425     case PhantomNewArrayBuffer:
426     case PhantomClonedArguments:
427     case GetMyArgumentByVal:
428     case GetMyArgumentByValOutOfBounds:
429     case ForwardVarargs:
430     case CreateRest:
431     case GetPrototypeOf:
432     case StringReplace:
433     case StringReplaceRegExp:
434     case GetRegExpObjectLastIndex:
435     case SetRegExpObjectLastIndex:
436     case RecordRegExpCachedResult:
437     case GetDynamicVar:
438     case PutDynamicVar:
439     case ResolveScopeForHoistingFuncDeclInEval:
440     case ResolveScope:
441     case MapHash:
442     case NormalizeMapKey:
443     case StringValueOf:
444     case StringSlice:
445     case ToLowerCase:
446     case GetMapBucket:
447     case GetMapBucketHead:
448     case GetMapBucketNext:
449     case LoadKeyFromMapBucket:
450     case LoadValueFromMapBucket:
451     case ExtractValueFromWeakMapGet:
452     case WeakMapGet:
453     case WeakSetAdd:
454     case WeakMapSet:
455     case AtomicsAdd:
456     case AtomicsAnd:
457     case AtomicsCompareExchange:
458     case AtomicsExchange:
459     case AtomicsLoad:
460     case AtomicsOr:
461     case AtomicsStore:
462     case AtomicsSub:
463     case AtomicsXor:
464     case AtomicsIsLockFree:
465     case InitializeEntrypointArguments:
466     case MatchStructure:
467     case DataViewGetInt:
468     case DataViewGetFloat:
469         return true;
470
471     case ArraySlice:
472     case ArrayIndexOf: {
473         // You could plausibly move this code around as long as you proved the
474         // incoming array base structure is an original array at the hoisted location.
475         // Instead of doing that extra work, we just conservatively return false.
476         return false;
477     }
478
479     case BottomValue:
480         // If in doubt, assume that this isn't safe to execute, just because we have no way of
481         // compiling this node.
482         return false;
483
484     case StoreBarrier:
485     case FencedStoreBarrier:
486     case PutStructure:
487     case NukeStructureAndSetButterfly:
488         // We conservatively assume that these cannot be put anywhere, which forces the compiler to
489         // keep them exactly where they were. This is sort of overkill since the clobberize effects
490         // already force these things to be ordered precisely. I'm just not confident enough in my
491         // effect based memory model to rely solely on that right now.
492         return false;
493         
494     case FilterCallLinkStatus:
495     case FilterGetByIdStatus:
496     case FilterPutByIdStatus:
497     case FilterInByIdStatus:
498         // We don't want these to be moved anywhere other than where we put them, since we want them
499         // to capture "profiling" at the point in control flow here the user put them.
500         return false;
501
502     case GetByVal:
503     case GetIndexedPropertyStorage:
504     case GetArrayLength:
505     case GetVectorLength:
506     case ArrayPop:
507     case StringCharAt:
508     case StringCharCodeAt:
509         return node->arrayMode().alreadyChecked(graph, node, state.forNode(graph.child(node, 0)));
510
511     case ArrayPush:
512         return node->arrayMode().alreadyChecked(graph, node, state.forNode(graph.varArgChild(node, 1)));
513
514     case GetTypedArrayByteOffset:
515         return !(state.forNode(node->child1()).m_type & ~(SpecTypedArrayView));
516             
517     case PutByValDirect:
518     case PutByVal:
519     case PutByValAlias:
520         return node->arrayMode().modeForPut().alreadyChecked(
521             graph, node, state.forNode(graph.varArgChild(node, 0)));
522
523     case AllocatePropertyStorage:
524     case ReallocatePropertyStorage:
525         return state.forNode(node->child1()).m_structure.isSubsetOf(
526             RegisteredStructureSet(node->transition()->previous));
527         
528     case GetByOffset:
529     case GetGetterSetterByOffset:
530     case PutByOffset: {
531         StorageAccessData& data = node->storageAccessData();
532         PropertyOffset offset = data.offset;
533         UniquedStringImpl* uid = graph.identifiers()[data.identifierNumber];
534
535         InferredType::Descriptor inferredType;
536         switch (node->op()) {
537         case GetByOffset:
538         case GetGetterSetterByOffset:
539             inferredType = data.inferredType;
540             break;
541         case PutByOffset:
542             // PutByOffset knows about inferred types because it's the enforcer of that type rather
543             // than the consumer of that type. Therefore, PutByOffset expects TOP for the purpose of
544             // safe-to-execute in the sense that it will be happy with anything as general as TOP
545             // (so any type).
546             inferredType = InferredType::Top;
547             break;
548         default:
549             DFG_CRASH(graph, node, "Bad opcode");
550             break;
551         }
552
553         // Graph::isSafeToLoad() is all about proofs derived from PropertyConditions. Those don't
554         // know anything about inferred types. But if we have a proof derived from watching a
555         // structure that has a type proof, then the next case below will deal with it.
556         if (state.structureClobberState() == StructuresAreWatched
557             && inferredType.kind() == InferredType::Top) {
558             if (JSObject* knownBase = node->child1()->dynamicCastConstant<JSObject*>(graph.m_vm)) {
559                 if (graph.isSafeToLoad(knownBase, offset))
560                     return true;
561             }
562         }
563         
564         StructureAbstractValue& value = state.forNode(node->child1()).m_structure;
565         if (value.isInfinite())
566             return false;
567         for (unsigned i = value.size(); i--;) {
568             Structure* thisStructure = value[i].get();
569             if (!thisStructure->isValidOffset(offset))
570                 return false;
571             if (inferredType.kind() != InferredType::Top) {
572                 InferredType::Descriptor thisInferredType =
573                     graph.inferredTypeForProperty(thisStructure, uid);
574                 if (!inferredType.subsumes(thisInferredType))
575                     return false;
576             }
577         }
578         return true;
579     }
580         
581     case MultiGetByOffset: {
582         // We can't always guarantee that the MultiGetByOffset is safe to execute if it
583         // contains loads from prototypes. If the load requires a check in IR, which is rare, then
584         // we currently claim that we don't know if it's safe to execute because finding that
585         // check in the abstract state would be hard. If the load requires watchpoints, we just
586         // check if we're not in a clobbered state (i.e. in between a side effect and an
587         // invalidation point).
588         for (const MultiGetByOffsetCase& getCase : node->multiGetByOffsetData().cases) {
589             GetByOffsetMethod method = getCase.method();
590             switch (method.kind()) {
591             case GetByOffsetMethod::Invalid:
592                 RELEASE_ASSERT_NOT_REACHED();
593                 break;
594             case GetByOffsetMethod::Constant: // OK because constants are always safe to execute.
595             case GetByOffsetMethod::Load: // OK because the MultiGetByOffset has its own checks for loading from self.
596                 break;
597             case GetByOffsetMethod::LoadFromPrototype:
598                 // Only OK if the state isn't clobbered. That's almost always the case.
599                 if (state.structureClobberState() != StructuresAreWatched)
600                     return false;
601                 if (!graph.isSafeToLoad(method.prototype()->cast<JSObject*>(), method.offset()))
602                     return false;
603                 break;
604             }
605         }
606         return true;
607     }
608
609     case DataViewSet:
610         return false;
611
612     case SetAdd:
613     case MapSet:
614         return false;
615
616     case LastNodeType:
617         RELEASE_ASSERT_NOT_REACHED();
618         return false;
619     }
620     
621     RELEASE_ASSERT_NOT_REACHED();
622     return false;
623 }
624
625 } } // namespace JSC::DFG
626
627 #endif // ENABLE(DFG_JIT)