DFG should inline InstanceOf ICs
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 19 May 2018 22:00:21 +0000 (22:00 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 19 May 2018 22:00:21 +0000 (22:00 +0000)
https://bugs.webkit.org/show_bug.cgi?id=185695

Reviewed by Yusuke Suzuki.

Source/JavaScriptCore:

This teaches the DFG how to inline InstanceOf ICs into a MatchStructure node. This can then
be folded to a CheckStructure + JSConstant.

In the process of testing this, I found a bug where LICM was not hoisting things that
depended on ExtraOSREntryLocal because that might return SpecEmpty. I fixed that by teaching
LICM how to materialize CheckNotEmpty on demand whenever !HoistingFailed.

This is a ~5% speed-up on boyer.

~2x speed-up on the instanceof-always-hit-one, instanceof-always-hit-two, and
instanceof-sometimes-hit microbenchmarks.

* JavaScriptCore.xcodeproj/project.pbxproj:
* Sources.txt:
* bytecode/GetByIdStatus.cpp:
(JSC::GetByIdStatus::appendVariant):
(JSC::GetByIdStatus::filter):
* bytecode/GetByIdStatus.h:
(JSC::GetByIdStatus::operator bool const):
(JSC::GetByIdStatus::operator! const): Deleted.
* bytecode/GetByIdVariant.h:
(JSC::GetByIdVariant::operator bool const):
(JSC::GetByIdVariant::operator! const): Deleted.
* bytecode/ICStatusUtils.h: Added.
(JSC::appendICStatusVariant):
(JSC::filterICStatusVariants):
* bytecode/InstanceOfStatus.cpp: Added.
(JSC::InstanceOfStatus::appendVariant):
(JSC::InstanceOfStatus::computeFor):
(JSC::InstanceOfStatus::computeForStubInfo):
(JSC::InstanceOfStatus::commonPrototype const):
(JSC::InstanceOfStatus::filter):
* bytecode/InstanceOfStatus.h: Added.
(JSC::InstanceOfStatus::InstanceOfStatus):
(JSC::InstanceOfStatus::state const):
(JSC::InstanceOfStatus::isSet const):
(JSC::InstanceOfStatus::operator bool const):
(JSC::InstanceOfStatus::isSimple const):
(JSC::InstanceOfStatus::takesSlowPath const):
(JSC::InstanceOfStatus::numVariants const):
(JSC::InstanceOfStatus::variants const):
(JSC::InstanceOfStatus::at const):
(JSC::InstanceOfStatus::operator[] const):
* bytecode/InstanceOfVariant.cpp: Added.
(JSC::InstanceOfVariant::InstanceOfVariant):
(JSC::InstanceOfVariant::attemptToMerge):
(JSC::InstanceOfVariant::dump const):
(JSC::InstanceOfVariant::dumpInContext const):
* bytecode/InstanceOfVariant.h: Added.
(JSC::InstanceOfVariant::InstanceOfVariant):
(JSC::InstanceOfVariant::operator bool const):
(JSC::InstanceOfVariant::structureSet const):
(JSC::InstanceOfVariant::structureSet):
(JSC::InstanceOfVariant::conditionSet const):
(JSC::InstanceOfVariant::prototype const):
(JSC::InstanceOfVariant::isHit const):
* bytecode/StructureStubInfo.cpp:
(JSC::StructureStubInfo::StructureStubInfo):
* bytecode/StructureStubInfo.h:
(JSC::StructureStubInfo::considerCaching):
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::parseBlock):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGConstantFoldingPhase.cpp:
(JSC::DFG::ConstantFoldingPhase::foldConstants):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
* dfg/DFGGraph.h:
* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::attemptHoist):
* dfg/DFGNode.cpp:
(JSC::DFG::Node::remove):
* dfg/DFGNode.h:
(JSC::DFG::Node::hasMatchStructureData):
(JSC::DFG::Node::matchStructureData):
* dfg/DFGNodeType.h:
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileMatchStructure):
* dfg/DFGSpeculativeJIT.h:
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileMatchStructure):

Source/WTF:

I found myself needing a way to represent bottom/false/true/top, so I created it.

* WTF.xcodeproj/project.pbxproj:
* wtf/BooleanLattice.h: Added.
(WTF::lubBooleanLattice):
(WTF::printInternal):
* wtf/CMakeLists.txt:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@232000 268f45cc-cd09-0410-ab3c-d52691b4dbfc

37 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/Sources.txt
Source/JavaScriptCore/bytecode/GetByIdStatus.cpp
Source/JavaScriptCore/bytecode/GetByIdStatus.h
Source/JavaScriptCore/bytecode/GetByIdVariant.h
Source/JavaScriptCore/bytecode/ICStatusUtils.h [new file with mode: 0644]
Source/JavaScriptCore/bytecode/InstanceOfStatus.cpp [new file with mode: 0644]
Source/JavaScriptCore/bytecode/InstanceOfStatus.h [new file with mode: 0644]
Source/JavaScriptCore/bytecode/InstanceOfVariant.cpp [new file with mode: 0644]
Source/JavaScriptCore/bytecode/InstanceOfVariant.h [new file with mode: 0644]
Source/JavaScriptCore/bytecode/StructureStubInfo.cpp
Source/JavaScriptCore/bytecode/StructureStubInfo.h
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
Source/JavaScriptCore/dfg/DFGDoesGC.cpp
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
Source/JavaScriptCore/dfg/DFGNode.cpp
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGSafeToExecute.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/ftl/FTLCapabilities.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/BooleanLattice.h [new file with mode: 0644]
Source/WTF/wtf/CMakeLists.txt

index 02fb647..8228176 100644 (file)
@@ -1,3 +1,108 @@
+2018-05-18  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should inline InstanceOf ICs
+        https://bugs.webkit.org/show_bug.cgi?id=185695
+
+        Reviewed by Yusuke Suzuki.
+        
+        This teaches the DFG how to inline InstanceOf ICs into a MatchStructure node. This can then
+        be folded to a CheckStructure + JSConstant.
+        
+        In the process of testing this, I found a bug where LICM was not hoisting things that
+        depended on ExtraOSREntryLocal because that might return SpecEmpty. I fixed that by teaching
+        LICM how to materialize CheckNotEmpty on demand whenever !HoistingFailed.
+        
+        This is a ~5% speed-up on boyer.
+        
+        ~2x speed-up on the instanceof-always-hit-one, instanceof-always-hit-two, and
+        instanceof-sometimes-hit microbenchmarks.
+
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * Sources.txt:
+        * bytecode/GetByIdStatus.cpp:
+        (JSC::GetByIdStatus::appendVariant):
+        (JSC::GetByIdStatus::filter):
+        * bytecode/GetByIdStatus.h:
+        (JSC::GetByIdStatus::operator bool const):
+        (JSC::GetByIdStatus::operator! const): Deleted.
+        * bytecode/GetByIdVariant.h:
+        (JSC::GetByIdVariant::operator bool const):
+        (JSC::GetByIdVariant::operator! const): Deleted.
+        * bytecode/ICStatusUtils.h: Added.
+        (JSC::appendICStatusVariant):
+        (JSC::filterICStatusVariants):
+        * bytecode/InstanceOfStatus.cpp: Added.
+        (JSC::InstanceOfStatus::appendVariant):
+        (JSC::InstanceOfStatus::computeFor):
+        (JSC::InstanceOfStatus::computeForStubInfo):
+        (JSC::InstanceOfStatus::commonPrototype const):
+        (JSC::InstanceOfStatus::filter):
+        * bytecode/InstanceOfStatus.h: Added.
+        (JSC::InstanceOfStatus::InstanceOfStatus):
+        (JSC::InstanceOfStatus::state const):
+        (JSC::InstanceOfStatus::isSet const):
+        (JSC::InstanceOfStatus::operator bool const):
+        (JSC::InstanceOfStatus::isSimple const):
+        (JSC::InstanceOfStatus::takesSlowPath const):
+        (JSC::InstanceOfStatus::numVariants const):
+        (JSC::InstanceOfStatus::variants const):
+        (JSC::InstanceOfStatus::at const):
+        (JSC::InstanceOfStatus::operator[] const):
+        * bytecode/InstanceOfVariant.cpp: Added.
+        (JSC::InstanceOfVariant::InstanceOfVariant):
+        (JSC::InstanceOfVariant::attemptToMerge):
+        (JSC::InstanceOfVariant::dump const):
+        (JSC::InstanceOfVariant::dumpInContext const):
+        * bytecode/InstanceOfVariant.h: Added.
+        (JSC::InstanceOfVariant::InstanceOfVariant):
+        (JSC::InstanceOfVariant::operator bool const):
+        (JSC::InstanceOfVariant::structureSet const):
+        (JSC::InstanceOfVariant::structureSet):
+        (JSC::InstanceOfVariant::conditionSet const):
+        (JSC::InstanceOfVariant::prototype const):
+        (JSC::InstanceOfVariant::isHit const):
+        * bytecode/StructureStubInfo.cpp:
+        (JSC::StructureStubInfo::StructureStubInfo):
+        * bytecode/StructureStubInfo.h:
+        (JSC::StructureStubInfo::considerCaching):
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::parseBlock):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGConstantFoldingPhase.cpp:
+        (JSC::DFG::ConstantFoldingPhase::foldConstants):
+        * dfg/DFGDoesGC.cpp:
+        (JSC::DFG::doesGC):
+        * dfg/DFGFixupPhase.cpp:
+        (JSC::DFG::FixupPhase::fixupNode):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::dump):
+        * dfg/DFGGraph.h:
+        * dfg/DFGLICMPhase.cpp:
+        (JSC::DFG::LICMPhase::attemptHoist):
+        * dfg/DFGNode.cpp:
+        (JSC::DFG::Node::remove):
+        * dfg/DFGNode.h:
+        (JSC::DFG::Node::hasMatchStructureData):
+        (JSC::DFG::Node::matchStructureData):
+        * dfg/DFGNodeType.h:
+        * dfg/DFGSafeToExecute.h:
+        (JSC::DFG::safeToExecute):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileMatchStructure):
+        * dfg/DFGSpeculativeJIT.h:
+        * dfg/DFGSpeculativeJIT32_64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * ftl/FTLCapabilities.cpp:
+        (JSC::FTL::canCompile):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::compileNode):
+        (JSC::FTL::DFG::LowerDFGToB3::compileMatchStructure):
+
 2018-05-19  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [JSC] JSC should have consistent InById IC
index 9e7f7bf..2802ef6 100644 (file)
                0FB17663196B8F9E0091052A /* DFGPureValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB1765F196B8F9E0091052A /* DFGPureValue.h */; };
                0FB3878E1BFBC44D00E3AB1E /* AirBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB3878B1BFBC44D00E3AB1E /* AirBlockWorklist.h */; };
                0FB387901BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */; };
+               0FB399BE20AF6B3D0017E213 /* ICStatusUtils.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB399BD20AF6B380017E213 /* ICStatusUtils.h */; };
+               0FB399BF20AF6B3F0017E213 /* InstanceOfStatus.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB399BB20AF6B2A0017E213 /* InstanceOfStatus.h */; };
+               0FB399C020AF6B430017E213 /* InstanceOfVariant.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB399B920AF6B2A0017E213 /* InstanceOfVariant.h */; };
                0FB4677F1FDDA6E9003FCB09 /* AtomIndices.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB4677E1FDDA6E5003FCB09 /* AtomIndices.h */; };
                0FB467801FDDA6F1003FCB09 /* IsoCellSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB4677D1FDDA6D9003FCB09 /* IsoCellSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FB467811FDDA6F7003FCB09 /* IsoCellSetInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB4677B1FDDA6D8003FCB09 /* IsoCellSetInlines.h */; };
                0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirOptimizeBlockOrder.cpp; path = b3/air/AirOptimizeBlockOrder.cpp; sourceTree = "<group>"; };
                0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirOptimizeBlockOrder.h; path = b3/air/AirOptimizeBlockOrder.h; sourceTree = "<group>"; };
                0FB387911BFD31A100E3AB1E /* FTLCompile.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLCompile.cpp; path = ftl/FTLCompile.cpp; sourceTree = "<group>"; };
+               0FB399B920AF6B2A0017E213 /* InstanceOfVariant.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = InstanceOfVariant.h; sourceTree = "<group>"; };
+               0FB399BA20AF6B2A0017E213 /* InstanceOfStatus.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = InstanceOfStatus.cpp; sourceTree = "<group>"; };
+               0FB399BB20AF6B2A0017E213 /* InstanceOfStatus.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = InstanceOfStatus.h; sourceTree = "<group>"; };
+               0FB399BC20AF6B2A0017E213 /* InstanceOfVariant.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = InstanceOfVariant.cpp; sourceTree = "<group>"; };
+               0FB399BD20AF6B380017E213 /* ICStatusUtils.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ICStatusUtils.h; sourceTree = "<group>"; };
                0FB415831D78F98200DF8D09 /* ArrayConventions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ArrayConventions.cpp; sourceTree = "<group>"; };
                0FB438A219270B1D00E1FBC9 /* StructureSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StructureSet.cpp; sourceTree = "<group>"; };
                0FB4677B1FDDA6D8003FCB09 /* IsoCellSetInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IsoCellSetInlines.h; sourceTree = "<group>"; };
                                0F0332C218B01763005F979A /* GetByIdVariant.h */,
                                14AD91081DCA92940014F9FE /* GlobalCodeBlock.h */,
                                0F0B83A814BCF55E00885B4F /* HandlerInfo.h */,
+                               0FB399BD20AF6B380017E213 /* ICStatusUtils.h */,
                                7905BB661D12050E0019FE57 /* InlineAccess.cpp */,
                                7905BB671D12050E0019FE57 /* InlineAccess.h */,
                                148A7BED1B82975A002D9157 /* InlineCallFrame.cpp */,
                                148A7BEE1B82975A002D9157 /* InlineCallFrame.h */,
                                0F24E55317F0B71C00ABB217 /* InlineCallFrameSet.cpp */,
                                0F24E55417F0B71C00ABB217 /* InlineCallFrameSet.h */,
+                               0FB399BA20AF6B2A0017E213 /* InstanceOfStatus.cpp */,
+                               0FB399BB20AF6B2A0017E213 /* InstanceOfStatus.h */,
+                               0FB399BC20AF6B2A0017E213 /* InstanceOfVariant.cpp */,
+                               0FB399B920AF6B2A0017E213 /* InstanceOfVariant.h */,
                                969A07930ED1D3AE00F1F681 /* Instruction.h */,
                                53F6BF6C1C3F060A00F41E5D /* InternalFunctionAllocationProfile.h */,
                                BCFD8C900EEB2EE700283848 /* JumpTable.cpp */,
                                A503FA1E188E0FB000110F14 /* JSJavaScriptCallFramePrototype.h in Headers */,
                                7013CA8C1B491A9400CAE613 /* JSJob.h in Headers */,
                                BC18C4160E16F5CD00B34460 /* JSLexicalEnvironment.h in Headers */,
+                               0FB399C020AF6B430017E213 /* InstanceOfVariant.h in Headers */,
                                BC18C4230E16F5CD00B34460 /* JSLock.h in Headers */,
                                C25D709C16DE99F400FCA6BC /* JSManagedValue.h in Headers */,
                                2A4BB7F318A41179008A0FCD /* JSManagedValueInternal.h in Headers */,
                                0F4680CD14BBB17D00BFE272 /* LowLevelInterpreter.h in Headers */,
                                981ED82328234D91BAECCADE /* MachineContext.h in Headers */,
                                14B723B812D7DA6F003BD5ED /* MachineStackMarker.h in Headers */,
+                               0FB399BF20AF6B3F0017E213 /* InstanceOfStatus.h in Headers */,
                                86C36EEA0EE1289D00B3DF59 /* MacroAssembler.h in Headers */,
                                86D3B2C610156BDE002865E7 /* MacroAssemblerARM.h in Headers */,
                                A1A009C01831A22D00CF8711 /* MacroAssemblerARM64.h in Headers */,
                                705B41AE1A6E501E00716757 /* SymbolConstructor.h in Headers */,
                                996B73271BDA08EF00331B84 /* SymbolConstructor.lut.h in Headers */,
                                705B41B01A6E501E00716757 /* SymbolObject.h in Headers */,
+                               0FB399BE20AF6B3D0017E213 /* ICStatusUtils.h in Headers */,
                                705B41B21A6E501E00716757 /* SymbolPrototype.h in Headers */,
                                996B73281BDA08EF00331B84 /* SymbolPrototype.lut.h in Headers */,
                                BC18C46B0E16F5CD00B34460 /* SymbolTable.h in Headers */,
index df22408..6ad1a45 100644 (file)
@@ -223,6 +223,8 @@ bytecode/InlineAccess.cpp
 bytecode/InlineCallFrame.cpp
 bytecode/InlineCallFrameSet.cpp
 bytecode/InstanceOfAccessCase.cpp
+bytecode/InstanceOfStatus.cpp
+bytecode/InstanceOfVariant.cpp
 bytecode/IntrinsicGetterAccessCase.cpp
 bytecode/JumpTable.cpp
 bytecode/LLIntPrototypeLoadAdaptiveStructureWatchpoint.cpp
index 04a3767..972d5de 100644 (file)
@@ -29,6 +29,7 @@
 #include "CodeBlock.h"
 #include "ComplexGetStatus.h"
 #include "GetterSetterAccessCase.h"
+#include "ICStatusUtils.h"
 #include "InterpreterInlines.h"
 #include "IntrinsicGetterAccessCase.h"
 #include "JSCInlines.h"
@@ -47,22 +48,7 @@ class GetterSetter;
 
 bool GetByIdStatus::appendVariant(const GetByIdVariant& variant)
 {
-    // Attempt to merge this variant with an already existing variant.
-    for (unsigned i = 0; i < m_variants.size(); ++i) {
-        if (m_variants[i].attemptToMerge(variant))
-            return true;
-    }
-    
-    // Make sure there is no overlap. We should have pruned out opportunities for
-    // overlap but it's possible that an inline cache got into a weird state. We are
-    // defensive and bail if we detect crazy.
-    for (unsigned i = 0; i < m_variants.size(); ++i) {
-        if (m_variants[i].structureSet().overlaps(variant.structureSet()))
-            return false;
-    }
-    
-    m_variants.append(variant);
-    return true;
+    return appendICStatusVariant(m_variants, variant);
 }
 
 #if ENABLE(DFG_JIT)
@@ -432,14 +418,7 @@ void GetByIdStatus::filter(const StructureSet& set)
 {
     if (m_state != Simple)
         return;
-    
-    // FIXME: We could also filter the variants themselves.
-    
-    m_variants.removeAllMatching(
-        [&] (GetByIdVariant& variant) -> bool {
-            return !variant.structureSet().overlaps(set);
-        });
-    
+    filterICStatusVariants(m_variants, set);
     if (m_variants.isEmpty())
         m_state = NoInformation;
 }
index 1d662c9..a309bf9 100644 (file)
@@ -93,7 +93,7 @@ public:
     State state() const { return m_state; }
     
     bool isSet() const { return m_state != NoInformation; }
-    bool operator!() const { return !isSet(); }
+    explicit operator bool() const { return isSet(); }
     bool isSimple() const { return m_state == Simple; }
     bool isCustom() const { return m_state == Custom; }
     bool isModuleNamespace() const { return m_state == ModuleNamespace; }
index 4a16278..cf2814a 100644 (file)
@@ -55,7 +55,7 @@ public:
     GetByIdVariant& operator=(const GetByIdVariant&);
     
     bool isSet() const { return !!m_structureSet.size(); }
-    bool operator!() const { return !isSet(); }
+    explicit operator bool() const { return isSet(); }
     const StructureSet& structureSet() const { return m_structureSet; }
     StructureSet& structureSet() { return m_structureSet; }
 
diff --git a/Source/JavaScriptCore/bytecode/ICStatusUtils.h b/Source/JavaScriptCore/bytecode/ICStatusUtils.h
new file mode 100644 (file)
index 0000000..9003e5c
--- /dev/null
@@ -0,0 +1,63 @@
+/*
+ * Copyright (C) 2018 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+namespace JSC {
+
+template<typename VariantVectorType, typename VariantType>
+bool appendICStatusVariant(VariantVectorType& variants, const VariantType& variant)
+{
+    // Attempt to merge this variant with an already existing variant.
+    for (unsigned i = 0; i < variants.size(); ++i) {
+        if (variants[i].attemptToMerge(variant))
+            return true;
+    }
+    
+    // Make sure there is no overlap. We should have pruned out opportunities for
+    // overlap but it's possible that an inline cache got into a weird state. We are
+    // defensive and bail if we detect crazy.
+    for (unsigned i = 0; i < variants.size(); ++i) {
+        if (variants[i].structureSet().overlaps(variant.structureSet()))
+            return false;
+    }
+    
+    variants.append(variant);
+    return true;
+}
+
+template<typename VariantVectorType>
+void filterICStatusVariants(VariantVectorType& variants, const StructureSet& set)
+{
+    // FIXME: We could also filter the variants themselves.
+    
+    variants.removeAllMatching(
+        [&] (auto& variant) -> bool {
+            return !variant.structureSet().overlaps(set);
+        });
+}
+
+} // namespace JSC
+
diff --git a/Source/JavaScriptCore/bytecode/InstanceOfStatus.cpp b/Source/JavaScriptCore/bytecode/InstanceOfStatus.cpp
new file mode 100644 (file)
index 0000000..d1b99ba
--- /dev/null
@@ -0,0 +1,128 @@
+/*
+ * Copyright (C) 2018 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "InstanceOfStatus.h"
+
+#include "ICStatusUtils.h"
+#include "JSCInlines.h"
+#include "PolymorphicAccess.h"
+#include "StructureStubInfo.h"
+
+namespace JSC {
+
+void InstanceOfStatus::appendVariant(const InstanceOfVariant& variant)
+{
+    appendICStatusVariant(m_variants, variant);
+}
+
+InstanceOfStatus InstanceOfStatus::computeFor(
+    CodeBlock* codeBlock, StubInfoMap& infoMap, unsigned bytecodeIndex)
+{
+    ConcurrentJSLocker locker(codeBlock->m_lock);
+    
+    InstanceOfStatus result;
+#if ENABLE(DFG_JIT)
+    result = computeForStubInfo(locker, infoMap.get(CodeOrigin(bytecodeIndex)));
+
+    if (!result.takesSlowPath()) {
+        UnlinkedCodeBlock* unlinkedCodeBlock = codeBlock->unlinkedCodeBlock();
+        ConcurrentJSLocker locker(unlinkedCodeBlock->m_lock);
+        // We also check for BadType here in case this is "primitive instanceof Foo".
+        if (unlinkedCodeBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadCache))
+            || unlinkedCodeBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadConstantCache))
+            || unlinkedCodeBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadType)))
+            return TakesSlowPath;
+    }
+#else
+    UNUSED_PARAM(infoMap);
+    UNUSED_PARAM(codeOrigin);
+#endif
+    
+    return result;
+}
+
+#if ENABLE(DFG_JIT)
+InstanceOfStatus InstanceOfStatus::computeForStubInfo(const ConcurrentJSLocker&, StructureStubInfo* stubInfo)
+{
+    if (!stubInfo || !stubInfo->everConsidered)
+        return NoInformation;
+    
+    // FIXME: We wouldn't have to bail for nonCell if we taught MatchStructure how to handle non
+    // cells.
+    // https://bugs.webkit.org/show_bug.cgi?id=185784
+    if (stubInfo->tookSlowPath || stubInfo->sawNonCell)
+        return TakesSlowPath;
+    
+    if (stubInfo->cacheType != CacheType::Stub)
+        return TakesSlowPath; // This is conservative. It could be that we have no information.
+    
+    PolymorphicAccess* list = stubInfo->u.stub;
+    InstanceOfStatus result;
+    for (unsigned listIndex = 0; listIndex < list->size(); ++listIndex) {
+        const AccessCase& access = list->at(listIndex);
+        
+        if (access.type() == AccessCase::InstanceOfGeneric)
+            return TakesSlowPath;
+        
+        if (!access.conditionSet().structuresEnsureValidity())
+            return TakesSlowPath;
+        
+        result.appendVariant(InstanceOfVariant(
+            access.structure(),
+            access.conditionSet(),
+            access.as<InstanceOfAccessCase>().prototype(),
+            access.type() == AccessCase::InstanceOfHit));
+    }
+    
+    return result;
+}
+#endif // ENABLE(DFG_JIT)
+
+JSObject* InstanceOfStatus::commonPrototype() const
+{
+    JSObject* prototype = nullptr;
+    for (const InstanceOfVariant& variant : m_variants) {
+        if (!prototype) {
+            prototype = variant.prototype();
+            continue;
+        }
+        if (prototype != variant.prototype())
+            return nullptr;
+    }
+    return prototype;
+}
+
+void InstanceOfStatus::filter(const StructureSet& structureSet)
+{
+    if (m_state != Simple)
+        return;
+    filterICStatusVariants(m_variants, structureSet);
+    if (m_variants.isEmpty())
+        m_state = NoInformation;
+}
+
+} // namespace JSC
+
diff --git a/Source/JavaScriptCore/bytecode/InstanceOfStatus.h b/Source/JavaScriptCore/bytecode/InstanceOfStatus.h
new file mode 100644 (file)
index 0000000..fe466c4
--- /dev/null
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2018 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#include "CodeOrigin.h"
+#include "ConcurrentJSLock.h"
+#include "InstanceOfVariant.h"
+
+namespace JSC {
+
+class AccessCase;
+class CodeBlock;
+class StructureStubInfo;
+
+typedef HashMap<CodeOrigin, StructureStubInfo*, CodeOriginApproximateHash> StubInfoMap;
+
+class InstanceOfStatus {
+public:
+    enum State {
+        // It's uncached so we have no information.
+        NoInformation,
+        
+        // It's cached in a simple way.
+        Simple,
+        
+        // It's known to often take slow path.
+        TakesSlowPath
+    };
+    
+    InstanceOfStatus()
+        : m_state(NoInformation)
+    {
+    }
+    
+    InstanceOfStatus(State state)
+        : m_state(state)
+    {
+        ASSERT(state == NoInformation || state == TakesSlowPath);
+    }
+    
+    static InstanceOfStatus computeFor(CodeBlock*, StubInfoMap&, unsigned bytecodeIndex);
+    
+#if ENABLE(DFG_JIT)
+    static InstanceOfStatus computeForStubInfo(const ConcurrentJSLocker&, StructureStubInfo*);
+#endif
+    
+    State state() const { return m_state; }
+    
+    bool isSet() const { return m_state != NoInformation; }
+    explicit operator bool() const { return isSet(); }
+    
+    bool isSimple() const { return m_state == Simple; }
+    bool takesSlowPath() const { return m_state == TakesSlowPath; }
+    
+    JSObject* commonPrototype() const;
+    
+    size_t numVariants() const { return m_variants.size(); }
+    const Vector<InstanceOfVariant, 2>& variants() const { return m_variants; }
+    const InstanceOfVariant& at(size_t index) const { return m_variants[index]; }
+    const InstanceOfVariant& operator[](size_t index) const { return at(index); }
+
+    void filter(const StructureSet&);
+    
+    void dump(PrintStream&) const;
+
+private:
+    void appendVariant(const InstanceOfVariant&);
+    
+    State m_state;
+    Vector<InstanceOfVariant, 2> m_variants;
+};
+
+} // namespace JSC
+
diff --git a/Source/JavaScriptCore/bytecode/InstanceOfVariant.cpp b/Source/JavaScriptCore/bytecode/InstanceOfVariant.cpp
new file mode 100644 (file)
index 0000000..2bdb493
--- /dev/null
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2018 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "InstanceOfVariant.h"
+
+#include "JSCInlines.h"
+#include <wtf/ListDump.h>
+
+namespace JSC {
+
+InstanceOfVariant::InstanceOfVariant(
+    const StructureSet& structureSet, const ObjectPropertyConditionSet& conditionSet,
+    JSObject* prototype, bool isHit)
+    : m_structureSet(structureSet)
+    , m_conditionSet(conditionSet)
+    , m_prototype(prototype)
+    , m_isHit(isHit)
+{
+}
+
+bool InstanceOfVariant::attemptToMerge(const InstanceOfVariant& other)
+{
+    if (m_prototype != other.m_prototype)
+        return false;
+    
+    if (m_isHit != other.m_isHit)
+        return false;
+    
+    ObjectPropertyConditionSet mergedConditionSet = m_conditionSet.mergedWith(other.m_conditionSet);
+    if (!mergedConditionSet.isValid())
+        return false;
+    m_conditionSet = mergedConditionSet;
+    
+    m_structureSet.merge(other.m_structureSet);
+    
+    return true;
+}
+
+void InstanceOfVariant::dump(PrintStream& out) const
+{
+    dumpInContext(out, nullptr);
+}
+
+void InstanceOfVariant::dumpInContext(PrintStream& out, DumpContext* context) const
+{
+    if (!*this) {
+        out.print("<empty>");
+        return;
+    }
+    
+    out.print(
+        "<", inContext(structureSet(), context), ", ", inContext(m_conditionSet, context), ","
+        " prototype = ", inContext(JSValue(m_prototype), context), ","
+        " isHit = ", m_isHit, ">");
+}
+
+} // namespace JSC
+
diff --git a/Source/JavaScriptCore/bytecode/InstanceOfVariant.h b/Source/JavaScriptCore/bytecode/InstanceOfVariant.h
new file mode 100644 (file)
index 0000000..1f13bbe
--- /dev/null
@@ -0,0 +1,66 @@
+/*
+ * Copyright (C) 2018 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#include "ObjectPropertyConditionSet.h"
+#include "StructureSet.h"
+
+namespace JSC {
+
+class InstanceOfStatus;
+
+class InstanceOfVariant {
+public:
+    InstanceOfVariant() = default;
+    InstanceOfVariant(const StructureSet&, const ObjectPropertyConditionSet&, JSObject* prototype, bool isHit);
+    
+    explicit operator bool() const { return !!m_structureSet.size(); }
+    
+    const StructureSet& structureSet() const { return m_structureSet; }
+    StructureSet& structureSet() { return m_structureSet; }
+    
+    const ObjectPropertyConditionSet& conditionSet() const { return m_conditionSet; }
+    
+    JSObject* prototype() const { return m_prototype; }
+    
+    bool isHit() const { return m_isHit; }
+    
+    bool attemptToMerge(const InstanceOfVariant& other);
+    
+    void dump(PrintStream&) const;
+    void dumpInContext(PrintStream&, DumpContext*) const;
+    
+private:
+    friend class InstanceOfStatus;
+    
+    StructureSet m_structureSet;
+    ObjectPropertyConditionSet m_conditionSet;
+    JSObject* m_prototype { nullptr };
+    bool m_isHit { false };
+};
+
+} // namespace JSC
+
index 04218db..8351539 100644 (file)
@@ -51,6 +51,7 @@ StructureStubInfo::StructureStubInfo(AccessType accessType)
     , tookSlowPath(false)
     , everConsidered(false)
     , prototypeIsKnownObject(false)
+    , sawNonCell(false)
 {
 }
 
index efe619b..133b604 100644 (file)
@@ -92,8 +92,10 @@ public:
     ALWAYS_INLINE bool considerCaching(CodeBlock* codeBlock, Structure* structure)
     {
         // We never cache non-cells.
-        if (!structure)
+        if (!structure) {
+            sawNonCell = true;
             return false;
+        }
         
         // This method is called from the Optimize variants of IC slow paths. The first part of this
         // method tries to determine if the Optimize variant should really behave like the
@@ -221,6 +223,7 @@ public:
     bool tookSlowPath : 1;
     bool everConsidered : 1;
     bool prototypeIsKnownObject : 1; // Only relevant for InstanceOf.
+    bool sawNonCell : 1;
 };
 
 inline CodeOrigin getStructureStubInfoCodeOrigin(StructureStubInfo& structureStubInfo)
index 9da5f41..c4c92dd 100644 (file)
@@ -41,7 +41,7 @@
 #include "Operations.h"
 #include "PutByIdStatus.h"
 #include "StringObject.h"
-
+#include <wtf/BooleanLattice.h>
 #include <wtf/CheckedArithmetic.h>
 
 namespace JSC { namespace DFG {
@@ -3391,6 +3391,40 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
         clobberWorld();
         setNonCellTypeForNode(node, SpecBoolean);
         break;
+        
+    case MatchStructure: {
+        AbstractValue base = forNode(node->child1());
+        RegisteredStructureSet baseSet;
+        
+        BooleanLattice result = BooleanLattice::Bottom;
+        for (MatchStructureVariant& variant : node->matchStructureData().variants) {
+            RegisteredStructure structure = variant.structure;
+            if (!base.contains(structure)) {
+                m_state.setFoundConstants(true);
+                continue;
+            }
+            
+            baseSet.add(structure);
+            result = leastUpperBoundOfBooleanLattices(
+                result, variant.result ? BooleanLattice::True : BooleanLattice::False);
+        }
+        
+        if (forNode(node->child1()).changeStructure(m_graph, baseSet) == Contradiction)
+            m_state.setIsValid(false);
+        
+        switch (result) {
+        case BooleanLattice::False:
+            setConstant(node, jsBoolean(false));
+            break;
+        case BooleanLattice::True:
+            setConstant(node, jsBoolean(true));
+            break;
+        default:
+            setNonCellTypeForNode(node, SpecBoolean);
+            break;
+        }
+        break;
+    }
             
     case Phi:
         RELEASE_ASSERT(m_graph.m_form == SSA);
index 1077649..fa097f3 100644 (file)
@@ -48,6 +48,7 @@
 #include "FunctionCodeBlock.h"
 #include "GetByIdStatus.h"
 #include "Heap.h"
+#include "InstanceOfStatus.h"
 #include "JSCInlines.h"
 #include "JSFixedArray.h"
 #include "JSModuleEnvironment.h"
@@ -4783,12 +4784,40 @@ void ByteCodeParser::parseBlock(unsigned limit)
         }
 
         case op_instanceof: {
-            // FIXME: We should turn this into either a CheckStructure followed by a constant, or
-            // some kind of MultiInstanceOf thing, if the InstanceOf IC is stable.
-            // https://bugs.webkit.org/show_bug.cgi?id=185695
             auto& bytecode = *reinterpret_cast<OpInstanceof*>(currentInstruction);
+            
+            InstanceOfStatus status = InstanceOfStatus::computeFor(
+                m_inlineStackTop->m_profiledBlock, m_inlineStackTop->m_stubInfos,
+                m_currentIndex);
+            
             Node* value = get(VirtualRegister(bytecode.value()));
             Node* prototype = get(VirtualRegister(bytecode.prototype()));
+
+            // Only inline it if it's Simple with a commonPrototype; bottom/top or variable
+            // prototypes both get handled by the IC. This makes sense for bottom (unprofiled)
+            // instanceof ICs because the profit of this optimization is fairly low. So, in the
+            // absence of any information, it's better to avoid making this be the cause of a
+            // recompilation.
+            if (JSObject* commonPrototype = status.commonPrototype()) {
+                addToGraph(CheckCell, OpInfo(m_graph.freeze(commonPrototype)), prototype);
+                
+                MatchStructureData* data = m_graph.m_matchStructureData.add();
+                for (const InstanceOfVariant& variant : status.variants()) {
+                    check(variant.conditionSet());
+                    for (Structure* structure : variant.structureSet()) {
+                        MatchStructureVariant matchVariant;
+                        matchVariant.structure = m_graph.registerStructure(structure);
+                        matchVariant.result = variant.isHit();
+                        
+                        data->variants.append(matchVariant);
+                    }
+                }
+                
+                Node* match = addToGraph(MatchStructure, OpInfo(data), value);
+                set(VirtualRegister(bytecode.dst()), match);
+                NEXT_OPCODE(op_instanceof);
+            }
+            
             set(VirtualRegister(bytecode.dst()), addToGraph(InstanceOf, value, prototype));
             NEXT_OPCODE(op_instanceof);
         }
index 552edef..3ea02a8 100644 (file)
@@ -545,6 +545,10 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
         read(MiscFields);
         def(HeapLocation(IsFunctionLoc, MiscFields, node->child1()), LazyNode(node));
         return;
+        
+    case MatchStructure:
+        read(JSCell_structureID);
+        return;
 
     case ArraySlice:
         read(MiscFields);
index b7edc06..0e26ae8 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-2018 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -489,6 +489,41 @@ private:
                 changed = true;
                 break;
             }
+                
+            case MatchStructure: {
+                Edge baseEdge = node->child1();
+                Node* base = baseEdge.node();
+                MatchStructureData& data = node->matchStructureData();
+                
+                AbstractValue baseValue = m_state.forNode(base);
+
+                m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
+                alreadyHandled = true; // Don't allow the default constant folder to do things to this.
+                
+                BooleanLattice result = BooleanLattice::Bottom;
+                for (unsigned i = 0; i < data.variants.size(); ++i) {
+                    if (!baseValue.contains(data.variants[i].structure)) {
+                        data.variants[i--] = data.variants.last();
+                        data.variants.removeLast();
+                        changed = true;
+                        continue;
+                    }
+                    result = leastUpperBoundOfBooleanLattices(
+                        result,
+                        data.variants[i].result ? BooleanLattice::True : BooleanLattice::False);
+                }
+                
+                if (result == BooleanLattice::False || result == BooleanLattice::True) {
+                    RegisteredStructureSet structureSet;
+                    for (MatchStructureVariant& variant : data.variants)
+                        structureSet.add(variant.structure);
+                    addBaseCheck(indexInBlock, node, baseValue, structureSet);
+                    m_graph.convertToConstant(
+                        node, m_graph.freeze(jsBoolean(result == BooleanLattice::True)));
+                    changed = true;
+                }
+                break;
+            }
         
             case GetByIdDirect:
             case GetByIdDirectFlush:
index 416210a..fdf2e77 100644 (file)
@@ -311,6 +311,7 @@ bool doesGC(Graph& graph, Node* node)
     case AtomicsSub:
     case AtomicsXor:
     case AtomicsIsLockFree:
+    case MatchStructure:
         return false;
 
     case PushWithScope:
index 9a1dc13..ecbb3d3 100644 (file)
@@ -1454,6 +1454,13 @@ private:
             break;
         }
             
+        case MatchStructure: {
+            // FIXME: Introduce a variant of MatchStructure that doesn't do a cell check.
+            // https://bugs.webkit.org/show_bug.cgi?id=185784
+            fixEdge<CellUse>(node->child1());
+            break;
+        }
+            
         case InstanceOf: {
             if (node->child1()->shouldSpeculateCell()
                 && node->child2()->shouldSpeculateCell()
index bb5433c..1fe87b7 100644 (file)
@@ -293,6 +293,10 @@ void Graph::dump(PrintStream& out, const char* prefix, Node* node, DumpContext*
         for (unsigned i = 0; i < data.variants.size(); ++i)
             out.print(comma, inContext(data.variants[i], context));
     }
+    if (node->hasMatchStructureData()) {
+        for (MatchStructureVariant& variant : node->matchStructureData().variants)
+            out.print(comma, inContext(*variant.structure.get(), context), "=>", variant.result);
+    }
     ASSERT(node->hasVariableAccessData(*this) == node->accessesStack(*this));
     if (node->hasVariableAccessData(*this)) {
         VariableAccessData* variableAccessData = node->tryGetVariableAccessData();
index 7ab62fc..1f0c6a7 100644 (file)
@@ -1052,6 +1052,7 @@ public:
     Bag<SwitchData> m_switchData;
     Bag<MultiGetByOffsetData> m_multiGetByOffsetData;
     Bag<MultiPutByOffsetData> m_multiPutByOffsetData;
+    Bag<MatchStructureData> m_matchStructureData;
     Bag<ObjectMaterializationData> m_objectMaterializationData;
     Bag<CallVarargsData> m_callVarargsData;
     Bag<LoadVarargsData> m_loadVarargsData;
index 8a9ebbb..215f8a1 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2018 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -264,15 +264,9 @@ private:
         }
         
         m_state.initializeTo(data.preHeader);
-        if (!safeToExecute(m_state, m_graph, node)) {
-            if (verbose) {
-                dataLog(
-                    "    Not hoisting ", node, " because it isn't safe to execute.\n");
-            }
-            return false;
-        }
-        
+
         NodeOrigin originalOrigin = node->origin;
+        bool canSpeculateBlindly = !m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed);
 
         // NOTE: We could just use BackwardsDominators here directly, since we already know that the
         // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
@@ -280,8 +274,7 @@ private:
         bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
             && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
         
-        if (addsBlindSpeculation
-            && m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed)) {
+        if (addsBlindSpeculation && !canSpeculateBlindly) {
             if (verbose) {
                 dataLog(
                     "    Not hoisting ", node, " because it may exit and the pre-header (",
@@ -291,22 +284,61 @@ private:
             return false;
         }
         
+        // For abstract interpretation, these are in the reverse order that they appear in this
+        // vector.
+        Vector<Node*, 2> hoistedNodesReverse;
+        hoistedNodesReverse.append(node);
+
+        NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
+        
+        auto insertHoistedNode = [&] (Node* node) {
+            data.preHeader->insertBeforeTerminal(node);
+            node->owner = data.preHeader;
+            node->origin = terminalOrigin.withSemantic(node->origin.semantic);
+            node->origin.wasHoisted |= addsBlindSpeculation;
+        };
+        
+        if (!safeToExecute(m_state, m_graph, node)) {
+            // See if we can rescue the situation by inserting blind speculations.
+            bool ignoreEmptyChildren = true;
+            if (canSpeculateBlindly
+                && safeToExecute(m_state, m_graph, node, ignoreEmptyChildren)) {
+                if (verbose) {
+                    dataLog(
+                        "    Rescuing hoisting by inserting empty checks.\n");
+                }
+                m_graph.doToChildren(
+                    node,
+                    [&] (Edge& edge) {
+                        if (!(m_state.forNode(edge).m_type & SpecEmpty))
+                            return;
+                        
+                        Node* check = m_graph.addNode(CheckNotEmpty, originalOrigin, Edge(edge.node(), UntypedUse));
+                        insertHoistedNode(check);
+                        hoistedNodesReverse.append(check);
+                    });
+            } else {
+                if (verbose) {
+                    dataLog(
+                        "    Not hoisting ", node, " because it isn't safe to execute.\n");
+                }
+                return false;
+            }
+        }
+        
         if (verbose) {
             dataLog(
                 "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
                 "\n");
         }
 
-        data.preHeader->insertBeforeTerminal(node);
-        node->owner = data.preHeader;
-        NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
-        node->origin = terminalOrigin.withSemantic(node->origin.semantic);
-        node->origin.wasHoisted |= addsBlindSpeculation;
+        insertHoistedNode(node);
         
         // We can trust what AI proves about edge proof statuses when hoisting to the preheader.
         m_state.trustEdgeProofs();
         m_state.initializeTo(data.preHeader);
-        m_interpreter.execute(node);
+        for (unsigned i = hoistedNodesReverse.size(); i--;)
+            m_interpreter.execute(hoistedNodesReverse[i]);
         // However, when walking various inner loops below, the proof status of
         // an edge may be trivially true, even if it's not true in the preheader
         // we hoist to. We don't allow the below node executions to change the
@@ -340,7 +372,8 @@ private:
             if (subPreHeader == data.preHeader)
                 continue;
             m_state.initializeTo(subPreHeader);
-            m_interpreter.execute(node);
+            for (unsigned i = hoistedNodesReverse.size(); i--;)
+                m_interpreter.execute(hoistedNodesReverse[i]);
         }
 
         if (node->flags() & NodeHasVarArgs)
index c1db0cb..4314762 100644 (file)
@@ -97,6 +97,15 @@ void Node::remove(Graph& graph)
         return;
     }
         
+    case MatchStructure: {
+        MatchStructureData& data = matchStructureData();
+        RegisteredStructureSet set;
+        for (MatchStructureVariant& variant : data.variants)
+            set.add(variant.structure);
+        convertToCheckStructure(graph.addStructureSet(set));
+        return;
+    }
+        
     default:
         if (flags() & NodeHasVarArgs) {
             unsigned targetIndex = 0;
index f6e10eb..6236309 100644 (file)
@@ -96,6 +96,15 @@ struct MultiPutByOffsetData {
     bool reallocatesStorage() const;
 };
 
+struct MatchStructureVariant {
+    RegisteredStructure structure;
+    bool result;
+};
+
+struct MatchStructureData {
+    Vector<MatchStructureVariant, 2> variants;
+};
+
 struct NewArrayBufferData {
     union {
         struct {
@@ -1863,6 +1872,17 @@ public:
         return *m_opInfo.as<MultiPutByOffsetData*>();
     }
     
+    bool hasMatchStructureData()
+    {
+        return op() == MatchStructure;
+    }
+    
+    MatchStructureData& matchStructureData()
+    {
+        ASSERT(hasMatchStructureData());
+        return *m_opInfo.as<MatchStructureData*>();
+    }
+    
     bool hasObjectMaterializationData()
     {
         switch (op()) {
index 4fba90d..531711b 100644 (file)
@@ -346,6 +346,7 @@ namespace JSC { namespace DFG {
     macro(OverridesHasInstance, NodeMustGenerate | NodeResultBoolean) \
     macro(InstanceOf, NodeMustGenerate | NodeResultBoolean) \
     macro(InstanceOfCustom, NodeMustGenerate | NodeResultBoolean) \
+    macro(MatchStructure, NodeMustGenerate | NodeResultBoolean) \
     \
     macro(IsCellWithType, NodeResultBoolean) \
     macro(IsEmpty, NodeResultBoolean) \
index 228643b..9c661f9 100644 (file)
@@ -864,7 +864,8 @@ private:
         case IsObjectOrNull:
         case IsFunction:
         case IsCellWithType:
-        case IsTypedArrayView: {
+        case IsTypedArrayView:
+        case MatchStructure: {
             setPrediction(SpecBoolean);
             break;
         }
index 82eed6a..d6d026c 100644 (file)
@@ -134,14 +134,14 @@ private:
 // 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)
+bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node, bool ignoreEmptyChildren = false)
 {
     SafeToExecuteEdge<AbstractStateType> safeToExecuteEdge(state);
     DFG_NODE_DO_TO_CHILDREN(graph, node, safeToExecuteEdge);
     if (!safeToExecuteEdge.result())
         return false;
 
-    if (safeToExecuteEdge.maySeeEmptyChild()) {
+    if (!ignoreEmptyChildren && 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
@@ -453,6 +453,7 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case AtomicsXor:
     case AtomicsIsLockFree:
     case InitializeEntrypointArguments:
+    case MatchStructure:
         return true;
 
     case ArraySlice:
index fe8be37..1d56d46 100644 (file)
@@ -11818,6 +11818,33 @@ void SpeculativeJIT::compilePutByOffset(Node* node)
     noResult(node);
 }
 
+void SpeculativeJIT::compileMatchStructure(Node* node)
+{
+    SpeculateCellOperand base(this, node->child1());
+    GPRTemporary temp(this);
+    GPRReg baseGPR = base.gpr();
+    GPRReg tempGPR = temp.gpr();
+    
+    m_jit.load32(JITCompiler::Address(baseGPR, JSCell::structureIDOffset()), tempGPR);
+    
+    auto& variants = node->matchStructureData().variants;
+    Vector<int64_t> cases;
+    for (MatchStructureVariant& variant : variants)
+        cases.append(bitwise_cast<int32_t>(variant.structure->id()));
+    
+    BinarySwitch binarySwitch(tempGPR, cases, BinarySwitch::Int32);
+    JITCompiler::JumpList done;
+    while (binarySwitch.advance(m_jit)) {
+        m_jit.boxBooleanPayload(variants[binarySwitch.caseIndex()].result, tempGPR);
+        done.append(m_jit.jump());
+    }
+    speculationCheck(BadCache, JSValueRegs(), node, binarySwitch.fallThrough());
+    
+    done.link(&m_jit);
+    
+    blessedBooleanResult(tempGPR, node);
+}
+
 void SpeculativeJIT::compileHasStructureProperty(Node* node)
 {
     JSValueOperand base(this, node->child1());
index 46174c9..05a08ea 100644 (file)
@@ -1376,6 +1376,7 @@ public:
     void compileGetByValWithThis(Node*);
     void compileGetByOffset(Node*);
     void compilePutByOffset(Node*);
+    void compileMatchStructure(Node*);
     // If this returns false it means that we terminated speculative execution.
     bool getIntTypedArrayStoreOperand(
         GPRTemporary& value,
index 3efb7b7..272c57a 100644 (file)
@@ -3360,6 +3360,11 @@ void SpeculativeJIT::compile(Node* node)
         break;
     }
         
+    case MatchStructure: {
+        compileMatchStructure(node);
+        break;
+    }
+        
     case GetGetter: {
         compileGetGetter(node);
         break;
index 8d38697..50f2645 100644 (file)
@@ -3627,6 +3627,11 @@ void SpeculativeJIT::compile(Node* node)
         break;
     }
         
+    case MatchStructure: {
+        compileMatchStructure(node);
+        break;
+    }
+        
     case GetGetter: {
         compileGetGetter(node);
         break;
index 6b95134..f1513bb 100644 (file)
@@ -350,6 +350,7 @@ inline CapabilityLevel canCompile(Node* node)
     case PutByValAlias:
     case PutByValDirect:
     case PutByValWithThis:
+    case MatchStructure:
         // These are OK.
         break;
 
index e6decfa..911d62a 100644 (file)
@@ -914,6 +914,9 @@ private:
         case MultiPutByOffset:
             compileMultiPutByOffset();
             break;
+        case MatchStructure:
+            compileMatchStructure();
+            break;
         case GetGlobalVar:
         case GetGlobalLexicalVariable:
             compileGetGlobalVariable();
@@ -6595,6 +6598,47 @@ private:
         m_out.appendTo(continuation, lastNext);
     }
     
+    void compileMatchStructure()
+    {
+        LValue base = lowCell(m_node->child1());
+        
+        MatchStructureData& data = m_node->matchStructureData();
+        
+        LBasicBlock trueBlock = m_out.newBlock();
+        LBasicBlock falseBlock = m_out.newBlock();
+        LBasicBlock exitBlock = m_out.newBlock();
+        LBasicBlock continuation = m_out.newBlock();
+        
+        LBasicBlock lastNext = m_out.insertNewBlocksBefore(trueBlock);
+        
+        Vector<SwitchCase, 2> cases;
+        RegisteredStructureSet baseSet;
+        for (MatchStructureVariant& variant : data.variants) {
+            baseSet.add(variant.structure);
+            cases.append(SwitchCase(
+                weakStructureID(variant.structure),
+                variant.result ? trueBlock : falseBlock, Weight(1)));
+        }
+        bool structuresChecked = m_interpreter.forNode(m_node->child1()).m_structure.isSubsetOf(baseSet);
+        emitSwitchForMultiByOffset(base, structuresChecked, cases, exitBlock);
+        
+        m_out.appendTo(trueBlock, falseBlock);
+        ValueFromBlock trueResult = m_out.anchor(m_out.booleanTrue);
+        m_out.jump(continuation);
+        
+        m_out.appendTo(falseBlock, exitBlock);
+        ValueFromBlock falseResult = m_out.anchor(m_out.booleanFalse);
+        m_out.jump(continuation);
+        
+        m_out.appendTo(exitBlock, continuation);
+        if (!structuresChecked)
+            speculate(BadCache, noValue(), nullptr, m_out.booleanTrue);
+        m_out.unreachable();
+        
+        m_out.appendTo(continuation, lastNext);
+        setBoolean(m_out.phi(Int32, trueResult, falseResult));
+    }
+    
     void compileGetGlobalVariable()
     {
         setJSValue(m_out.load64(m_out.absolute(m_node->variablePointer())));
index fa290f0..44e7a19 100644 (file)
@@ -1,3 +1,18 @@
+2018-05-18  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should inline InstanceOf ICs
+        https://bugs.webkit.org/show_bug.cgi?id=185695
+
+        Reviewed by Yusuke Suzuki.
+        
+        I found myself needing a way to represent bottom/false/true/top, so I created it.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/BooleanLattice.h: Added.
+        (WTF::lubBooleanLattice):
+        (WTF::printInternal):
+        * wtf/CMakeLists.txt:
+
 2018-05-17  Jiewen Tan  <jiewen_tan@apple.com>
 
         Convert CertificateInfo into Credential in UI Process instead of Networking Process
index 1a38f19..55a4c60 100644 (file)
                0FB14E18180FA218009B6B4D /* Bag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Bag.h; sourceTree = "<group>"; };
                0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = BagToHashMap.h; sourceTree = "<group>"; };
                0FB317C31C488001007E395A /* SystemTracing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SystemTracing.h; sourceTree = "<group>"; };
+               0FB399B820AF5A580017E213 /* BooleanLattice.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BooleanLattice.h; sourceTree = "<group>"; };
                0FB467821FDE282B003FCB09 /* ConcurrentBuffer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ConcurrentBuffer.h; sourceTree = "<group>"; };
                0FB467831FDE282C003FCB09 /* ConcurrentVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ConcurrentVector.h; sourceTree = "<group>"; };
                0FC4488216FE9FE100844BE9 /* ProcessID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ProcessID.h; sourceTree = "<group>"; };
                                1A944F461C3D8814005BD28C /* BlockPtr.h */,
                                A8A47264151A825A004123FF /* BlockStack.h */,
                                A8A47265151A825A004123FF /* BloomFilter.h */,
+                               0FB399B820AF5A580017E213 /* BooleanLattice.h */,
                                0F93274A1C17F4B700CF6564 /* Box.h */,
                                7C3F72391D78811900674E26 /* Brigand.h */,
                                0F4570441BE834410062A629 /* BubbleSort.h */,
diff --git a/Source/WTF/wtf/BooleanLattice.h b/Source/WTF/wtf/BooleanLattice.h
new file mode 100644 (file)
index 0000000..c16713a
--- /dev/null
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2018 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#include <wtf/PrintStream.h>
+
+namespace WTF {
+
+// This is a boolean type that is part of an abstract value lattice. It's useful for inferring what
+// the boolean value of something is by exploring all boolean values we encounter.
+//
+// It's useful to think of a lattice as a set. The comments below also describe what the enum values
+// mean in terms of sets.
+//
+// FIXME: This would work a lot better as a class with methods. Then we could ensure that the default
+// value is always Bottom, we could have nice conversions to and from boolean, and things like the
+// leastUpperBound function could be a member function with a nicer name.
+// https://bugs.webkit.org/show_bug.cgi?id=185804
+enum class BooleanLattice : uint8_t {
+    // Bottom means that we haven't seen any boolean values yet. We don't know what boolean value we
+    // will infer yet. If we are left with Bottom after we have considered all booleans, it means
+    // that we did not see any booleans.
+    //
+    // This represents the empty set.
+    Bottom = 0,
+    
+    // We definitely saw false.
+    //
+    // This represents a set that just contains false.
+    False = 1,
+
+    // We definitely saw true.
+    //
+    // This represents a set that just contains true.
+    True = 2,
+    
+    // Top means that we have seen both false and true. Like Bottom, it means that we don't know what
+    // boolean value this lattice has. But unlike Bottom, which bases its lack of knowledge on not
+    // having seen any booleans, Top bases its lack of knowledge based on having seen both False and
+    // True.
+    //
+    // This represents a set that contains both false and true.
+    Top = 3
+};
+
+inline BooleanLattice leastUpperBoundOfBooleanLattices(BooleanLattice a, BooleanLattice b)
+{
+    return static_cast<BooleanLattice>(static_cast<uint8_t>(a) | static_cast<uintptr_t>(b));
+}
+
+inline void printInternal(PrintStream& out, BooleanLattice value)
+{
+    switch (value) {
+    case BooleanLattice::Bottom:
+        out.print("Bottom");
+        return;
+    case BooleanLattice::False:
+        out.print("False");
+        return;
+    case BooleanLattice::True:
+        out.print("True");
+        return;
+    case BooleanLattice::Top:
+        out.print("Top");
+        return;
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+} // namespace WTF
+
+using WTF::BooleanLattice;
+using WTF::leastUpperBoundOfBooleanLattices;
+
index 4890297..70dc231 100644 (file)
@@ -14,6 +14,7 @@ set(WTF_PUBLIC_HEADERS
     BlockPtr.h
     BlockStack.h
     BloomFilter.h
+    BooleanLattice.h
     Box.h
     Brigand.h
     BubbleSort.h