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
32namespace JSC { namespace DFG {
33
34template<typename AbstractStateType>
35class SafeToExecuteEdge {
36public:
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; }
127private:
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.
144template<typename AbstractStateType>
145bool 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 Inc:
244 case Dec:
245 case ValueNegate:
246 case ValueAdd:
247 case ValueSub:
248 case ValueMul:
249 case ValueDiv:
250 case ValueMod:
251 case ValuePow:
252 case TryGetById:
253 case DeleteById:
254 case DeleteByVal:
255 case GetById:
256 case GetByIdWithThis:
257 case GetByValWithThis:
258 case GetByIdFlush:
259 case GetByIdDirect:
260 case GetByIdDirectFlush:
261 case PutById:
262 case PutByIdFlush:
263 case PutByIdWithThis:
264 case PutByValWithThis:
265 case PutByIdDirect:
266 case PutGetterById:
267 case PutSetterById:
268 case PutGetterSetterById:
269 case PutGetterByVal:
270 case PutSetterByVal:
271 case DefineDataProperty:
272 case DefineAccessorProperty:
273 case CheckStructure:
274 case CheckStructureOrEmpty:
275 case GetExecutable:
276 case GetButterfly:
277 case CallDOMGetter:
278 case CallDOM:
279 case CheckSubClass:
280 case CheckArray:
281 case Arrayify:
282 case ArrayifyToStructure:
283 case GetScope:
284 case SkipScope:
285 case GetGlobalObject:
286 case GetGlobalThis:
287 case GetClosureVar:
288 case PutClosureVar:
289 case GetGlobalVar:
290 case GetGlobalLexicalVariable:
291 case PutGlobalVariable:
292 case GetInternalField:
293 case PutInternalField:
294 case CheckCell:
295 case CheckBadCell:
296 case CheckNotEmpty:
297 case AssertNotEmpty:
298 case CheckIdent:
299 case RegExpExec:
300 case RegExpExecNonGlobalOrSticky:
301 case RegExpTest:
302 case RegExpMatchFast:
303 case RegExpMatchFastGlobal:
304 case CompareLess:
305 case CompareLessEq:
306 case CompareGreater:
307 case CompareGreaterEq:
308 case CompareBelow:
309 case CompareBelowEq:
310 case CompareEq:
311 case CompareStrictEq:
312 case CompareEqPtr:
313 case SameValue:
314 case Call:
315 case DirectCall:
316 case TailCallInlinedCaller:
317 case DirectTailCallInlinedCaller:
318 case Construct:
319 case DirectConstruct:
320 case CallVarargs:
321 case CallEval:
322 case TailCallVarargsInlinedCaller:
323 case TailCallForwardVarargsInlinedCaller:
324 case ConstructVarargs:
325 case LoadVarargs:
326 case CallForwardVarargs:
327 case ConstructForwardVarargs:
328 case NewObject:
329 case NewPromise:
330 case NewGenerator:
331 case NewAsyncGenerator:
332 case NewArray:
333 case NewArrayWithSize:
334 case NewArrayBuffer:
335 case NewArrayWithSpread:
336 case Spread:
337 case NewRegexp:
338 case NewSymbol:
339 case ProfileType:
340 case ProfileControlFlow:
341 case CheckTypeInfoFlags:
342 case ParseInt:
343 case OverridesHasInstance:
344 case InstanceOf:
345 case InstanceOfCustom:
346 case IsEmpty:
347 case IsUndefined:
348 case IsUndefinedOrNull:
349 case IsBoolean:
350 case IsNumber:
351 case NumberIsInteger:
352 case IsObject:
353 case IsObjectOrNull:
354 case IsFunction:
355 case IsCellWithType:
356 case IsTypedArrayView:
357 case TypeOf:
358 case LogicalNot:
359 case CallObjectConstructor:
360 case ToPrimitive:
361 case ToString:
362 case ToNumber:
363 case ToNumeric:
364 case ToObject:
365 case NumberToStringWithRadix:
366 case NumberToStringWithValidRadixConstant:
367 case SetFunctionName:
368 case StrCat:
369 case CallStringConstructor:
370 case NewStringObject:
371 case MakeRope:
372 case InByVal:
373 case InById:
374 case HasOwnProperty:
375 case PushWithScope:
376 case CreateActivation:
377 case CreateDirectArguments:
378 case CreateScopedArguments:
379 case CreateClonedArguments:
380 case GetFromArguments:
381 case GetArgument:
382 case PutToArguments:
383 case NewFunction:
384 case NewGeneratorFunction:
385 case NewAsyncGeneratorFunction:
386 case NewAsyncFunction:
387 case Jump:
388 case Branch:
389 case Switch:
390 case EntrySwitch:
391 case Return:
392 case TailCall:
393 case DirectTailCall:
394 case TailCallVarargs:
395 case TailCallForwardVarargs:
396 case Throw:
397 case ThrowStaticError:
398 case CountExecution:
399 case SuperSamplerBegin:
400 case SuperSamplerEnd:
401 case ForceOSRExit:
402 case CPUIntrinsic:
403 case CheckTraps:
404 case LogShadowChickenPrologue:
405 case LogShadowChickenTail:
406 case StringFromCharCode:
407 case NewTypedArray:
408 case Unreachable:
409 case ExtractOSREntryLocal:
410 case ExtractCatchLocal:
411 case ClearCatchLocals:
412 case CheckTierUpInLoop:
413 case CheckTierUpAtReturn:
414 case CheckTierUpAndOSREnter:
415 case LoopHint:
416 case InvalidationPoint:
417 case NotifyWrite:
418 case CheckInBounds:
419 case ConstantStoragePointer:
420 case Check:
421 case CheckVarargs:
422 case MultiPutByOffset:
423 case ValueRep:
424 case DoubleRep:
425 case Int52Rep:
426 case BooleanToNumber:
427 case FiatInt52:
428 case GetGetter:
429 case GetSetter:
430 case GetEnumerableLength:
431 case HasGenericProperty:
432 case HasStructureProperty:
433 case HasIndexedProperty:
434 case GetDirectPname:
435 case GetPropertyEnumerator:
436 case GetEnumeratorStructurePname:
437 case GetEnumeratorGenericPname:
438 case ToIndexString:
439 case PhantomNewObject:
440 case PhantomNewFunction:
441 case PhantomNewGeneratorFunction:
442 case PhantomNewAsyncGeneratorFunction:
443 case PhantomNewAsyncFunction:
444 case PhantomCreateActivation:
445 case PhantomNewRegexp:
446 case PutHint:
447 case CheckStructureImmediate:
448 case MaterializeNewObject:
449 case MaterializeCreateActivation:
450 case PhantomDirectArguments:
451 case PhantomCreateRest:
452 case PhantomSpread:
453 case PhantomNewArrayWithSpread:
454 case PhantomNewArrayBuffer:
455 case PhantomClonedArguments:
456 case GetMyArgumentByVal:
457 case GetMyArgumentByValOutOfBounds:
458 case ForwardVarargs:
459 case CreateRest:
460 case GetPrototypeOf:
461 case StringReplace:
462 case StringReplaceRegExp:
463 case GetRegExpObjectLastIndex:
464 case SetRegExpObjectLastIndex:
465 case RecordRegExpCachedResult:
466 case GetDynamicVar:
467 case PutDynamicVar:
468 case ResolveScopeForHoistingFuncDeclInEval:
469 case ResolveScope:
470 case MapHash:
471 case NormalizeMapKey:
472 case StringValueOf:
473 case StringSlice:
474 case ToLowerCase:
475 case GetMapBucket:
476 case GetMapBucketHead:
477 case GetMapBucketNext:
478 case LoadKeyFromMapBucket:
479 case LoadValueFromMapBucket:
480 case ExtractValueFromWeakMapGet:
481 case WeakMapGet:
482 case WeakSetAdd:
483 case WeakMapSet:
484 case AtomicsAdd:
485 case AtomicsAnd:
486 case AtomicsCompareExchange:
487 case AtomicsExchange:
488 case AtomicsLoad:
489 case AtomicsOr:
490 case AtomicsStore:
491 case AtomicsSub:
492 case AtomicsXor:
493 case AtomicsIsLockFree:
494 case InitializeEntrypointArguments:
495 case MatchStructure:
496 case DateGetInt32OrNaN:
497 case DateGetTime:
498 case DataViewGetInt:
499 case DataViewGetFloat:
500 return true;
501
502 case ArraySlice:
503 case ArrayIndexOf: {
504 // You could plausibly move this code around as long as you proved the
505 // incoming array base structure is an original array at the hoisted location.
506 // Instead of doing that extra work, we just conservatively return false.
507 return false;
508 }
509
510 case BottomValue:
511 // If in doubt, assume that this isn't safe to execute, just because we have no way of
512 // compiling this node.
513 return false;
514
515 case StoreBarrier:
516 case FencedStoreBarrier:
517 case PutStructure:
518 case NukeStructureAndSetButterfly:
519 // We conservatively assume that these cannot be put anywhere, which forces the compiler to
520 // keep them exactly where they were. This is sort of overkill since the clobberize effects
521 // already force these things to be ordered precisely. I'm just not confident enough in my
522 // effect based memory model to rely solely on that right now.
523 return false;
524
525 case FilterCallLinkStatus:
526 case FilterGetByStatus:
527 case FilterPutByIdStatus:
528 case FilterInByIdStatus:
529 // We don't want these to be moved anywhere other than where we put them, since we want them
530 // to capture "profiling" at the point in control flow here the user put them.
531 return false;
532
533 case GetByVal:
534 case GetIndexedPropertyStorage:
535 case GetArrayLength:
536 case GetVectorLength:
537 case ArrayPop:
538 case StringCharAt:
539 case StringCharCodeAt:
540 case StringCodePointAt:
541 return node->arrayMode().alreadyChecked(graph, node, state.forNode(graph.child(node, 0)));
542
543 case ArrayPush:
544 return node->arrayMode().alreadyChecked(graph, node, state.forNode(graph.varArgChild(node, 1)));
545
546 case GetTypedArrayByteOffset:
547 return !(state.forNode(node->child1()).m_type & ~(SpecTypedArrayView));
548
549 case PutByValDirect:
550 case PutByVal:
551 case PutByValAlias:
552 return node->arrayMode().modeForPut().alreadyChecked(
553 graph, node, state.forNode(graph.varArgChild(node, 0)));
554
555 case AllocatePropertyStorage:
556 case ReallocatePropertyStorage:
557 return state.forNode(node->child1()).m_structure.isSubsetOf(
558 RegisteredStructureSet(node->transition()->previous));
559
560 case GetByOffset:
561 case GetGetterSetterByOffset:
562 case PutByOffset: {
563 StorageAccessData& data = node->storageAccessData();
564 PropertyOffset offset = data.offset;
565 // Graph::isSafeToLoad() is all about proofs derived from PropertyConditions. Those don't
566 // know anything about inferred types. But if we have a proof derived from watching a
567 // structure that has a type proof, then the next case below will deal with it.
568 if (state.structureClobberState() == StructuresAreWatched) {
569 if (JSObject* knownBase = node->child2()->dynamicCastConstant<JSObject*>(graph.m_vm)) {
570 if (graph.isSafeToLoad(knownBase, offset))
571 return true;
572 }
573 }
574
575 StructureAbstractValue& value = state.forNode(node->child2()).m_structure;
576 if (value.isInfinite())
577 return false;
578 for (unsigned i = value.size(); i--;) {
579 Structure* thisStructure = value[i].get();
580 if (!thisStructure->isValidOffset(offset))
581 return false;
582 }
583 return true;
584 }
585
586 case MultiGetByOffset: {
587 // We can't always guarantee that the MultiGetByOffset is safe to execute if it
588 // contains loads from prototypes. If the load requires a check in IR, which is rare, then
589 // we currently claim that we don't know if it's safe to execute because finding that
590 // check in the abstract state would be hard. If the load requires watchpoints, we just
591 // check if we're not in a clobbered state (i.e. in between a side effect and an
592 // invalidation point).
593 for (const MultiGetByOffsetCase& getCase : node->multiGetByOffsetData().cases) {
594 GetByOffsetMethod method = getCase.method();
595 switch (method.kind()) {
596 case GetByOffsetMethod::Invalid:
597 RELEASE_ASSERT_NOT_REACHED();
598 break;
599 case GetByOffsetMethod::Constant: // OK because constants are always safe to execute.
600 case GetByOffsetMethod::Load: // OK because the MultiGetByOffset has its own checks for loading from self.
601 break;
602 case GetByOffsetMethod::LoadFromPrototype:
603 // Only OK if the state isn't clobbered. That's almost always the case.
604 if (state.structureClobberState() != StructuresAreWatched)
605 return false;
606 if (!graph.isSafeToLoad(method.prototype()->cast<JSObject*>(), method.offset()))
607 return false;
608 break;
609 }
610 }
611 return true;
612 }
613
614 case DataViewSet:
615 return false;
616
617 case SetAdd:
618 case MapSet:
619 return false;
620
621 case LastNodeType:
622 RELEASE_ASSERT_NOT_REACHED();
623 return false;
624 }
625
626 RELEASE_ASSERT_NOT_REACHED();
627 return false;
628}
629
630} } // namespace JSC::DFG
631
632#endif // ENABLE(DFG_JIT)
633