[JSC] Implement optimized WeakMap and WeakSet
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSafeToExecute.h
index a57ed2a..cbfae9f 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -23,8 +23,7 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#ifndef DFGSafeToExecute_h
-#define DFGSafeToExecute_h
+#pragma once
 
 #if ENABLE(DFG_JIT)
 
@@ -37,12 +36,13 @@ class SafeToExecuteEdge {
 public:
     SafeToExecuteEdge(AbstractStateType& state)
         : m_state(state)
-        , m_result(true)
     {
     }
     
     void operator()(Node*, Edge edge)
     {
+        m_maySeeEmptyChild |= !!(m_state.forNode(edge).m_type & SpecEmpty);
+
         switch (edge.useKind()) {
         case UntypedUse:
         case Int32Use:
@@ -50,26 +50,44 @@ public:
         case DoubleRepRealUse:
         case Int52RepUse:
         case NumberUse:
+        case RealNumberUse:
         case BooleanUse:
         case CellUse:
+        case CellOrOtherUse:
         case ObjectUse:
+        case ArrayUse:
         case FunctionUse:
         case FinalObjectUse:
+        case RegExpObjectUse:
+        case ProxyObjectUse:
+        case DerivedArrayUse:
+        case MapObjectUse:
+        case SetObjectUse:
+        case WeakMapObjectUse:
+        case WeakSetObjectUse:
         case ObjectOrOtherUse:
         case StringIdentUse:
         case StringUse:
+        case StringOrOtherUse:
+        case SymbolUse:
         case StringObjectUse:
         case StringOrStringObjectUse:
         case NotStringVarUse:
+        case NotSymbolUse:
         case NotCellUse:
         case OtherUse:
         case MiscUse:
-        case MachineIntUse:
-        case DoubleRepMachineIntUse:
+        case AnyIntUse:
+        case DoubleRepAnyIntUse:
             return;
             
         case KnownInt32Use:
-            if (m_state.forNode(edge).m_type & ~SpecInt32)
+            if (m_state.forNode(edge).m_type & ~SpecInt32Only)
+                m_result = false;
+            return;
+
+        case KnownBooleanUse:
+            if (m_state.forNode(edge).m_type & ~SpecBoolean)
                 m_result = false;
             return;
             
@@ -82,6 +100,11 @@ public:
             if (m_state.forNode(edge).m_type & ~SpecString)
                 m_result = false;
             return;
+
+        case KnownPrimitiveUse:
+            if (m_state.forNode(edge).m_type & ~(SpecHeapTop & ~SpecObject))
+                m_result = false;
+            return;
             
         case LastUseKind:
             RELEASE_ASSERT_NOT_REACHED();
@@ -91,15 +114,24 @@ public:
     }
     
     bool result() const { return m_result; }
+    bool maySeeEmptyChild() const { return m_maySeeEmptyChild; }
 private:
     AbstractStateType& m_state;
-    bool m_result;
+    bool m_result { true };
+    bool m_maySeeEmptyChild { false };
 };
 
 // Determines if it's safe to execute a node within the given abstract state. This may
 // return false conservatively. If it returns true, then you can hoist the given node
-// up to the given point and expect that it will not crash. This doesn't guarantee that
-// the node will produce the result you wanted other than not crashing.
+// up to the given point and expect that it will not crash. It also guarantees that the
+// node will not produce a malformed JSValue or object pointer when executed in the
+// given state. But this doesn't guarantee that the node will produce the result you
+// wanted. For example, you may have a GetByOffset from a prototype that only makes
+// semantic sense if you've also checked that some nearer prototype doesn't also have
+// a property of the same name. This could still return true even if that check hadn't
+// been performed in the given abstract state. That's fine though: the load can still
+// safely execute before that check, so long as that check continues to guard any
+// user-observable things done to the loaded value.
 template<typename AbstractStateType>
 bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
 {
@@ -108,15 +140,39 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     if (!safeToExecuteEdge.result())
         return false;
 
+    if (safeToExecuteEdge.maySeeEmptyChild()) {
+        // We conservatively assume if the empty value flows into a node,
+        // it might not be able to handle it (e.g, crash). In general, the bytecode generator
+        // emits code in such a way that most node types don't need to worry about the empty value
+        // because they will never see it. However, code motion has to consider the empty
+        // value so it does not insert/move nodes to a place where they will crash. E.g, the
+        // type check hoisting phase needs to insert CheckStructureOrEmpty instead of CheckStructure
+        // for hoisted structure checks because it can not guarantee that a particular local is not
+        // the empty value.
+        switch (node->op()) {
+        case CheckNotEmpty:
+        case CheckStructureOrEmpty:
+            break;
+        default:
+            return false;
+        }
+    }
+
+    // NOTE: This tends to lie when it comes to effectful nodes, because it knows that they aren't going to
+    // get hoisted anyway.
+
     switch (node->op()) {
     case JSConstant:
     case DoubleConstant:
     case Int52Constant:
+    case LazyJSConstant:
     case Identity:
+    case IdentityWithProfile:
     case ToThis:
     case CreateThis:
     case GetCallee:
-    case GetArgumentCount:
+    case GetArgumentCountIncludingThis:
+    case GetRestLength:
     case GetLocal:
     case SetLocal:
     case PutStack:
@@ -124,12 +180,12 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case GetStack:
     case MovHint:
     case ZombieHint:
+    case ExitOK:
     case Phantom:
     case Upsilon:
     case Phi:
     case Flush:
     case PhantomLocal:
-    case GetLocalUnlinked:
     case SetArgument:
     case BitAnd:
     case BitOr:
@@ -152,46 +208,78 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case ArithMin:
     case ArithMax:
     case ArithPow:
+    case ArithRandom:
     case ArithSqrt:
     case ArithFRound:
     case ArithRound:
-    case ArithSin:
-    case ArithCos:
-    case ArithLog:
+    case ArithFloor:
+    case ArithCeil:
+    case ArithTrunc:
+    case ArithUnary:
     case ValueAdd:
+    case TryGetById:
+    case DeleteById:
+    case DeleteByVal:
     case GetById:
+    case GetByIdWithThis:
+    case GetByValWithThis:
     case GetByIdFlush:
     case PutById:
     case PutByIdFlush:
+    case PutByIdWithThis:
+    case PutByValWithThis:
     case PutByIdDirect:
+    case PutGetterById:
+    case PutSetterById:
+    case PutGetterSetterById:
+    case PutGetterByVal:
+    case PutSetterByVal:
+    case DefineDataProperty:
+    case DefineAccessorProperty:
     case CheckStructure:
+    case CheckStructureOrEmpty:
     case GetExecutable:
     case GetButterfly:
+    case CallDOMGetter:
+    case CallDOM:
+    case CheckSubClass:
     case CheckArray:
     case Arrayify:
     case ArrayifyToStructure:
     case GetScope:
     case SkipScope:
+    case GetGlobalObject:
+    case GetGlobalThis:
     case GetClosureVar:
     case PutClosureVar:
     case GetGlobalVar:
-    case PutGlobalVar:
-    case VarInjectionWatchpoint:
+    case GetGlobalLexicalVariable:
+    case PutGlobalVariable:
     case CheckCell:
     case CheckBadCell:
     case CheckNotEmpty:
+    case CheckStringIdent:
     case RegExpExec:
     case RegExpTest:
     case CompareLess:
     case CompareLessEq:
     case CompareGreater:
     case CompareGreaterEq:
+    case CompareBelow:
+    case CompareBelowEq:
     case CompareEq:
-    case CompareEqConstant:
     case CompareStrictEq:
+    case CompareEqPtr:
     case Call:
+    case DirectCall:
+    case TailCallInlinedCaller:
+    case DirectTailCallInlinedCaller:
     case Construct:
+    case DirectConstruct:
     case CallVarargs:
+    case CallEval:
+    case TailCallVarargsInlinedCaller:
+    case TailCallForwardVarargsInlinedCaller:
     case ConstructVarargs:
     case LoadVarargs:
     case CallForwardVarargs:
@@ -200,61 +288,86 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case NewArray:
     case NewArrayWithSize:
     case NewArrayBuffer:
+    case NewArrayWithSpread:
+    case Spread:
     case NewRegexp:
-    case Breakpoint:
-    case ProfileWillCall:
-    case ProfileDidCall:
     case ProfileType:
     case ProfileControlFlow:
-    case CheckHasInstance:
+    case CheckTypeInfoFlags:
+    case ParseInt:
+    case OverridesHasInstance:
     case InstanceOf:
+    case InstanceOfCustom:
+    case IsEmpty:
     case IsUndefined:
     case IsBoolean:
     case IsNumber:
-    case IsString:
     case IsObject:
     case IsObjectOrNull:
     case IsFunction:
+    case IsCellWithType:
+    case IsTypedArrayView:
     case TypeOf:
     case LogicalNot:
+    case CallObjectConstructor:
     case ToPrimitive:
     case ToString:
+    case ToNumber:
+    case ToObject:
+    case NumberToStringWithRadix:
+    case NumberToStringWithValidRadixConstant:
+    case SetFunctionName:
+    case StrCat:
     case CallStringConstructor:
     case NewStringObject:
     case MakeRope:
     case In:
+    case HasOwnProperty:
+    case PushWithScope:
     case CreateActivation:
     case CreateDirectArguments:
     case CreateScopedArguments:
     case CreateClonedArguments:
     case GetFromArguments:
+    case GetArgument:
     case PutToArguments:
     case NewFunction:
+    case NewGeneratorFunction:
+    case NewAsyncGeneratorFunction:
+    case NewAsyncFunction:
     case Jump:
     case Branch:
     case Switch:
+    case EntrySwitch:
     case Return:
+    case TailCall:
+    case DirectTailCall:
+    case TailCallVarargs:
+    case TailCallForwardVarargs:
     case Throw:
-    case ThrowReferenceError:
+    case ThrowStaticError:
     case CountExecution:
+    case SuperSamplerBegin:
+    case SuperSamplerEnd:
     case ForceOSRExit:
-    case CheckWatchdogTimer:
+    case CPUIntrinsic:
+    case CheckTraps:
+    case LogShadowChickenPrologue:
+    case LogShadowChickenTail:
     case StringFromCharCode:
     case NewTypedArray:
     case Unreachable:
     case ExtractOSREntryLocal:
+    case ExtractCatchLocal:
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
     case CheckTierUpAndOSREnter:
-    case CheckTierUpWithNestedTriggerAndOSREnter:
     case LoopHint:
-    case StoreBarrier:
     case InvalidationPoint:
     case NotifyWrite:
     case CheckInBounds:
     case ConstantStoragePointer:
     case Check:
-    case MultiGetByOffset:
     case MultiPutByOffset:
     case ValueRep:
     case DoubleRep:
@@ -274,35 +387,92 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case ToIndexString:
     case PhantomNewObject:
     case PhantomNewFunction:
+    case PhantomNewGeneratorFunction:
+    case PhantomNewAsyncGeneratorFunction:
+    case PhantomNewAsyncFunction:
     case PhantomCreateActivation:
     case PutHint:
     case CheckStructureImmediate:
     case MaterializeNewObject:
     case MaterializeCreateActivation:
     case PhantomDirectArguments:
+    case PhantomCreateRest:
+    case PhantomSpread:
+    case PhantomNewArrayWithSpread:
     case PhantomClonedArguments:
     case GetMyArgumentByVal:
+    case GetMyArgumentByValOutOfBounds:
     case ForwardVarargs:
+    case CreateRest:
+    case GetPrototypeOf:
+    case StringReplace:
+    case StringReplaceRegExp:
+    case GetRegExpObjectLastIndex:
+    case SetRegExpObjectLastIndex:
+    case RecordRegExpCachedResult:
+    case GetDynamicVar:
+    case PutDynamicVar:
+    case ResolveScopeForHoistingFuncDeclInEval:
+    case ResolveScope:
+    case MapHash:
+    case NormalizeMapKey:
+    case StringSlice:
+    case ToLowerCase:
+    case GetMapBucket:
+    case GetMapBucketHead:
+    case GetMapBucketNext:
+    case LoadKeyFromMapBucket:
+    case LoadValueFromMapBucket:
+    case ExtractValueFromWeakMapGet:
+    case WeakMapGet:
+    case AtomicsAdd:
+    case AtomicsAnd:
+    case AtomicsCompareExchange:
+    case AtomicsExchange:
+    case AtomicsLoad:
+    case AtomicsOr:
+    case AtomicsStore:
+    case AtomicsSub:
+    case AtomicsXor:
+    case AtomicsIsLockFree:
+    case InitializeEntrypointArguments:
         return true;
 
-    case NativeCall:
-    case NativeConstruct:
-        return false; // TODO: add a check for already checked.  https://bugs.webkit.org/show_bug.cgi?id=133769
+    case ArraySlice:
+    case ArrayIndexOf: {
+        // You could plausibly move this code around as long as you proved the
+        // incoming array base structure is an original array at the hoisted location.
+        // Instead of doing that extra work, we just conservatively return false.
+        return false;
+    }
 
     case BottomValue:
         // If in doubt, assume that this isn't safe to execute, just because we have no way of
         // compiling this node.
         return false;
 
+    case StoreBarrier:
+    case FencedStoreBarrier:
+    case PutStructure:
+    case NukeStructureAndSetButterfly:
+        // We conservatively assume that these cannot be put anywhere, which forces the compiler to
+        // keep them exactly where they were. This is sort of overkill since the clobberize effects
+        // already force these things to be ordered precisely. I'm just not confident enough in my
+        // effect based memory model to rely solely on that right now.
+        return false;
+
     case GetByVal:
     case GetIndexedPropertyStorage:
     case GetArrayLength:
-    case ArrayPush:
+    case GetVectorLength:
     case ArrayPop:
     case StringCharAt:
     case StringCharCodeAt:
         return node->arrayMode().alreadyChecked(graph, node, state.forNode(node->child1()));
-        
+
+    case ArrayPush:
+        return node->arrayMode().alreadyChecked(graph, node, state.forNode(graph.varArgChild(node, 1)));
+
     case GetTypedArrayByteOffset:
         return !(state.forNode(node->child1()).m_type & ~(SpecTypedArrayView));
             
@@ -312,19 +482,26 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
         return node->arrayMode().modeForPut().alreadyChecked(
             graph, node, state.forNode(graph.varArgChild(node, 0)));
 
-    case PutStructure:
     case AllocatePropertyStorage:
     case ReallocatePropertyStorage:
         return state.forNode(node->child1()).m_structure.isSubsetOf(
-            StructureSet(node->transition()->previous));
+            RegisteredStructureSet(node->transition()->previous));
         
     case GetByOffset:
     case GetGetterSetterByOffset:
     case PutByOffset: {
+        PropertyOffset offset = node->storageAccessData().offset;
+
+        if (state.structureClobberState() == StructuresAreWatched) {
+            if (JSObject* knownBase = node->child1()->dynamicCastConstant<JSObject*>(graph.m_vm)) {
+                if (graph.isSafeToLoad(knownBase, offset))
+                    return true;
+            }
+        }
+        
         StructureAbstractValue& value = state.forNode(node->child1()).m_structure;
-        if (value.isTop())
+        if (value.isInfinite())
             return false;
-        PropertyOffset offset = node->storageAccessData().offset;
         for (unsigned i = value.size(); i--;) {
             if (!value[i]->isValidOffset(offset))
                 return false;
@@ -332,6 +509,38 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
         return true;
     }
         
+    case MultiGetByOffset: {
+        // We can't always guarantee that the MultiGetByOffset is safe to execute if it
+        // contains loads from prototypes. If the load requires a check in IR, which is rare, then
+        // we currently claim that we don't know if it's safe to execute because finding that
+        // check in the abstract state would be hard. If the load requires watchpoints, we just
+        // check if we're not in a clobbered state (i.e. in between a side effect and an
+        // invalidation point).
+        for (const MultiGetByOffsetCase& getCase : node->multiGetByOffsetData().cases) {
+            GetByOffsetMethod method = getCase.method();
+            switch (method.kind()) {
+            case GetByOffsetMethod::Invalid:
+                RELEASE_ASSERT_NOT_REACHED();
+                break;
+            case GetByOffsetMethod::Constant: // OK because constants are always safe to execute.
+            case GetByOffsetMethod::Load: // OK because the MultiGetByOffset has its own checks for loading from self.
+                break;
+            case GetByOffsetMethod::LoadFromPrototype:
+                // Only OK if the state isn't clobbered. That's almost always the case.
+                if (state.structureClobberState() != StructuresAreWatched)
+                    return false;
+                if (!graph.isSafeToLoad(method.prototype()->cast<JSObject*>(), method.offset()))
+                    return false;
+                break;
+            }
+        }
+        return true;
+    }
+
+    case SetAdd:
+    case MapSet:
+        return false;
+
     case LastNodeType:
         RELEASE_ASSERT_NOT_REACHED();
         return false;
@@ -344,6 +553,3 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
-
-#endif // DFGSafeToExecute_h
-