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