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