fourthTier: Decouple the way that CFA stores its state from the way it does abstract...
authoroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 25 Jul 2013 04:05:03 +0000 (04:05 +0000)
committeroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 25 Jul 2013 04:05:03 +0000 (04:05 +0000)
https://bugs.webkit.org/show_bug.cgi?id=118835

Reviewed by Oliver Hunt.

This separates AbstractState into two things:

- InPlaceAbstractState, which can tell you the abstract state of anything you
  might care about, and uses the old AbstractState's algorithms and data
  structures for doing so.

- AbstractInterpreter<AbstractStateType>, which can execute a DFG::Node* with
  respect to an AbstractStateType. Currently we always use
  AbstractStateType = InPlaceAbstractState. But we could drop in an other
  class that supports basic primitives like forNode() and variables().

This is important because:

- We want to hoist things out of loops.

- We don't know what things rely on what type checks.

- We only want to hoist type checks out of loops if they aren't clobbered.

- We may want to still hoist things that depended on those type checks, if it's
  safe to do those things based on the CFA state at the tail of the loop
  pre-header.

- We don't want things to rely on their type checks by way of a token, because
  that's just weird.

So, we want to be able to have a special form of the CFA that can
incrementally update a basic block's state-at-tail, and we want to be able to
do this for multiple blocks simultaneously. This requires *not* storing the
per-node state in the nodes themselves, but instead using the at-tail HashMap
directly.

Hence we need to have a way of making the abstract interpreter (i.e.
AbstractState::execute) polymorphic with respect to state representation. Put
another way, we need to separate the way that abstract state is represented
from the way DFG IR is abstractly interpreted.

* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGAbstractInterpreter.h: Added.
(DFG):
(AbstractInterpreter):
(JSC::DFG::AbstractInterpreter::forNode):
(JSC::DFG::AbstractInterpreter::variables):
(JSC::DFG::AbstractInterpreter::needsTypeCheck):
(JSC::DFG::AbstractInterpreter::filterEdgeByUse):
(JSC::DFG::AbstractInterpreter::filter):
(JSC::DFG::AbstractInterpreter::filterArrayModes):
(JSC::DFG::AbstractInterpreter::filterByValue):
(JSC::DFG::AbstractInterpreter::trySetConstant):
(JSC::DFG::AbstractInterpreter::filterByType):
* dfg/DFGAbstractInterpreterInlines.h: Added.
(DFG):
(JSC::DFG::::AbstractInterpreter):
(JSC::DFG::::~AbstractInterpreter):
(JSC::DFG::::booleanResult):
(JSC::DFG::::startExecuting):
(JSC::DFG::::executeEdges):
(JSC::DFG::::verifyEdge):
(JSC::DFG::::verifyEdges):
(JSC::DFG::::executeEffects):
(JSC::DFG::::execute):
(JSC::DFG::::clobberWorld):
(JSC::DFG::::clobberCapturedVars):
(JSC::DFG::::clobberStructures):
(JSC::DFG::::dump):
(JSC::DFG::::filter):
(JSC::DFG::::filterArrayModes):
(JSC::DFG::::filterByValue):
* dfg/DFGAbstractState.cpp: Removed.
* dfg/DFGAbstractState.h: Removed.
* dfg/DFGArgumentsSimplificationPhase.cpp:
* dfg/DFGCFAPhase.cpp:
(JSC::DFG::CFAPhase::CFAPhase):
(JSC::DFG::CFAPhase::performBlockCFA):
(CFAPhase):
* dfg/DFGCFGSimplificationPhase.cpp:
* dfg/DFGConstantFoldingPhase.cpp:
(JSC::DFG::ConstantFoldingPhase::ConstantFoldingPhase):
(JSC::DFG::ConstantFoldingPhase::foldConstants):
(ConstantFoldingPhase):
* dfg/DFGInPlaceAbstractState.cpp: Added.
(DFG):
(JSC::DFG::InPlaceAbstractState::InPlaceAbstractState):
(JSC::DFG::InPlaceAbstractState::~InPlaceAbstractState):
(JSC::DFG::InPlaceAbstractState::beginBasicBlock):
(JSC::DFG::setLiveValues):
(JSC::DFG::InPlaceAbstractState::initialize):
(JSC::DFG::InPlaceAbstractState::endBasicBlock):
(JSC::DFG::InPlaceAbstractState::reset):
(JSC::DFG::InPlaceAbstractState::mergeStateAtTail):
(JSC::DFG::InPlaceAbstractState::merge):
(JSC::DFG::InPlaceAbstractState::mergeToSuccessors):
(JSC::DFG::InPlaceAbstractState::mergeVariableBetweenBlocks):
* dfg/DFGInPlaceAbstractState.h: Added.
(DFG):
(InPlaceAbstractState):
(JSC::DFG::InPlaceAbstractState::forNode):
(JSC::DFG::InPlaceAbstractState::variables):
(JSC::DFG::InPlaceAbstractState::block):
(JSC::DFG::InPlaceAbstractState::didClobber):
(JSC::DFG::InPlaceAbstractState::isValid):
(JSC::DFG::InPlaceAbstractState::setDidClobber):
(JSC::DFG::InPlaceAbstractState::setIsValid):
(JSC::DFG::InPlaceAbstractState::setBranchDirection):
(JSC::DFG::InPlaceAbstractState::setFoundConstants):
(JSC::DFG::InPlaceAbstractState::haveStructures):
(JSC::DFG::InPlaceAbstractState::setHaveStructures):
* dfg/DFGMergeMode.h: Added.
(DFG):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::SpeculativeJIT):
(JSC::DFG::SpeculativeJIT::backwardTypeCheck):
(JSC::DFG::SpeculativeJIT::compileCurrentBlock):
(JSC::DFG::SpeculativeJIT::compileToStringOnCell):
(JSC::DFG::SpeculativeJIT::speculateStringIdentAndLoadStorage):
(JSC::DFG::SpeculativeJIT::speculateStringObject):
(JSC::DFG::SpeculativeJIT::speculateStringOrStringObject):
* dfg/DFGSpeculativeJIT.h:
(JSC::DFG::SpeculativeJIT::needsTypeCheck):
(SpeculativeJIT):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::fillSpeculateIntInternal):
(JSC::DFG::SpeculativeJIT::fillSpeculateDouble):
(JSC::DFG::SpeculativeJIT::fillSpeculateCell):
(JSC::DFG::SpeculativeJIT::fillSpeculateBoolean):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::fillSpeculateIntInternal):
(JSC::DFG::SpeculativeJIT::fillSpeculateDouble):
(JSC::DFG::SpeculativeJIT::fillSpeculateCell):
(JSC::DFG::SpeculativeJIT::fillSpeculateBoolean):
* ftl/FTLLowerDFGToLLVM.cpp:
(FTL):
(JSC::FTL::LowerDFGToLLVM::LowerDFGToLLVM):
(JSC::FTL::LowerDFGToLLVM::compileNode):
(JSC::FTL::LowerDFGToLLVM::appendTypeCheck):
(JSC::FTL::LowerDFGToLLVM::speculate):
(JSC::FTL::LowerDFGToLLVM::speculateNumber):
(JSC::FTL::LowerDFGToLLVM::speculateRealNumber):
(LowerDFGToLLVM):

Conflicts:
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

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

16 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h [moved from Source/JavaScriptCore/dfg/DFGAbstractState.h with 53% similarity]
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h [moved from Source/JavaScriptCore/dfg/DFGAbstractState.cpp with 70% similarity]
Source/JavaScriptCore/dfg/DFGArgumentsSimplificationPhase.cpp
Source/JavaScriptCore/dfg/DFGCFAPhase.cpp
Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp
Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGMergeMode.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp

index b1868b2..b8257e4 100644 (file)
@@ -1,5 +1,152 @@
 2013-07-18  Filip Pizlo  <fpizlo@apple.com>
 
+        fourthTier: Decouple the way that CFA stores its state from the way it does abstract interpretation
+        https://bugs.webkit.org/show_bug.cgi?id=118835
+
+        Reviewed by Oliver Hunt.
+        
+        This separates AbstractState into two things:
+        
+        - InPlaceAbstractState, which can tell you the abstract state of anything you
+          might care about, and uses the old AbstractState's algorithms and data
+          structures for doing so.
+        
+        - AbstractInterpreter<AbstractStateType>, which can execute a DFG::Node* with
+          respect to an AbstractStateType. Currently we always use
+          AbstractStateType = InPlaceAbstractState. But we could drop in an other
+          class that supports basic primitives like forNode() and variables().
+        
+        This is important because:
+        
+        - We want to hoist things out of loops.
+
+        - We don't know what things rely on what type checks.
+
+        - We only want to hoist type checks out of loops if they aren't clobbered.
+
+        - We may want to still hoist things that depended on those type checks, if it's
+          safe to do those things based on the CFA state at the tail of the loop
+          pre-header.
+
+        - We don't want things to rely on their type checks by way of a token, because
+          that's just weird.
+
+        So, we want to be able to have a special form of the CFA that can
+        incrementally update a basic block's state-at-tail, and we want to be able to
+        do this for multiple blocks simultaneously. This requires *not* storing the
+        per-node state in the nodes themselves, but instead using the at-tail HashMap
+        directly.
+
+        Hence we need to have a way of making the abstract interpreter (i.e.
+        AbstractState::execute) polymorphic with respect to state representation. Put
+        another way, we need to separate the way that abstract state is represented
+        from the way DFG IR is abstractly interpreted.
+
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * dfg/DFGAbstractInterpreter.h: Added.
+        (DFG):
+        (AbstractInterpreter):
+        (JSC::DFG::AbstractInterpreter::forNode):
+        (JSC::DFG::AbstractInterpreter::variables):
+        (JSC::DFG::AbstractInterpreter::needsTypeCheck):
+        (JSC::DFG::AbstractInterpreter::filterEdgeByUse):
+        (JSC::DFG::AbstractInterpreter::filter):
+        (JSC::DFG::AbstractInterpreter::filterArrayModes):
+        (JSC::DFG::AbstractInterpreter::filterByValue):
+        (JSC::DFG::AbstractInterpreter::trySetConstant):
+        (JSC::DFG::AbstractInterpreter::filterByType):
+        * dfg/DFGAbstractInterpreterInlines.h: Added.
+        (DFG):
+        (JSC::DFG::::AbstractInterpreter):
+        (JSC::DFG::::~AbstractInterpreter):
+        (JSC::DFG::::booleanResult):
+        (JSC::DFG::::startExecuting):
+        (JSC::DFG::::executeEdges):
+        (JSC::DFG::::verifyEdge):
+        (JSC::DFG::::verifyEdges):
+        (JSC::DFG::::executeEffects):
+        (JSC::DFG::::execute):
+        (JSC::DFG::::clobberWorld):
+        (JSC::DFG::::clobberCapturedVars):
+        (JSC::DFG::::clobberStructures):
+        (JSC::DFG::::dump):
+        (JSC::DFG::::filter):
+        (JSC::DFG::::filterArrayModes):
+        (JSC::DFG::::filterByValue):
+        * dfg/DFGAbstractState.cpp: Removed.
+        * dfg/DFGAbstractState.h: Removed.
+        * dfg/DFGArgumentsSimplificationPhase.cpp:
+        * dfg/DFGCFAPhase.cpp:
+        (JSC::DFG::CFAPhase::CFAPhase):
+        (JSC::DFG::CFAPhase::performBlockCFA):
+        (CFAPhase):
+        * dfg/DFGCFGSimplificationPhase.cpp:
+        * dfg/DFGConstantFoldingPhase.cpp:
+        (JSC::DFG::ConstantFoldingPhase::ConstantFoldingPhase):
+        (JSC::DFG::ConstantFoldingPhase::foldConstants):
+        (ConstantFoldingPhase):
+        * dfg/DFGInPlaceAbstractState.cpp: Added.
+        (DFG):
+        (JSC::DFG::InPlaceAbstractState::InPlaceAbstractState):
+        (JSC::DFG::InPlaceAbstractState::~InPlaceAbstractState):
+        (JSC::DFG::InPlaceAbstractState::beginBasicBlock):
+        (JSC::DFG::setLiveValues):
+        (JSC::DFG::InPlaceAbstractState::initialize):
+        (JSC::DFG::InPlaceAbstractState::endBasicBlock):
+        (JSC::DFG::InPlaceAbstractState::reset):
+        (JSC::DFG::InPlaceAbstractState::mergeStateAtTail):
+        (JSC::DFG::InPlaceAbstractState::merge):
+        (JSC::DFG::InPlaceAbstractState::mergeToSuccessors):
+        (JSC::DFG::InPlaceAbstractState::mergeVariableBetweenBlocks):
+        * dfg/DFGInPlaceAbstractState.h: Added.
+        (DFG):
+        (InPlaceAbstractState):
+        (JSC::DFG::InPlaceAbstractState::forNode):
+        (JSC::DFG::InPlaceAbstractState::variables):
+        (JSC::DFG::InPlaceAbstractState::block):
+        (JSC::DFG::InPlaceAbstractState::didClobber):
+        (JSC::DFG::InPlaceAbstractState::isValid):
+        (JSC::DFG::InPlaceAbstractState::setDidClobber):
+        (JSC::DFG::InPlaceAbstractState::setIsValid):
+        (JSC::DFG::InPlaceAbstractState::setBranchDirection):
+        (JSC::DFG::InPlaceAbstractState::setFoundConstants):
+        (JSC::DFG::InPlaceAbstractState::haveStructures):
+        (JSC::DFG::InPlaceAbstractState::setHaveStructures):
+        * dfg/DFGMergeMode.h: Added.
+        (DFG):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::SpeculativeJIT):
+        (JSC::DFG::SpeculativeJIT::backwardTypeCheck):
+        (JSC::DFG::SpeculativeJIT::compileCurrentBlock):
+        (JSC::DFG::SpeculativeJIT::compileToStringOnCell):
+        (JSC::DFG::SpeculativeJIT::speculateStringIdentAndLoadStorage):
+        (JSC::DFG::SpeculativeJIT::speculateStringObject):
+        (JSC::DFG::SpeculativeJIT::speculateStringOrStringObject):
+        * dfg/DFGSpeculativeJIT.h:
+        (JSC::DFG::SpeculativeJIT::needsTypeCheck):
+        (SpeculativeJIT):
+        * dfg/DFGSpeculativeJIT32_64.cpp:
+        (JSC::DFG::SpeculativeJIT::fillSpeculateIntInternal):
+        (JSC::DFG::SpeculativeJIT::fillSpeculateDouble):
+        (JSC::DFG::SpeculativeJIT::fillSpeculateCell):
+        (JSC::DFG::SpeculativeJIT::fillSpeculateBoolean):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::fillSpeculateIntInternal):
+        (JSC::DFG::SpeculativeJIT::fillSpeculateDouble):
+        (JSC::DFG::SpeculativeJIT::fillSpeculateCell):
+        (JSC::DFG::SpeculativeJIT::fillSpeculateBoolean):
+        * ftl/FTLLowerDFGToLLVM.cpp:
+        (FTL):
+        (JSC::FTL::LowerDFGToLLVM::LowerDFGToLLVM):
+        (JSC::FTL::LowerDFGToLLVM::compileNode):
+        (JSC::FTL::LowerDFGToLLVM::appendTypeCheck):
+        (JSC::FTL::LowerDFGToLLVM::speculate):
+        (JSC::FTL::LowerDFGToLLVM::speculateNumber):
+        (JSC::FTL::LowerDFGToLLVM::speculateRealNumber):
+        (LowerDFGToLLVM):
+
+2013-07-18  Filip Pizlo  <fpizlo@apple.com>
+
         fourthTier: DFG shouldn't create CheckStructures for array accesses except if the ArrayMode implies an original array access
         https://bugs.webkit.org/show_bug.cgi?id=118867
 
index 0d1cca2..4d2b8c7 100644 (file)
                0F620174143FCD330068B77C /* DFGVariableAccessData.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F620172143FCD2F0068B77C /* DFGVariableAccessData.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F620176143FCD3B0068B77C /* DFGBasicBlock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F620170143FCD2F0068B77C /* DFGBasicBlock.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F620177143FCD3F0068B77C /* DFGAbstractValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F62016F143FCD2F0068B77C /* DFGAbstractValue.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               0F620178143FCD440068B77C /* DFGAbstractState.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F62016E143FCD2F0068B77C /* DFGAbstractState.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               0F620179143FCD480068B77C /* DFGAbstractState.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F62016D143FCD2F0068B77C /* DFGAbstractState.cpp */; };
                0F63943F15C75F19006A597C /* DFGTypeCheckHoistingPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F63943D15C75F14006A597C /* DFGTypeCheckHoistingPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F63944015C75F1D006A597C /* DFGTypeCheckHoistingPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F63943C15C75F14006A597C /* DFGTypeCheckHoistingPhase.cpp */; };
                0F63945415D07055006A597C /* ArrayProfile.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F63945115D07051006A597C /* ArrayProfile.cpp */; };
                A1712B3B11C7B212007A5315 /* RegExpCache.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A1712B3A11C7B212007A5315 /* RegExpCache.cpp */; };
                A1712B3F11C7B228007A5315 /* RegExpCache.h in Headers */ = {isa = PBXBuildFile; fileRef = A1712B3E11C7B228007A5315 /* RegExpCache.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A1712B4111C7B235007A5315 /* RegExpKey.h in Headers */ = {isa = PBXBuildFile; fileRef = A1712B4011C7B235007A5315 /* RegExpKey.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A704D90317A0BAA8006BA554 /* DFGAbstractInterpreter.h in Headers */ = {isa = PBXBuildFile; fileRef = A704D8FE17A0BAA8006BA554 /* DFGAbstractInterpreter.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A704D90417A0BAA8006BA554 /* DFGAbstractInterpreterInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = A704D8FF17A0BAA8006BA554 /* DFGAbstractInterpreterInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A704D90517A0BAA8006BA554 /* DFGInPlaceAbstractState.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A704D90017A0BAA8006BA554 /* DFGInPlaceAbstractState.cpp */; };
+               A704D90617A0BAA8006BA554 /* DFGInPlaceAbstractState.h in Headers */ = {isa = PBXBuildFile; fileRef = A704D90117A0BAA8006BA554 /* DFGInPlaceAbstractState.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A704D90717A0BAA8006BA554 /* DFGMergeMode.h in Headers */ = {isa = PBXBuildFile; fileRef = A704D90217A0BAA8006BA554 /* DFGMergeMode.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A709F2F017A0AC0400512E98 /* SlowPathCall.h in Headers */ = {isa = PBXBuildFile; fileRef = A709F2EF17A0AC0400512E98 /* SlowPathCall.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A709F2F217A0AC2A00512E98 /* CommonSlowPaths.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A709F2F117A0AC2A00512E98 /* CommonSlowPaths.cpp */; };
                A70B083217A0B79B00DAF14B /* DFGBinarySwitch.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A70B083017A0B79B00DAF14B /* DFGBinarySwitch.cpp */; };
                0F5EF91B16878F78003E5C25 /* JITThunks.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JITThunks.cpp; sourceTree = "<group>"; };
                0F5EF91C16878F78003E5C25 /* JITThunks.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JITThunks.h; sourceTree = "<group>"; };
                0F5F08CE146C762F000472A9 /* UnconditionalFinalizer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UnconditionalFinalizer.h; sourceTree = "<group>"; };
-               0F62016D143FCD2F0068B77C /* DFGAbstractState.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGAbstractState.cpp; path = dfg/DFGAbstractState.cpp; sourceTree = "<group>"; };
-               0F62016E143FCD2F0068B77C /* DFGAbstractState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAbstractState.h; path = dfg/DFGAbstractState.h; sourceTree = "<group>"; };
                0F62016F143FCD2F0068B77C /* DFGAbstractValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAbstractValue.h; path = dfg/DFGAbstractValue.h; sourceTree = "<group>"; };
                0F620170143FCD2F0068B77C /* DFGBasicBlock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBasicBlock.h; path = dfg/DFGBasicBlock.h; sourceTree = "<group>"; };
                0F620172143FCD2F0068B77C /* DFGVariableAccessData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGVariableAccessData.h; path = dfg/DFGVariableAccessData.h; sourceTree = "<group>"; };
                A1712B3A11C7B212007A5315 /* RegExpCache.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RegExpCache.cpp; sourceTree = "<group>"; };
                A1712B3E11C7B228007A5315 /* RegExpCache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RegExpCache.h; sourceTree = "<group>"; };
                A1712B4011C7B235007A5315 /* RegExpKey.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RegExpKey.h; sourceTree = "<group>"; };
+               A704D8FE17A0BAA8006BA554 /* DFGAbstractInterpreter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAbstractInterpreter.h; path = dfg/DFGAbstractInterpreter.h; sourceTree = "<group>"; };
+               A704D8FF17A0BAA8006BA554 /* DFGAbstractInterpreterInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAbstractInterpreterInlines.h; path = dfg/DFGAbstractInterpreterInlines.h; sourceTree = "<group>"; };
+               A704D90017A0BAA8006BA554 /* DFGInPlaceAbstractState.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGInPlaceAbstractState.cpp; path = dfg/DFGInPlaceAbstractState.cpp; sourceTree = "<group>"; };
+               A704D90117A0BAA8006BA554 /* DFGInPlaceAbstractState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGInPlaceAbstractState.h; path = dfg/DFGInPlaceAbstractState.h; sourceTree = "<group>"; };
+               A704D90217A0BAA8006BA554 /* DFGMergeMode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGMergeMode.h; path = dfg/DFGMergeMode.h; sourceTree = "<group>"; };
                A709F2EF17A0AC0400512E98 /* SlowPathCall.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SlowPathCall.h; sourceTree = "<group>"; };
                A709F2F117A0AC2A00512E98 /* CommonSlowPaths.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CommonSlowPaths.cpp; sourceTree = "<group>"; };
                A70B083017A0B79B00DAF14B /* DFGBinarySwitch.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBinarySwitch.cpp; path = dfg/DFGBinarySwitch.cpp; sourceTree = "<group>"; };
                034768DFFF38A50411DB9C8B /* Products */ = {
                        isa = PBXGroup;
                        children = (
-                               0FF922CF14F46B130041A24E /* JSCLLIntOffsetsExtractor */,
                                932F5BD90822A1C700736975 /* JavaScriptCore.framework */,
                                932F5BE10822A1C700736975 /* jsc */,
+                               0FF922CF14F46B130041A24E /* JSCLLIntOffsetsExtractor */,
                                141211200A48793C00480255 /* minidom */,
                                14BD59BF0A3E8F9000BAF59C /* testapi */,
                                6511230514046A4C002B101D /* testRegExp */,
                86EC9DB31328DF44002B2AD7 /* dfg */ = {
                        isa = PBXGroup;
                        children = (
-                               0F62016D143FCD2F0068B77C /* DFGAbstractState.cpp */,
-                               0F62016E143FCD2F0068B77C /* DFGAbstractState.h */,
+                               A704D8FE17A0BAA8006BA554 /* DFGAbstractInterpreter.h */,
+                               A704D8FF17A0BAA8006BA554 /* DFGAbstractInterpreterInlines.h */,
                                0F55C19317276E4600CEABFD /* DFGAbstractValue.cpp */,
                                0F62016F143FCD2F0068B77C /* DFGAbstractValue.h */,
                                0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */,
                                86AE6C4C136A11E400963012 /* DFGGPRInfo.h */,
                                86EC9DB71328DF82002B2AD7 /* DFGGraph.cpp */,
                                86EC9DB81328DF82002B2AD7 /* DFGGraph.h */,
+                               A704D90017A0BAA8006BA554 /* DFGInPlaceAbstractState.cpp */,
+                               A704D90117A0BAA8006BA554 /* DFGInPlaceAbstractState.h */,
                                0F2BDC1F151E803800CD8910 /* DFGInsertionSet.h */,
                                0FEA0A2F170D40BF00BB722C /* DFGJITCode.cpp */,
                                0FEA0A30170D40BF00BB722C /* DFGJITCode.h */,
                                0FB4B51D16B62772003F696B /* DFGLongLivedState.h */,
                                A767B5B317A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.cpp */,
                                A767B5B417A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.h */,
+                               A704D90217A0BAA8006BA554 /* DFGMergeMode.h */,
                                0F2BDC3D1522801700CD8910 /* DFGMinifiedGraph.h */,
                                0FB4B51016B3A964003F696B /* DFGMinifiedID.h */,
                                0F2BDC4C1522818300CD8910 /* DFGMinifiedNode.cpp */,
                                BC3135640F302FA3003DFD3A /* DebuggerActivation.h in Headers */,
                                BC18C3FB0E16F5CD00B34460 /* DebuggerCallFrame.h in Headers */,
                                0F136D4D174AD69E0075B354 /* DeferGC.h in Headers */,
-                               0F620178143FCD440068B77C /* DFGAbstractState.h in Headers */,
+                               A704D90317A0BAA8006BA554 /* DFGAbstractInterpreter.h in Headers */,
+                               A704D90417A0BAA8006BA554 /* DFGAbstractInterpreterInlines.h in Headers */,
                                0F620177143FCD3F0068B77C /* DFGAbstractValue.h in Headers */,
                                0F66E16B14DF3F1600B7B2E4 /* DFGAdjacencyList.h in Headers */,
                                0FFB921816D02EB20055A5DB /* DFGAllocator.h in Headers */,
                                86EC9DC61328DF82002B2AD7 /* DFGGenerationInfo.h in Headers */,
                                86AE6C4E136A11E400963012 /* DFGGPRInfo.h in Headers */,
                                86EC9DC81328DF82002B2AD7 /* DFGGraph.h in Headers */,
+                               A704D90617A0BAA8006BA554 /* DFGInPlaceAbstractState.h in Headers */,
                                0F2BDC21151E803B00CD8910 /* DFGInsertionSet.h in Headers */,
                                0FEA0A34170D40BF00BB722C /* DFGJITCode.h in Headers */,
                                86EC9DCC1328DF82002B2AD7 /* DFGJITCompiler.h in Headers */,
                                A7D89CFC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h in Headers */,
                                0FF0F19B16B729FA005DF95B /* DFGLongLivedState.h in Headers */,
                                A767B5B617A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.h in Headers */,
+                               A704D90717A0BAA8006BA554 /* DFGMergeMode.h in Headers */,
                                0F2BDC451522801B00CD8910 /* DFGMinifiedGraph.h in Headers */,
                                0F2E892D16D02BAF009E4FD2 /* DFGMinifiedID.h in Headers */,
                                0F2BDC461522802000CD8910 /* DFGMinifiedNode.h in Headers */,
                                14280823107EC02C0013E7B2 /* Debugger.cpp in Sources */,
                                BC3135650F302FA3003DFD3A /* DebuggerActivation.cpp in Sources */,
                                149559EE0DDCDDF700648087 /* DebuggerCallFrame.cpp in Sources */,
-                               0F620179143FCD480068B77C /* DFGAbstractState.cpp in Sources */,
                                0F55C19417276E4600CEABFD /* DFGAbstractValue.cpp in Sources */,
                                0F16015D156198C900C2587C /* DFGArgumentsSimplificationPhase.cpp in Sources */,
                                0F63948415E48118006A597C /* DFGArrayMode.cpp in Sources */,
                                A7D89CF717A0B8CC00773AD8 /* DFGFlushFormat.cpp in Sources */,
                                A7D89CF917A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.cpp in Sources */,
                                86EC9DC71328DF82002B2AD7 /* DFGGraph.cpp in Sources */,
+                               A704D90517A0BAA8006BA554 /* DFGInPlaceAbstractState.cpp in Sources */,
                                0FEA0A33170D40BF00BB722C /* DFGJITCode.cpp in Sources */,
                                86EC9DCB1328DF82002B2AD7 /* DFGJITCompiler.cpp in Sources */,
                                A78A9778179738B8009DF744 /* DFGJITFinalizer.cpp in Sources */,
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2012, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013 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,8 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#ifndef DFGAbstractState_h
-#define DFGAbstractState_h
+#ifndef DFGAbstractInterpreter_h
+#define DFGAbstractInterpreter_h
 
 #include <wtf/Platform.h>
 
 #include "DFGBranchDirection.h"
 #include "DFGGraph.h"
 #include "DFGNode.h"
-#include <wtf/Vector.h>
 
-namespace JSC {
+namespace JSC { namespace DFG {
 
-class CodeBlock;
-
-namespace DFG {
-
-struct BasicBlock;
-
-// This implements the notion of an abstract state for flow-sensitive intraprocedural
-// control flow analysis (CFA), with a focus on the elimination of redundant type checks.
-// It also implements most of the mechanisms of abstract interpretation that such an
-// analysis would use. This class should be used in two idioms:
-//
-// 1) Performing the CFA. In this case, AbstractState should be run over all basic
-//    blocks repeatedly until convergence is reached. Convergence is defined by
-//    endBasicBlock(AbstractState::MergeToSuccessors) returning false for all blocks.
-//
-// 2) Rematerializing the results of a previously executed CFA. In this case,
-//    AbstractState should be run over whatever basic block you're interested in up
-//    to the point of the node at which you'd like to interrogate the known type
-//    of all other nodes. At this point it's safe to discard the AbstractState entirely,
-//    call reset(), or to run it to the end of the basic block and call
-//    endBasicBlock(AbstractState::DontMerge). The latter option is safest because
-//    it performs some useful integrity checks.
-//
-// After the CFA is run, the inter-block state is saved at the heads and tails of all
-// basic blocks. This allows the intra-block state to be rematerialized by just
-// executing the CFA for that block. If you need to know inter-block state only, then
-// you only need to examine the BasicBlock::m_valuesAtHead or m_valuesAtTail fields.
-//
-// Running this analysis involves the following, modulo the inter-block state
-// merging and convergence fixpoint:
-//
-// AbstractState state(codeBlock, graph);
-// state.beginBasicBlock(basicBlock);
-// bool endReached = true;
-// for (unsigned i = 0; i < basicBlock->size(); ++i) {
-//     if (!state.execute(i))
-//         break;
-// }
-// bool result = state.endBasicBlock(<either Merge or DontMerge>);
-
-class AbstractState {
+template<typename AbstractStateType>
+class AbstractInterpreter {
 public:
-    enum MergeMode {
-        // Don't merge the state in AbstractState with basic blocks.
-        DontMerge,
-        
-        // Merge the state in AbstractState with the tail of the basic
-        // block being analyzed.
-        MergeToTail,
-        
-        // Merge the state in AbstractState with the tail of the basic
-        // block, and with the heads of successor blocks.
-        MergeToSuccessors
-    };
-    
-    AbstractState(Graph&);
-    
-    ~AbstractState();
+    AbstractInterpreter(Graph&, AbstractStateType& state);
+    ~AbstractInterpreter();
     
     AbstractValue& forNode(Node* node)
     {
-        return node->value;
+        return m_state.forNode(node);
     }
     
     AbstractValue& forNode(Edge edge)
@@ -109,7 +55,7 @@ public:
     
     Operands<AbstractValue>& variables()
     {
-        return m_variables;
+        return m_state.variables();
     }
     
     bool needsTypeCheck(Node* node, SpeculatedType typesPassedThrough)
@@ -127,45 +73,6 @@ public:
         return needsTypeCheck(edge, typeFilterFor(edge.useKind()));
     }
     
-    // Call this before beginning CFA to initialize the abstract values of
-    // arguments, and to indicate which blocks should be listed for CFA
-    // execution.
-    void initialize();
-
-    // Start abstractly executing the given basic block. Initializes the
-    // notion of abstract state to what we believe it to be at the head
-    // of the basic block, according to the basic block's data structures.
-    // This method also sets cfaShouldRevisit to false.
-    void beginBasicBlock(BasicBlock*);
-    
-    // Finish abstractly executing a basic block. If MergeToTail or
-    // MergeToSuccessors is passed, then this merges everything we have
-    // learned about how the state changes during this block's execution into
-    // the block's data structures. There are three return modes, depending
-    // on the value of mergeMode:
-    //
-    // DontMerge:
-    //    Always returns false.
-    //
-    // MergeToTail:
-    //    Returns true if the state of the block at the tail was changed.
-    //    This means that you must call mergeToSuccessors(), and if that
-    //    returns true, then you must revisit (at least) the successor
-    //    blocks. False will always be returned if the block is terminal
-    //    (i.e. ends in Throw or Return, or has a ForceOSRExit inside it).
-    //
-    // MergeToSuccessors:
-    //    Returns true if the state of the block at the tail was changed,
-    //    and, if the state at the heads of successors was changed.
-    //    A true return means that you must revisit (at least) the successor
-    //    blocks. This also sets cfaShouldRevisit to true for basic blocks
-    //    that must be visited next.
-    bool endBasicBlock(MergeMode);
-    
-    // Reset the AbstractState. This throws away any results, and at this point
-    // you can safely call beginBasicBlock() on any basic block.
-    void reset();
-    
     // Abstractly executes the given node. The new abstract state is stored into an
     // abstract stack stored in *this. Loads of local variables (that span
     // basic blocks) interrogate the basic block's notion of the state at the head.
@@ -209,26 +116,6 @@ public:
     bool executeEffects(unsigned indexInBlock);
     bool executeEffects(unsigned indexInBlock, Node*);
     
-    // Did the last executed node clobber the world?
-    bool didClobber() const { return m_didClobber; }
-    
-    // Is the execution state still valid? This will be false if execute() has
-    // returned false previously.
-    bool isValid() const { return m_isValid; }
-    
-    // Merge the abstract state stored at the first block's tail into the second
-    // block's head. Returns true if the second block's state changed. If so,
-    // that block must be abstractly interpreted again. This also sets
-    // to->cfaShouldRevisit to true, if it returns true, or if to has not been
-    // visited yet.
-    bool merge(BasicBlock* from, BasicBlock* to);
-    
-    // Merge the abstract state stored at the block's tail into all of its
-    // successors. Returns true if any of the successors' states changed. Note
-    // that this is automatically called in endBasicBlock() if MergeMode is
-    // MergeToSuccessors.
-    bool mergeToSuccessors(BasicBlock*);
-    
     void dump(PrintStream& out);
     
     template<typename T>
@@ -265,10 +152,6 @@ private:
     void clobberCapturedVars(const CodeOrigin&);
     void clobberStructures(unsigned indexInBlock);
     
-    bool mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*);
-    
-    static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);
-    
     enum BooleanResult {
         UnknownBooleanResult,
         DefinitelyFalse,
@@ -310,22 +193,12 @@ private:
     
     CodeBlock* m_codeBlock;
     Graph& m_graph;
-    
-    Operands<AbstractValue> m_variables;
-    BasicBlock* m_block;
-    
-    bool m_haveStructures;
-    bool m_foundConstants;
-    
-    bool m_isValid;
-    bool m_didClobber;
-    
-    BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true).
+    AbstractStateType& m_state;
 };
 
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
 
-#endif // DFGAbstractState_h
+#endif // DFGAbstractInterpreter_h
 
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2012, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#include "config.h"
-#include "DFGAbstractState.h"
+#ifndef DFGAbstractInterpreterInlines_h
+#define DFGAbstractInterpreterInlines_h
+
+#include <wtf/Platform.h>
 
 #if ENABLE(DFG_JIT)
 
-#include "CodeBlock.h"
-#include "DFGBasicBlock.h"
+#include "DFGAbstractInterpreter.h"
 #include "GetByIdStatus.h"
 #include "Operations.h"
 #include "PutByIdStatus.h"
 
 namespace JSC { namespace DFG {
 
-AbstractState::AbstractState(Graph& graph)
+template<typename AbstractStateType>
+AbstractInterpreter<AbstractStateType>::AbstractInterpreter(Graph& graph, AbstractStateType& state)
     : m_codeBlock(graph.m_codeBlock)
     , m_graph(graph)
-    , m_variables(m_codeBlock->numParameters(), graph.m_localVars)
-    , m_block(0)
-{
-}
-
-AbstractState::~AbstractState() { }
-
-void AbstractState::beginBasicBlock(BasicBlock* basicBlock)
+    , m_state(state)
 {
-    ASSERT(!m_block);
-    
-    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
-    ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
-    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
-    
-    for (size_t i = 0; i < basicBlock->size(); i++)
-        forNode(basicBlock->at(i)).clear();
-
-    m_variables = basicBlock->valuesAtHead;
-    m_haveStructures = false;
-    for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
-        if (m_variables.argument(i).hasClobberableState()) {
-            m_haveStructures = true;
-            break;
-        }
-    }
-    for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
-        if (m_variables.local(i).hasClobberableState()) {
-            m_haveStructures = true;
-            break;
-        }
-    }
-    
-    if (m_graph.m_form == SSA) {
-        HashMap<Node*, AbstractValue>::iterator iter = basicBlock->ssa->valuesAtHead.begin();
-        HashMap<Node*, AbstractValue>::iterator end = basicBlock->ssa->valuesAtHead.end();
-        for (; iter != end; ++iter) {
-            forNode(iter->key) = iter->value;
-            if (iter->value.hasClobberableState())
-                m_haveStructures = true;
-        }
-    }
-    
-    basicBlock->cfaShouldRevisit = false;
-    basicBlock->cfaHasVisited = true;
-    m_block = basicBlock;
-    m_isValid = true;
-    m_foundConstants = false;
-    m_branchDirection = InvalidBranchDirection;
 }
 
-static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
+template<typename AbstractStateType>
+AbstractInterpreter<AbstractStateType>::~AbstractInterpreter()
 {
-    values.clear();
-    
-    HashSet<Node*>::iterator iter = live.begin();
-    HashSet<Node*>::iterator end = live.end();
-    for (; iter != end; ++iter)
-        values.add(*iter, AbstractValue());
 }
 
-void AbstractState::initialize()
-{
-    BasicBlock* root = m_graph.block(0);
-    root->cfaShouldRevisit = true;
-    root->cfaHasVisited = false;
-    root->cfaFoundConstants = false;
-    for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
-        if (m_graph.m_form == SSA) {
-            root->valuesAtHead.argument(i).makeTop();
-            continue;
-        }
-        
-        Node* node = root->variablesAtHead.argument(i);
-        ASSERT(node->op() == SetArgument);
-        if (!node->variableAccessData()->shouldUnboxIfPossible()) {
-            root->valuesAtHead.argument(i).makeTop();
-            continue;
-        }
-        
-        SpeculatedType prediction =
-            node->variableAccessData()->argumentAwarePrediction();
-        if (isInt32Speculation(prediction))
-            root->valuesAtHead.argument(i).setType(SpecInt32);
-        else if (isBooleanSpeculation(prediction))
-            root->valuesAtHead.argument(i).setType(SpecBoolean);
-        else if (isCellSpeculation(prediction))
-            root->valuesAtHead.argument(i).setType(SpecCell);
-        else
-            root->valuesAtHead.argument(i).makeTop();
-        
-        root->valuesAtTail.argument(i).clear();
-    }
-    for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
-        Node* node = root->variablesAtHead.local(i);
-        if (node && node->variableAccessData()->isCaptured())
-            root->valuesAtHead.local(i).makeTop();
-        else
-            root->valuesAtHead.local(i).clear();
-        root->valuesAtTail.local(i).clear();
-    }
-    for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
-        BasicBlock* block = m_graph.block(blockIndex);
-        if (!block)
-            continue;
-        ASSERT(block->isReachable);
-        block->cfaShouldRevisit = false;
-        block->cfaHasVisited = false;
-        block->cfaFoundConstants = false;
-        for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
-            block->valuesAtHead.argument(i).clear();
-            block->valuesAtTail.argument(i).clear();
-        }
-        for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
-            block->valuesAtHead.local(i).clear();
-            block->valuesAtTail.local(i).clear();
-        }
-        if (!block->isOSRTarget)
-            continue;
-        if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
-            continue;
-        for (size_t i = 0; i < m_graph.m_plan.mustHandleValues.size(); ++i) {
-            AbstractValue value;
-            value.setMostSpecific(m_graph, m_graph.m_plan.mustHandleValues[i]);
-            int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i);
-            block->valuesAtHead.operand(operand).merge(value);
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-            dataLogF("    Initializing Block #%u, operand r%d, to ", blockIndex, operand);
-            block->valuesAtHead.operand(operand).dump(WTF::dataFile());
-            dataLogF("\n");
-#endif
-        }
-        block->cfaShouldRevisit = true;
-    }
-    if (m_graph.m_form == SSA) {
-        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
-            BasicBlock* block = m_graph.block(blockIndex);
-            if (!block)
-                continue;
-            setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
-            setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
-        }
-    }
-}
-
-bool AbstractState::endBasicBlock(MergeMode mergeMode)
-{
-    ASSERT(m_block);
-    
-    BasicBlock* block = m_block; // Save the block for successor merging.
-    
-    block->cfaFoundConstants = m_foundConstants;
-    block->cfaDidFinish = m_isValid;
-    block->cfaBranchDirection = m_branchDirection;
-    
-    if (!m_isValid) {
-        reset();
-        return false;
-    }
-    
-    bool changed = false;
-    
-    if (mergeMode != DontMerge || !ASSERT_DISABLED) {
-        switch (m_graph.m_form) {
-        case ThreadedCPS: {
-            for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-                dataLogF("        Merging state for argument %zu.\n", argument);
-#endif
-                AbstractValue& destination = block->valuesAtTail.argument(argument);
-                changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
-            }
-            
-            for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-                dataLogF("        Merging state for local %zu.\n", local);
-#endif
-                AbstractValue& destination = block->valuesAtTail.local(local);
-                changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
-            }
-            break;
-        }
-            
-        case SSA: {
-            for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
-                changed |= block->valuesAtTail[i].merge(m_variables[i]);
-            
-            HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
-            HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
-            for (; iter != end; ++iter) {
-                Node* node = *iter;
-                changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
-            }
-            break;
-        }
-            
-        default:
-            RELEASE_ASSERT_NOT_REACHED();
-        }
-    }
-    
-    ASSERT(mergeMode != DontMerge || !changed);
-    
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-    dataLogF("        Branch direction = %s\n", branchDirectionToString(m_branchDirection));
-#endif
-    
-    reset();
-    
-    if (mergeMode != MergeToSuccessors)
-        return changed;
-    
-    return mergeToSuccessors(block);
-}
-
-void AbstractState::reset()
-{
-    m_block = 0;
-    m_isValid = false;
-    m_branchDirection = InvalidBranchDirection;
-}
-
-AbstractState::BooleanResult AbstractState::booleanResult(Node* node, AbstractValue& value)
+template<typename AbstractStateType>
+typename AbstractInterpreter<AbstractStateType>::BooleanResult
+AbstractInterpreter<AbstractStateType>::booleanResult(
+    Node* node, AbstractValue& value)
 {
     JSValue childConst = value.value();
     if (childConst) {
@@ -283,44 +75,51 @@ AbstractState::BooleanResult AbstractState::booleanResult(Node* node, AbstractVa
     return UnknownBooleanResult;
 }
 
-bool AbstractState::startExecuting(Node* node)
+template<typename AbstractStateType>
+bool AbstractInterpreter<AbstractStateType>::startExecuting(Node* node)
 {
-    ASSERT(m_block);
-    ASSERT(m_isValid);
+    ASSERT(m_state.block());
+    ASSERT(m_state.isValid());
     
-    m_didClobber = false;
+    m_state.setDidClobber(false);
     
     node->setCanExit(false);
     
     return node->shouldGenerate();
 }
 
-bool AbstractState::startExecuting(unsigned indexInBlock)
+template<typename AbstractStateType>
+bool AbstractInterpreter<AbstractStateType>::startExecuting(unsigned indexInBlock)
 {
-    return startExecuting(m_block->at(indexInBlock));
+    return startExecuting(m_state.block()->at(indexInBlock));
 }
 
-void AbstractState::executeEdges(Node* node)
+template<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::executeEdges(Node* node)
 {
     DFG_NODE_DO_TO_CHILDREN(m_graph, node, filterEdgeByUse);
 }
 
-void AbstractState::executeEdges(unsigned indexInBlock)
+template<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::executeEdges(unsigned indexInBlock)
 {
-    executeEdges(m_block->at(indexInBlock));
+    executeEdges(m_state.block()->at(indexInBlock));
 }
 
-void AbstractState::verifyEdge(Node*, Edge edge)
+template<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::verifyEdge(Node*, Edge edge)
 {
     RELEASE_ASSERT(!(forNode(edge).m_type & ~typeFilterFor(edge.useKind())));
 }
 
-void AbstractState::verifyEdges(Node* node)
+template<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::verifyEdges(Node* node)
 {
     DFG_NODE_DO_TO_CHILDREN(m_graph, node, verifyEdge);
 }
 
-bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
+template<typename AbstractStateType>
+bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned indexInBlock, Node* node)
 {
     if (!ASSERT_DISABLED)
         verifyEdges(node);
@@ -341,7 +140,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
     case GetArgument: {
         ASSERT(m_graph.m_form == SSA);
         VariableAccessData* variable = node->variableAccessData();
-        AbstractValue& value = m_variables.operand(variable->local());
+        AbstractValue& value = m_state.variables().operand(variable->local());
         ASSERT(value.isTop());
         FiltrationResult result =
             value.filter(typeFilterFor(useKindFor(variable->flushFormat())));
@@ -353,30 +152,30 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
     case GetLocal: {
         VariableAccessData* variableAccessData = node->variableAccessData();
         if (variableAccessData->prediction() == SpecNone) {
-            m_isValid = false;
+            m_state.setIsValid(false);
             break;
         }
-        AbstractValue value = m_variables.operand(variableAccessData->local());
+        AbstractValue value = m_state.variables().operand(variableAccessData->local());
         if (!variableAccessData->isCaptured()) {
             if (value.isClear())
                 node->setCanExit(true);
         }
         if (value.value())
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
         forNode(node) = value;
         break;
     }
         
     case GetLocalUnlinked: {
-        AbstractValue value = m_variables.operand(node->unlinkedLocal());
+        AbstractValue value = m_state.variables().operand(node->unlinkedLocal());
         if (value.value())
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
         forNode(node) = value;
         break;
     }
         
     case SetLocal: {
-        m_variables.operand(node->local()) = forNode(node->child1());
+        m_state.variables().operand(node->local()) = forNode(node->child1());
         break;
     }
         
@@ -394,7 +193,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
             
     case SetArgument:
         // Assert that the state of arguments has been set.
-        ASSERT(!m_block->valuesAtHead.operand(node->local()).isClear());
+        ASSERT(!m_state.block()->valuesAtHead.operand(node->local()).isClear());
         break;
             
     case BitAnd:
@@ -433,7 +232,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
                 constantWasSet = false;
             }
             if (constantWasSet) {
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         }
@@ -446,7 +245,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         if (child && child.isNumber()) {
             ASSERT(child.isInt32());
             if (trySetConstant(node, JSValue(child.asUInt32()))) {
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         }
@@ -466,7 +265,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
             int32_t asInt = JSC::toInt32(asDouble);
             if (bitwise_cast<int64_t>(static_cast<double>(asInt)) == bitwise_cast<int64_t>(asDouble)
                 && trySetConstant(node, JSValue(asInt))) {
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         }
@@ -484,7 +283,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
             else
                 constantWasSet = trySetConstant(node, JSValue(JSC::toInt32(child.asDouble())));
             if (constantWasSet) {
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         }
@@ -498,7 +297,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         JSValue child = forNode(node->child1()).value();
         if (child && child.isNumber()
             && trySetConstant(node, JSValue(JSValue::EncodeAsDouble, child.asNumber()))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         if (isInt32Speculation(forNode(node->child1()).m_type))
@@ -514,7 +313,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         JSValue right = forNode(node->child2()).value();
         if (left && right && left.isNumber() && right.isNumber()
             && trySetConstant(node, JSValue(left.asNumber() + right.asNumber()))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         switch (node->binaryUseKind()) {
@@ -549,7 +348,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         JSValue right = forNode(node->child2()).value();
         if (left && right && left.isNumber() && right.isNumber()
             && trySetConstant(node, JSValue(left.asNumber() - right.asNumber()))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         switch (node->binaryUseKind()) {
@@ -572,7 +371,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         JSValue child = forNode(node->child1()).value();
         if (child && child.isNumber()
             && trySetConstant(node, JSValue(-child.asNumber()))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         switch (node->child1().useKind()) {
@@ -596,7 +395,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         JSValue right = forNode(node->child2()).value();
         if (left && right && left.isNumber() && right.isNumber()
             && trySetConstant(node, JSValue(left.asNumber() * right.asNumber()))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         switch (node->binaryUseKind()) {
@@ -633,7 +432,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         JSValue right = forNode(node->child2()).value();
         if (node->op() == ArithMod && right && right.isNumber() && right.asNumber() == 1
             && trySetConstant(node, JSValue(0))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         if (left && right && left.isNumber() && right.isNumber()) {
@@ -659,7 +458,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
                 break;
             }
             if (constantWasSet) {
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         }
@@ -682,7 +481,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         JSValue child = forNode(node->child1()).value();
         if (child && child.isNumber()
             && trySetConstant(node, JSValue(fabs(child.asNumber())))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         switch (node->child1().useKind()) {
@@ -704,7 +503,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         JSValue child = forNode(node->child1()).value();
         if (child && child.isNumber()
             && trySetConstant(node, JSValue(sqrt(child.asNumber())))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         forNode(node).setType(SpecDouble);
@@ -724,7 +523,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
             break;
         }
         if (didSetConstant) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         switch (node->child1().useKind()) {
@@ -782,7 +581,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
                 break;
             }
             if (constantWasSet) {
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         }
@@ -798,37 +597,37 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         if (child) {
             JSValue typeString = jsTypeStringForValue(*vm, m_codeBlock->globalObjectFor(node->codeOrigin), child);
             if (trySetConstant(node, typeString)) {
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         } else if (isNumberSpeculation(abstractChild.m_type)) {
             if (trySetConstant(node, vm->smallStrings.numberString())) {
                 filter(node->child1(), SpecNumber);
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         } else if (isStringSpeculation(abstractChild.m_type)) {
             if (trySetConstant(node, vm->smallStrings.stringString())) {
                 filter(node->child1(), SpecString);
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         } else if (isFinalObjectSpeculation(abstractChild.m_type) || isArraySpeculation(abstractChild.m_type) || isArgumentsSpeculation(abstractChild.m_type)) {
             if (trySetConstant(node, vm->smallStrings.objectString())) {
                 filter(node->child1(), SpecFinalObject | SpecArray | SpecArguments);
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         } else if (isFunctionSpeculation(abstractChild.m_type)) {
             if (trySetConstant(node, vm->smallStrings.functionString())) {
                 filter(node->child1(), SpecFunction);
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         } else if (isBooleanSpeculation(abstractChild.m_type)) {
             if (trySetConstant(node, vm->smallStrings.booleanString())) {
                 filter(node->child1(), SpecBoolean);
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
         }
@@ -903,7 +702,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         }
         
         if (constantWasSet) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         
@@ -928,14 +727,14 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         if (left && right) {
             if (left.isNumber() && right.isNumber()
                 && trySetConstant(node, jsBoolean(left.asNumber() == right.asNumber()))) {
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
             if (left.isString() && right.isString()) {
                 const StringImpl* a = asString(left)->tryGetValueImpl();
                 const StringImpl* b = asString(right)->tryGetValueImpl();
                 if (a && b && trySetConstant(node, jsBoolean(WTF::equal(a, b)))) {
-                    m_foundConstants = true;
+                    m_state.setFoundConstants(true);
                     break;
                 }
             }
@@ -968,7 +767,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
             RELEASE_ASSERT_NOT_REACHED();
             break;
         case Array::ForceExit:
-            m_isValid = false;
+            m_state.setIsValid(false);
             break;
         case Array::Generic:
             clobberWorld(node->codeOrigin, indexInBlock);
@@ -1057,7 +856,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         node->setCanExit(true);
         switch (node->arrayMode().modeForPut().type()) {
         case Array::ForceExit:
-            m_isValid = false;
+            m_state.setIsValid(false);
             break;
         case Array::Generic:
             clobberWorld(node->codeOrigin, indexInBlock);
@@ -1112,11 +911,11 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         Node* child = node->child1().node();
         BooleanResult result = booleanResult(node, forNode(child));
         if (result == DefinitelyTrue) {
-            m_branchDirection = TakeTrue;
+            m_state.setBranchDirection(TakeTrue);
             break;
         }
         if (result == DefinitelyFalse) {
-            m_branchDirection = TakeFalse;
+            m_state.setBranchDirection(TakeFalse);
             break;
         }
         // FIXME: The above handles the trivial cases of sparse conditional
@@ -1124,7 +923,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         // We can specialize the source variable's value on each direction of
         // the branch.
         node->setCanExit(true); // This is overly conservative.
-        m_branchDirection = TakeBoth;
+        m_state.setBranchDirection(TakeBoth);
         break;
     }
         
@@ -1135,19 +934,19 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
     }
             
     case Return:
-        m_isValid = false;
+        m_state.setIsValid(false);
         break;
         
     case Throw:
     case ThrowReferenceError:
-        m_isValid = false;
+        m_state.setIsValid(false);
         node->setCanExit(true);
         break;
             
     case ToPrimitive: {
         JSValue childConst = forNode(node->child1()).value();
         if (childConst && childConst.isNumber() && trySetConstant(node, childConst)) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         
@@ -1186,7 +985,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         }
         destination.setType(type);
         if (destination.isClear())
-            m_isValid = false;
+            m_state.setIsValid(false);
         break;
     }
         
@@ -1226,7 +1025,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         forNode(node).set(
             m_graph,
             m_graph.globalObjectFor(node->codeOrigin)->arrayStructureForIndexingTypeDuringAllocation(node->indexingType()));
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
         
     case NewArrayBuffer:
@@ -1234,18 +1033,18 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         forNode(node).set(
             m_graph,
             m_graph.globalObjectFor(node->codeOrigin)->arrayStructureForIndexingTypeDuringAllocation(node->indexingType()));
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
 
     case NewArrayWithSize:
         node->setCanExit(true);
         forNode(node).setType(SpecArray);
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
             
     case NewRegexp:
         forNode(node).set(m_graph, m_graph.globalObjectFor(node->codeOrigin)->regExpStructure());
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
             
     case ToThis: {
@@ -1268,19 +1067,19 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
 
     case NewObject:
         forNode(node).set(m_graph, node->structure());
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
         
     case CreateActivation:
         forNode(node).set(
             m_graph, m_codeBlock->globalObjectFor(node->codeOrigin)->activationStructure());
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
         
     case CreateArguments:
         forNode(node).set(
             m_graph, m_codeBlock->globalObjectFor(node->codeOrigin)->argumentsStructure());
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
         
     case TearOffActivation:
@@ -1290,9 +1089,9 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
 
     case CheckArgumentsNotCreated:
         if (isEmptySpeculation(
-                m_variables.operand(
+                m_state.variables().operand(
                     m_graph.argumentsRegisterFor(node->codeOrigin)).m_type))
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
         else
             node->setCanExit(true);
         break;
@@ -1309,7 +1108,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
             forNode(node).setType(SpecInt32);
         node->setCanExit(
             !isEmptySpeculation(
-                m_variables.operand(
+                m_state.variables().operand(
                     m_graph.argumentsRegisterFor(node->codeOrigin)).m_type));
         break;
         
@@ -1344,7 +1143,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         value = forNode(node->child1());
         
         if (!(value.m_type & SpecEmpty)) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
 
@@ -1375,7 +1174,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
     case SkipScope: {
         JSValue child = forNode(node->child1()).value();
         if (child && trySetConstant(node, JSValue(jsCast<JSScope*>(child.asCell())->next()))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         forNode(node).setType(SpecCellOther);
@@ -1398,7 +1197,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
     case GetByIdFlush:
         node->setCanExit(true);
         if (!node->prediction()) {
-            m_isValid = false;
+            m_state.setIsValid(false);
             break;
         }
         if (isCellSpeculation(node->child1()->prediction())) {
@@ -1418,7 +1217,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
                         forNode(node).makeTop();
                     filter(node->child1(), status.structureSet());
                     
-                    m_foundConstants = true;
+                    m_state.setFoundConstants(true);
                     break;
                 }
             }
@@ -1450,7 +1249,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         StructureSet& set = node->structureSet();
 
         if (value.m_currentKnownStructure.isSubsetOf(set)) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
 
@@ -1461,13 +1260,13 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         // turn this into a watchpoint instead.
         if (value.m_futurePossibleStructure.isSubsetOf(set)
             && value.m_futurePossibleStructure.hasSingleton()) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             filter(value, value.m_futurePossibleStructure.singleton());
             break;
         }
 
         filter(value, set);
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
     }
         
@@ -1486,7 +1285,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
             || m_graph.watchpoints().shouldAssumeMixedState(node->structure()->transitionWatchpointSet()));
         
         filter(value, node->structure());
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         node->setCanExit(true);
         break;
     }
@@ -1496,7 +1295,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         if (!forNode(node->child1()).m_currentKnownStructure.isClear()) {
             clobberStructures(indexInBlock);
             forNode(node->child1()).set(m_graph, node->structureTransitionData().newStructure);
-            m_haveStructures = true;
+            m_state.setHaveStructures(true);
         }
         break;
     case GetButterfly:
@@ -1507,7 +1306,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
     case ForwardCheckArray:
     case CheckArray: {
         if (node->arrayMode().alreadyChecked(m_graph, node, forNode(node->child1()))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         node->setCanExit(true); // Lies, but this is followed by operations (like GetByVal) that always exit, so there is no point in us trying to be clever here.
@@ -1556,12 +1355,12 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
             break;
         }
         filterArrayModes(node->child1(), node->arrayMode().arrayModesThatPassFiltering());
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
     }
     case Arrayify: {
         if (node->arrayMode().alreadyChecked(m_graph, node, forNode(node->child1()))) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             break;
         }
         ASSERT(node->arrayMode().conversion() == Array::Convert
@@ -1569,7 +1368,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         node->setCanExit(true);
         clobberStructures(indexInBlock);
         filterArrayModes(node->child1(), node->arrayMode().arrayModesThatPassFiltering());
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
     }
     case ArrayifyToStructure: {
@@ -1577,11 +1376,11 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         StructureSet set = node->structure();
         if (value.m_futurePossibleStructure.isSubsetOf(set)
             || value.m_currentKnownStructure.isSubsetOf(set))
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
         node->setCanExit(true);
         clobberStructures(indexInBlock);
         filter(value, set);
-        m_haveStructures = true;
+        m_state.setHaveStructures(true);
         break;
     }
     case GetIndexedPropertyStorage: {
@@ -1600,7 +1399,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
     case CheckFunction: {
         JSValue value = forNode(node->child1()).value();
         if (value == node->function()) {
-            m_foundConstants = true;
+            m_state.setFoundConstants(true);
             ASSERT(value);
             break;
         }
@@ -1622,14 +1421,14 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
                 node->op() == PutByIdDirect);
             if (status.isSimpleReplace()) {
                 filter(node->child1(), structure);
-                m_foundConstants = true;
+                m_state.setFoundConstants(true);
                 break;
             }
             if (status.isSimpleTransition()) {
                 clobberStructures(indexInBlock);
                 forNode(node->child1()).set(m_graph, status.newStructure());
-                m_haveStructures = true;
-                m_foundConstants = true;
+                m_state.setHaveStructures(true);
+                m_state.setFoundConstants(true);
                 break;
             }
         }
@@ -1693,7 +1492,7 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
     case ForceOSRExit:
     case ForwardForceOSRExit:
         node->setCanExit(true);
-        m_isValid = false;
+        m_state.setIsValid(false);
         break;
             
     case CheckWatchdogTimer:
@@ -1710,17 +1509,19 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         break;
     }
     
-    return m_isValid;
+    return m_state.isValid();
 }
 
-bool AbstractState::executeEffects(unsigned indexInBlock)
+template<typename AbstractStateType>
+bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned indexInBlock)
 {
-    return executeEffects(indexInBlock, m_block->at(indexInBlock));
+    return executeEffects(indexInBlock, m_state.block()->at(indexInBlock));
 }
 
-bool AbstractState::execute(unsigned indexInBlock)
+template<typename AbstractStateType>
+bool AbstractInterpreter<AbstractStateType>::execute(unsigned indexInBlock)
 {
-    Node* node = m_block->at(indexInBlock);
+    Node* node = m_state.block()->at(indexInBlock);
     if (!startExecuting(node))
         return true;
     
@@ -1728,262 +1529,65 @@ bool AbstractState::execute(unsigned indexInBlock)
     return executeEffects(indexInBlock, node);
 }
 
-inline void AbstractState::clobberWorld(const CodeOrigin& codeOrigin, unsigned indexInBlock)
+template<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::clobberWorld(
+    const CodeOrigin& codeOrigin, unsigned indexInBlock)
 {
     clobberCapturedVars(codeOrigin);
     clobberStructures(indexInBlock);
 }
 
-inline void AbstractState::clobberCapturedVars(const CodeOrigin& codeOrigin)
+template<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::clobberCapturedVars(const CodeOrigin& codeOrigin)
 {
     if (codeOrigin.inlineCallFrame) {
         const BitVector& capturedVars = codeOrigin.inlineCallFrame->capturedVars;
         for (size_t i = capturedVars.size(); i--;) {
             if (!capturedVars.quickGet(i))
                 continue;
-            m_variables.local(i).makeTop();
+            m_state.variables().local(i).makeTop();
         }
     } else {
         for (size_t i = m_codeBlock->m_numVars; i--;) {
             if (m_codeBlock->isCaptured(i))
-                m_variables.local(i).makeTop();
+                m_state.variables().local(i).makeTop();
         }
     }
 
-    for (size_t i = m_variables.numberOfArguments(); i--;) {
+    for (size_t i = m_state.variables().numberOfArguments(); i--;) {
         if (m_codeBlock->isCaptured(argumentToOperand(i)))
-            m_variables.argument(i).makeTop();
+            m_state.variables().argument(i).makeTop();
     }
 }
 
-inline void AbstractState::clobberStructures(unsigned indexInBlock)
+template<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::clobberStructures(unsigned indexInBlock)
 {
-    if (!m_haveStructures)
+    if (!m_state.haveStructures())
         return;
     for (size_t i = indexInBlock + 1; i--;)
-        forNode(m_block->at(i)).clobberStructures();
+        forNode(m_state.block()->at(i)).clobberStructures();
     if (m_graph.m_form == SSA) {
-        HashSet<Node*>::iterator iter = m_block->ssa->liveAtHead.begin();
-        HashSet<Node*>::iterator end = m_block->ssa->liveAtHead.end();
+        HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtHead.begin();
+        HashSet<Node*>::iterator end = m_state.block()->ssa->liveAtHead.end();
         for (; iter != end; ++iter)
             forNode(*iter).clobberStructures();
     }
-    for (size_t i = m_variables.numberOfArguments(); i--;)
-        m_variables.argument(i).clobberStructures();
-    for (size_t i = m_variables.numberOfLocals(); i--;)
-        m_variables.local(i).clobberStructures();
-    m_haveStructures = false;
-    m_didClobber = true;
+    for (size_t i = m_state.variables().numberOfArguments(); i--;)
+        m_state.variables().argument(i).clobberStructures();
+    for (size_t i = m_state.variables().numberOfLocals(); i--;)
+        m_state.variables().local(i).clobberStructures();
+    m_state.setHaveStructures(true);
+    m_state.setDidClobber(true);
 }
 
-bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
-{
-    if (!node)
-        return false;
-        
-    AbstractValue source;
-    
-    if (node->variableAccessData()->isCaptured()) {
-        // If it's captured then we know that whatever value was stored into the variable last is the
-        // one we care about. This is true even if the variable at tail is dead, which might happen if
-        // the last thing we did to the variable was a GetLocal and then ended up now using the
-        // GetLocal's result.
-        
-        source = inVariable;
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-        dataLogF("          Transfering ");
-        source.dump(WTF::dataFile());
-        dataLogF(" from last access due to captured variable.\n");
-#endif
-    } else {
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-        dataLogF("          It's live, node @%u.\n", node->index());
-#endif
-    
-        switch (node->op()) {
-        case Phi:
-        case SetArgument:
-        case PhantomLocal:
-        case Flush:
-            // The block transfers the value from head to tail.
-            source = inVariable;
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-            dataLogF("          Transfering ");
-            source.dump(WTF::dataFile());
-            dataLogF(" from head to tail.\n");
-#endif
-            break;
-            
-        case GetLocal:
-            // The block refines the value with additional speculations.
-            source = forNode(node);
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-            dataLogF("          Refining to ");
-            source.dump(WTF::dataFile());
-            dataLogF("\n");
-#endif
-            break;
-            
-        case SetLocal:
-            // The block sets the variable, and potentially refines it, both
-            // before and after setting it.
-            if (node->variableAccessData()->shouldUseDoubleFormat()) {
-                // FIXME: This unnecessarily loses precision.
-                source.setType(SpecDouble);
-            } else
-                source = forNode(node->child1());
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-            dataLogF("          Setting to ");
-            source.dump(WTF::dataFile());
-            dataLogF("\n");
-#endif
-            break;
-        
-        default:
-            RELEASE_ASSERT_NOT_REACHED();
-            break;
-        }
-    }
-    
-    if (destination == source) {
-        // Abstract execution did not change the output value of the variable, for this
-        // basic block, on this iteration.
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-        dataLogF("          Not changed!\n");
-#endif
-        return false;
-    }
-    
-    // Abstract execution reached a new conclusion about the speculations reached about
-    // this variable after execution of this basic block. Update the state, and return
-    // true to indicate that the fixpoint must go on!
-    destination = source;
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-    dataLogF("          Changed!\n");
-#endif
-    return true;
-}
-
-bool AbstractState::merge(BasicBlock* from, BasicBlock* to)
-{
-    ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
-    ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
-    
-    bool changed = false;
-    
-    switch (m_graph.m_form) {
-    case ThreadedCPS: {
-        for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
-            AbstractValue& destination = to->valuesAtHead.argument(argument);
-            changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
-        }
-        
-        for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
-            AbstractValue& destination = to->valuesAtHead.local(local);
-            changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
-        }
-        break;
-    }
-        
-    case SSA: {
-        for (size_t i = from->valuesAtTail.size(); i--;)
-            changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
-        
-        HashSet<Node*>::iterator iter = to->ssa->liveAtHead.begin();
-        HashSet<Node*>::iterator end = to->ssa->liveAtHead.end();
-        for (; iter != end; ++iter) {
-            Node* node = *iter;
-            changed |= to->ssa->valuesAtHead.find(node)->value.merge(
-                from->ssa->valuesAtTail.find(node)->value);
-        }
-        break;
-    }
-        
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-        break;
-    }
-
-    if (!to->cfaHasVisited)
-        changed = true;
-    
-    to->cfaShouldRevisit |= changed;
-    
-    return changed;
-}
-
-inline bool AbstractState::mergeToSuccessors(BasicBlock* basicBlock)
-{
-    Node* terminal = basicBlock->last();
-    
-    ASSERT(terminal->isTerminal());
-    
-    switch (terminal->op()) {
-    case Jump: {
-        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-        dataLog("        Merging to block ", *terminal->takenBlock(), ".\n");
-#endif
-        return merge(basicBlock, terminal->takenBlock());
-    }
-        
-    case Branch: {
-        ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
-        bool changed = false;
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-        dataLog("        Merging to block ", *terminal->takenBlock(), ".\n");
-#endif
-        if (basicBlock->cfaBranchDirection != TakeFalse)
-            changed |= merge(basicBlock, terminal->takenBlock());
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-        dataLog("        Merging to block ", *terminal->notTakenBlock(), ".\n");
-#endif
-        if (basicBlock->cfaBranchDirection != TakeTrue)
-            changed |= merge(basicBlock, terminal->notTakenBlock());
-        return changed;
-    }
-        
-    case Switch: {
-        // FIXME: It would be cool to be sparse conditional for Switch's. Currently
-        // we're not. However I somehow doubt that this will ever be a big deal.
-        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
-        SwitchData* data = terminal->switchData();
-        bool changed = merge(basicBlock, data->fallThrough);
-        for (unsigned i = data->cases.size(); i--;)
-            changed |= merge(basicBlock, data->cases[i].target);
-        return changed;
-    }
-        
-    case Return:
-    case Throw:
-    case ThrowReferenceError:
-        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
-        return false;
-        
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-        return false;
-    }
-}
-
-inline bool AbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
-{
-    if (!destinationNode)
-        return false;
-    
-    ASSERT_UNUSED(sourceNode, sourceNode);
-    
-    // FIXME: We could do some sparse conditional propagation here!
-    
-    return destination.merge(source);
-}
-
-void AbstractState::dump(PrintStream& out)
+template<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::dump(PrintStream& out)
 {
     CommaPrinter comma(" ");
     if (m_graph.m_form == SSA) {
-        HashSet<Node*>::iterator iter = m_block->ssa->liveAtHead.begin();
-        HashSet<Node*>::iterator end = m_block->ssa->liveAtHead.end();
+        HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtHead.begin();
+        HashSet<Node*>::iterator end = m_state.block()->ssa->liveAtHead.end();
         for (; iter != end; ++iter) {
             Node* node = *iter;
             AbstractValue& value = forNode(node);
@@ -1992,8 +1596,8 @@ void AbstractState::dump(PrintStream& out)
             out.print(comma, node, ":", value);
         }
     }
-    for (size_t i = 0; i < m_block->size(); ++i) {
-        Node* node = m_block->at(i);
+    for (size_t i = 0; i < m_state.block()->size(); ++i) {
+        Node* node = m_state.block()->at(i);
         AbstractValue& value = forNode(node);
         if (value.isClear())
             continue;
@@ -2001,36 +1605,43 @@ void AbstractState::dump(PrintStream& out)
     }
 }
 
-FiltrationResult AbstractState::filter(AbstractValue& value, const StructureSet& set)
+template<typename AbstractStateType>
+FiltrationResult AbstractInterpreter<AbstractStateType>::filter(
+    AbstractValue& value, const StructureSet& set)
 {
     if (value.filter(m_graph, set) == FiltrationOK)
         return FiltrationOK;
-    m_isValid = false;
+    m_state.setIsValid(false);
     return Contradiction;
 }
-    
-FiltrationResult AbstractState::filterArrayModes(AbstractValue& value, ArrayModes arrayModes)
+
+template<typename AbstractStateType>
+FiltrationResult AbstractInterpreter<AbstractStateType>::filterArrayModes(
+    AbstractValue& value, ArrayModes arrayModes)
 {
     if (value.filterArrayModes(arrayModes) == FiltrationOK)
         return FiltrationOK;
-    m_isValid = false;
+    m_state.setIsValid(false);
     return Contradiction;
 }
-    
-FiltrationResult AbstractState::filter(AbstractValue& value, SpeculatedType type)
+
+template<typename AbstractStateType>
+FiltrationResult AbstractInterpreter<AbstractStateType>::filter(
+    AbstractValue& value, SpeculatedType type)
 {
     if (value.filter(type) == FiltrationOK)
         return FiltrationOK;
-    m_isValid = false;
+    m_state.setIsValid(false);
     return Contradiction;
 }
-    
-FiltrationResult AbstractState::filterByValue(
+
+template<typename AbstractStateType>
+FiltrationResult AbstractInterpreter<AbstractStateType>::filterByValue(
     AbstractValue& abstractValue, JSValue concreteValue)
 {
     if (abstractValue.filterByValue(concreteValue) == FiltrationOK)
         return FiltrationOK;
-    m_isValid = false;
+    m_state.setIsValid(false);
     return Contradiction;
 }
 
@@ -2038,3 +1649,5 @@ FiltrationResult AbstractState::filterByValue(
 
 #endif // ENABLE(DFG_JIT)
 
+#endif // DFGAbstractInterpreterInlines_h
+
index 874fff8..ba9b4e7 100644 (file)
@@ -28,7 +28,6 @@
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGAbstractState.h"
 #include "DFGBasicBlock.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
index ee97442..9a392d4 100644 (file)
@@ -28,8 +28,9 @@
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGAbstractState.h"
+#include "DFGAbstractInterpreterInlines.h"
 #include "DFGGraph.h"
+#include "DFGInPlaceAbstractState.h"
 #include "DFGPhase.h"
 #include "Operations.h"
 
@@ -46,6 +47,7 @@ public:
     CFAPhase(Graph& graph)
         : Phase(graph, "control flow analysis")
         , m_state(graph)
+        , m_interpreter(graph, m_state)
     {
     }
     
@@ -97,10 +99,10 @@ private:
             if (verbose) {
                 Node* node = block->at(i);
                 dataLogF("      %s @%u: ", Graph::opName(node->op()), node->index());
-                m_state.dump(WTF::dataFile());
+                m_interpreter.dump(WTF::dataFile());
                 dataLogF("\n");
             }
-            if (!m_state.execute(i)) {
+            if (!m_interpreter.execute(i)) {
                 if (verbose)
                     dataLogF("         Expect OSR exit.\n");
                 break;
@@ -108,10 +110,10 @@ private:
         }
         if (verbose) {
             dataLogF("      tail regs: ");
-            m_state.dump(WTF::dataFile());
+            m_interpreter.dump(WTF::dataFile());
             dataLogF("\n");
         }
-        m_changed |= m_state.endBasicBlock(AbstractState::MergeToSuccessors);
+        m_changed |= m_state.endBasicBlock(MergeToSuccessors);
         
         if (verbose) {
             dataLogF("      tail vars: ");
@@ -131,7 +133,8 @@ private:
     }
 
 private:
-    AbstractState m_state;
+    InPlaceAbstractState m_state;
+    AbstractInterpreter<InPlaceAbstractState> m_interpreter;
     
     bool m_changed;
     unsigned m_count;
index 11af9c6..63fff9b 100644 (file)
@@ -28,7 +28,6 @@
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGAbstractState.h"
 #include "DFGBasicBlockInlines.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
index 1d88fda..e1d911a 100644 (file)
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGAbstractState.h"
+#include "DFGAbstractInterpreterInlines.h"
 #include "DFGBasicBlock.h"
 #include "DFGGraph.h"
+#include "DFGInPlaceAbstractState.h"
 #include "DFGInsertionSet.h"
 #include "DFGPhase.h"
 #include "GetByIdStatus.h"
@@ -44,6 +45,7 @@ public:
     ConstantFoldingPhase(Graph& graph)
         : Phase(graph, "constant folding")
         , m_state(graph)
+        , m_interpreter(graph, m_state)
         , m_insertionSet(graph)
     {
     }
@@ -100,7 +102,7 @@ private:
                 else
                     set = node->structureSet();
                 if (value.m_currentKnownStructure.isSubsetOf(set)) {
-                    m_state.execute(indexInBlock); // Catch the fact that we may filter on cell.
+                    m_interpreter.execute(indexInBlock); // Catch the fact that we may filter on cell.
                     node->convertToPhantom();
                     eliminated = true;
                     break;
@@ -109,7 +111,7 @@ private:
                 if (structureValue.isSubsetOf(set)
                     && structureValue.hasSingleton()) {
                     Structure* structure = structureValue.singleton();
-                    m_state.execute(indexInBlock); // Catch the fact that we may filter on cell.
+                    m_interpreter.execute(indexInBlock); // Catch the fact that we may filter on cell.
                     AdjacencyList children = node->children;
                     children.removeEdge(0);
                     if (!!children.child1()) {
@@ -178,7 +180,7 @@ private:
                 // Now before we do anything else, push the CFA forward over the GetById
                 // and make sure we signal to the loop that it should continue and not
                 // do any eliminations.
-                m_state.execute(indexInBlock);
+                m_interpreter.execute(indexInBlock);
                 eliminated = true;
                 
                 if (needsWatchpoint) {
@@ -242,7 +244,7 @@ private:
                 // Now before we do anything else, push the CFA forward over the PutById
                 // and make sure we signal to the loop that it should continue and not
                 // do any eliminations.
-                m_state.execute(indexInBlock);
+                m_interpreter.execute(indexInBlock);
                 eliminated = true;
                 
                 if (needsWatchpoint) {
@@ -331,7 +333,7 @@ private:
                 continue;
             }
                 
-            m_state.execute(indexInBlock);
+            m_interpreter.execute(indexInBlock);
             if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant())
                 continue;
             JSValue value = m_state.forNode(node).value();
@@ -419,7 +421,8 @@ private:
             OpInfo(m_graph.addStructureSet(cell->structure())), Edge(weakConstant, CellUse));
     }
     
-    AbstractState m_state;
+    InPlaceAbstractState m_state;
+    AbstractInterpreter<InPlaceAbstractState> m_interpreter;
     InsertionSet m_insertionSet;
 };
 
diff --git a/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp b/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp
new file mode 100644 (file)
index 0000000..0510878
--- /dev/null
@@ -0,0 +1,469 @@
+/*
+ * Copyright (C) 2013 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 "DFGInPlaceAbstractState.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "CodeBlock.h"
+#include "DFGBasicBlock.h"
+#include "GetByIdStatus.h"
+#include "Operations.h"
+#include "PutByIdStatus.h"
+#include "StringObject.h"
+
+namespace JSC { namespace DFG {
+
+InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
+    : m_graph(graph)
+    , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
+    , m_block(0)
+{
+}
+
+InPlaceAbstractState::~InPlaceAbstractState() { }
+
+void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
+{
+    ASSERT(!m_block);
+    
+    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
+    ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
+    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
+    
+    for (size_t i = 0; i < basicBlock->size(); i++)
+        forNode(basicBlock->at(i)).clear();
+
+    m_variables = basicBlock->valuesAtHead;
+    m_haveStructures = false;
+    for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
+        if (m_variables.argument(i).hasClobberableState()) {
+            m_haveStructures = true;
+            break;
+        }
+    }
+    for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
+        if (m_variables.local(i).hasClobberableState()) {
+            m_haveStructures = true;
+            break;
+        }
+    }
+    
+    if (m_graph.m_form == SSA) {
+        HashMap<Node*, AbstractValue>::iterator iter = basicBlock->ssa->valuesAtHead.begin();
+        HashMap<Node*, AbstractValue>::iterator end = basicBlock->ssa->valuesAtHead.end();
+        for (; iter != end; ++iter) {
+            forNode(iter->key) = iter->value;
+            if (iter->value.hasClobberableState())
+                m_haveStructures = true;
+        }
+    }
+    
+    basicBlock->cfaShouldRevisit = false;
+    basicBlock->cfaHasVisited = true;
+    m_block = basicBlock;
+    m_isValid = true;
+    m_foundConstants = false;
+    m_branchDirection = InvalidBranchDirection;
+}
+
+static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
+{
+    values.clear();
+    
+    HashSet<Node*>::iterator iter = live.begin();
+    HashSet<Node*>::iterator end = live.end();
+    for (; iter != end; ++iter)
+        values.add(*iter, AbstractValue());
+}
+
+void InPlaceAbstractState::initialize()
+{
+    BasicBlock* root = m_graph.block(0);
+    root->cfaShouldRevisit = true;
+    root->cfaHasVisited = false;
+    root->cfaFoundConstants = false;
+    for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
+        if (m_graph.m_form == SSA) {
+            root->valuesAtHead.argument(i).makeTop();
+            continue;
+        }
+        
+        Node* node = root->variablesAtHead.argument(i);
+        ASSERT(node->op() == SetArgument);
+        if (!node->variableAccessData()->shouldUnboxIfPossible()) {
+            root->valuesAtHead.argument(i).makeTop();
+            continue;
+        }
+        
+        SpeculatedType prediction =
+            node->variableAccessData()->argumentAwarePrediction();
+        if (isInt32Speculation(prediction))
+            root->valuesAtHead.argument(i).setType(SpecInt32);
+        else if (isBooleanSpeculation(prediction))
+            root->valuesAtHead.argument(i).setType(SpecBoolean);
+        else if (isCellSpeculation(prediction))
+            root->valuesAtHead.argument(i).setType(SpecCell);
+        else
+            root->valuesAtHead.argument(i).makeTop();
+        
+        root->valuesAtTail.argument(i).clear();
+    }
+    for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
+        Node* node = root->variablesAtHead.local(i);
+        if (node && node->variableAccessData()->isCaptured())
+            root->valuesAtHead.local(i).makeTop();
+        else
+            root->valuesAtHead.local(i).clear();
+        root->valuesAtTail.local(i).clear();
+    }
+    for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+        BasicBlock* block = m_graph.block(blockIndex);
+        if (!block)
+            continue;
+        ASSERT(block->isReachable);
+        block->cfaShouldRevisit = false;
+        block->cfaHasVisited = false;
+        block->cfaFoundConstants = false;
+        for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
+            block->valuesAtHead.argument(i).clear();
+            block->valuesAtTail.argument(i).clear();
+        }
+        for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
+            block->valuesAtHead.local(i).clear();
+            block->valuesAtTail.local(i).clear();
+        }
+        if (!block->isOSRTarget)
+            continue;
+        if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
+            continue;
+        for (size_t i = 0; i < m_graph.m_plan.mustHandleValues.size(); ++i) {
+            AbstractValue value;
+            value.setMostSpecific(m_graph, m_graph.m_plan.mustHandleValues[i]);
+            int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i);
+            block->valuesAtHead.operand(operand).merge(value);
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+            dataLogF("    Initializing Block #%u, operand r%d, to ", blockIndex, operand);
+            block->valuesAtHead.operand(operand).dump(WTF::dataFile());
+            dataLogF("\n");
+#endif
+        }
+        block->cfaShouldRevisit = true;
+    }
+    if (m_graph.m_form == SSA) {
+        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
+            setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
+        }
+    }
+}
+
+bool InPlaceAbstractState::endBasicBlock(MergeMode mergeMode)
+{
+    ASSERT(m_block);
+    
+    BasicBlock* block = m_block; // Save the block for successor merging.
+    
+    block->cfaFoundConstants = m_foundConstants;
+    block->cfaDidFinish = m_isValid;
+    block->cfaBranchDirection = m_branchDirection;
+    
+    if (!m_isValid) {
+        reset();
+        return false;
+    }
+    
+    bool changed = false;
+    
+    if (mergeMode != DontMerge || !ASSERT_DISABLED) {
+        switch (m_graph.m_form) {
+        case ThreadedCPS: {
+            for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+                dataLogF("        Merging state for argument %zu.\n", argument);
+#endif
+                AbstractValue& destination = block->valuesAtTail.argument(argument);
+                changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
+            }
+            
+            for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+                dataLogF("        Merging state for local %zu.\n", local);
+#endif
+                AbstractValue& destination = block->valuesAtTail.local(local);
+                changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
+            }
+            break;
+        }
+            
+        case SSA: {
+            for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
+                changed |= block->valuesAtTail[i].merge(m_variables[i]);
+            
+            HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
+            HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
+            for (; iter != end; ++iter) {
+                Node* node = *iter;
+                changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
+            }
+            break;
+        }
+            
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+        }
+    }
+    
+    ASSERT(mergeMode != DontMerge || !changed);
+    
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+    dataLogF("        Branch direction = %s\n", branchDirectionToString(m_branchDirection));
+#endif
+    
+    reset();
+    
+    if (mergeMode != MergeToSuccessors)
+        return changed;
+    
+    return mergeToSuccessors(block);
+}
+
+void InPlaceAbstractState::reset()
+{
+    m_block = 0;
+    m_isValid = false;
+    m_branchDirection = InvalidBranchDirection;
+}
+
+bool InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
+{
+    if (!node)
+        return false;
+        
+    AbstractValue source;
+    
+    if (node->variableAccessData()->isCaptured()) {
+        // If it's captured then we know that whatever value was stored into the variable last is the
+        // one we care about. This is true even if the variable at tail is dead, which might happen if
+        // the last thing we did to the variable was a GetLocal and then ended up now using the
+        // GetLocal's result.
+        
+        source = inVariable;
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+        dataLogF("          Transfering ");
+        source.dump(WTF::dataFile());
+        dataLogF(" from last access due to captured variable.\n");
+#endif
+    } else {
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+        dataLogF("          It's live, node @%u.\n", node->index());
+#endif
+    
+        switch (node->op()) {
+        case Phi:
+        case SetArgument:
+        case PhantomLocal:
+        case Flush:
+            // The block transfers the value from head to tail.
+            source = inVariable;
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+            dataLogF("          Transfering ");
+            source.dump(WTF::dataFile());
+            dataLogF(" from head to tail.\n");
+#endif
+            break;
+            
+        case GetLocal:
+            // The block refines the value with additional speculations.
+            source = forNode(node);
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+            dataLogF("          Refining to ");
+            source.dump(WTF::dataFile());
+            dataLogF("\n");
+#endif
+            break;
+            
+        case SetLocal:
+            // The block sets the variable, and potentially refines it, both
+            // before and after setting it.
+            if (node->variableAccessData()->shouldUseDoubleFormat()) {
+                // FIXME: This unnecessarily loses precision.
+                source.setType(SpecDouble);
+            } else
+                source = forNode(node->child1());
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+            dataLogF("          Setting to ");
+            source.dump(WTF::dataFile());
+            dataLogF("\n");
+#endif
+            break;
+        
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            break;
+        }
+    }
+    
+    if (destination == source) {
+        // Abstract execution did not change the output value of the variable, for this
+        // basic block, on this iteration.
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+        dataLogF("          Not changed!\n");
+#endif
+        return false;
+    }
+    
+    // Abstract execution reached a new conclusion about the speculations reached about
+    // this variable after execution of this basic block. Update the state, and return
+    // true to indicate that the fixpoint must go on!
+    destination = source;
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+    dataLogF("          Changed!\n");
+#endif
+    return true;
+}
+
+bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
+{
+    ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
+    ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
+    
+    bool changed = false;
+    
+    switch (m_graph.m_form) {
+    case ThreadedCPS: {
+        for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
+            AbstractValue& destination = to->valuesAtHead.argument(argument);
+            changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
+        }
+        
+        for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
+            AbstractValue& destination = to->valuesAtHead.local(local);
+            changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
+        }
+        break;
+    }
+        
+    case SSA: {
+        for (size_t i = from->valuesAtTail.size(); i--;)
+            changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
+        
+        HashSet<Node*>::iterator iter = to->ssa->liveAtHead.begin();
+        HashSet<Node*>::iterator end = to->ssa->liveAtHead.end();
+        for (; iter != end; ++iter) {
+            Node* node = *iter;
+            changed |= to->ssa->valuesAtHead.find(node)->value.merge(
+                from->ssa->valuesAtTail.find(node)->value);
+        }
+        break;
+    }
+        
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+        break;
+    }
+
+    if (!to->cfaHasVisited)
+        changed = true;
+    
+    to->cfaShouldRevisit |= changed;
+    
+    return changed;
+}
+
+inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
+{
+    Node* terminal = basicBlock->last();
+    
+    ASSERT(terminal->isTerminal());
+    
+    switch (terminal->op()) {
+    case Jump: {
+        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+        dataLog("        Merging to block ", *terminal->takenBlock(), ".\n");
+#endif
+        return merge(basicBlock, terminal->takenBlock());
+    }
+        
+    case Branch: {
+        ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
+        bool changed = false;
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+        dataLog("        Merging to block ", *terminal->takenBlock(), ".\n");
+#endif
+        if (basicBlock->cfaBranchDirection != TakeFalse)
+            changed |= merge(basicBlock, terminal->takenBlock());
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+        dataLog("        Merging to block ", *terminal->notTakenBlock(), ".\n");
+#endif
+        if (basicBlock->cfaBranchDirection != TakeTrue)
+            changed |= merge(basicBlock, terminal->notTakenBlock());
+        return changed;
+    }
+        
+    case Switch: {
+        // FIXME: It would be cool to be sparse conditional for Switch's. Currently
+        // we're not. However I somehow doubt that this will ever be a big deal.
+        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
+        SwitchData* data = terminal->switchData();
+        bool changed = merge(basicBlock, data->fallThrough);
+        for (unsigned i = data->cases.size(); i--;)
+            changed |= merge(basicBlock, data->cases[i].target);
+        return changed;
+    }
+        
+    case Return:
+    case Throw:
+    case ThrowReferenceError:
+        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
+        return false;
+        
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+        return false;
+    }
+}
+
+inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
+{
+    if (!destinationNode)
+        return false;
+    
+    ASSERT_UNUSED(sourceNode, sourceNode);
+    
+    // FIXME: We could do some sparse conditional propagation here!
+    
+    return destination.merge(source);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h b/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h
new file mode 100644 (file)
index 0000000..633261e
--- /dev/null
@@ -0,0 +1,155 @@
+/*
+ * Copyright (C) 2013 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. 
+ */
+
+#ifndef DFGInPlaceAbstractState_h
+#define DFGInPlaceAbstractState_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGAbstractValue.h"
+#include "DFGBranchDirection.h"
+#include "DFGGraph.h"
+#include "DFGMergeMode.h"
+#include "DFGNode.h"
+
+namespace JSC { namespace DFG {
+
+class InPlaceAbstractState {
+public:
+    InPlaceAbstractState(Graph& graph);
+    
+    ~InPlaceAbstractState();
+    
+    AbstractValue& forNode(Node* node)
+    {
+        return node->value;
+    }
+    
+    AbstractValue& forNode(Edge edge)
+    {
+        return forNode(edge.node());
+    }
+    
+    Operands<AbstractValue>& variables()
+    {
+        return m_variables;
+    }
+    
+    // Call this before beginning CFA to initialize the abstract values of
+    // arguments, and to indicate which blocks should be listed for CFA
+    // execution.
+    void initialize();
+
+    // Start abstractly executing the given basic block. Initializes the
+    // notion of abstract state to what we believe it to be at the head
+    // of the basic block, according to the basic block's data structures.
+    // This method also sets cfaShouldRevisit to false.
+    void beginBasicBlock(BasicBlock*);
+    
+    BasicBlock* block() const { return m_block; }
+    
+    // Finish abstractly executing a basic block. If MergeToTail or
+    // MergeToSuccessors is passed, then this merges everything we have
+    // learned about how the state changes during this block's execution into
+    // the block's data structures. There are three return modes, depending
+    // on the value of mergeMode:
+    //
+    // DontMerge:
+    //    Always returns false.
+    //
+    // MergeToTail:
+    //    Returns true if the state of the block at the tail was changed.
+    //    This means that you must call mergeToSuccessors(), and if that
+    //    returns true, then you must revisit (at least) the successor
+    //    blocks. False will always be returned if the block is terminal
+    //    (i.e. ends in Throw or Return, or has a ForceOSRExit inside it).
+    //
+    // MergeToSuccessors:
+    //    Returns true if the state of the block at the tail was changed,
+    //    and, if the state at the heads of successors was changed.
+    //    A true return means that you must revisit (at least) the successor
+    //    blocks. This also sets cfaShouldRevisit to true for basic blocks
+    //    that must be visited next.
+    bool endBasicBlock(MergeMode);
+    
+    // Reset the AbstractState. This throws away any results, and at this point
+    // you can safely call beginBasicBlock() on any basic block.
+    void reset();
+    
+    // Did the last executed node clobber the world?
+    bool didClobber() const { return m_didClobber; }
+    
+    // Is the execution state still valid? This will be false if execute() has
+    // returned false previously.
+    bool isValid() const { return m_isValid; }
+    
+    // Merge the abstract state stored at the first block's tail into the second
+    // block's head. Returns true if the second block's state changed. If so,
+    // that block must be abstractly interpreted again. This also sets
+    // to->cfaShouldRevisit to true, if it returns true, or if to has not been
+    // visited yet.
+    bool merge(BasicBlock* from, BasicBlock* to);
+    
+    // Merge the abstract state stored at the block's tail into all of its
+    // successors. Returns true if any of the successors' states changed. Note
+    // that this is automatically called in endBasicBlock() if MergeMode is
+    // MergeToSuccessors.
+    bool mergeToSuccessors(BasicBlock*);
+    
+    // Methods intended to be called from AbstractInterpreter.
+    void setDidClobber(bool didClobber) { m_didClobber = didClobber; }
+    void setIsValid(bool isValid) { m_isValid = isValid; }
+    void setBranchDirection(BranchDirection branchDirection) { m_branchDirection = branchDirection; }
+    void setFoundConstants(bool foundConstants) { m_foundConstants = foundConstants; }
+    bool haveStructures() const { return m_haveStructures; } // It's always safe to return true.
+    void setHaveStructures(bool haveStructures) { m_haveStructures = haveStructures; }
+
+private:
+    bool mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*);
+
+    static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);
+    
+    Graph& m_graph;
+    
+    Operands<AbstractValue> m_variables;
+    BasicBlock* m_block;
+    
+    bool m_haveStructures;
+    bool m_foundConstants;
+    
+    bool m_isValid;
+    bool m_didClobber;
+    
+    BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true).
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGInPlaceAbstractState_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGMergeMode.h b/Source/JavaScriptCore/dfg/DFGMergeMode.h
new file mode 100644 (file)
index 0000000..6619fea
--- /dev/null
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2013 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. 
+ */
+
+#ifndef DFGMergeMode_h
+#define DFGMergeMode_h
+
+namespace JSC { namespace DFG {
+
+enum MergeMode {
+    // Don't merge the state in AbstractState with basic blocks.
+    DontMerge,
+    
+    // Merge the state in AbstractState with the tail of the basic
+    // block being analyzed.
+    MergeToTail,
+    
+    // Merge the state in AbstractState with the tail of the basic
+    // block, and with the heads of successor blocks.
+    MergeToSuccessors
+};
+
+} } // namespace JSC::DFG
+
+#endif // DFGMergeMode_h
+
index bdbd93a..58b465e 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "Arguments.h"
+#include "DFGAbstractInterpreterInlines.h"
 #include "DFGArrayifySlowPathGenerator.h"
 #include "DFGBinarySwitch.h"
 #include "DFGCallArrayAllocatorSlowPathGenerator.h"
@@ -48,6 +49,7 @@ SpeculativeJIT::SpeculativeJIT(JITCompiler& jit)
     , m_variables(jit.graph().m_localVars)
     , m_lastSetOperand(std::numeric_limits<int>::max())
     , m_state(m_jit.graph())
+    , m_interpreter(m_jit.graph(), m_state)
     , m_stream(&jit.jitCode()->variableEventStream)
     , m_minifiedGraph(&jit.jitCode()->minifiedDFG)
     , m_isCheckingArgumentTypes(false)
@@ -262,7 +264,7 @@ void SpeculativeJIT::terminateSpeculativeExecution(ExitKind kind, JSValueRegs js
 void SpeculativeJIT::backwardTypeCheck(JSValueSource source, Edge edge, SpeculatedType typesPassedThrough, MacroAssembler::Jump jumpToFail)
 {
     ASSERT(needsTypeCheck(edge, typesPassedThrough));
-    m_state.filter(edge, typesPassedThrough);
+    m_interpreter.filter(edge, typesPassedThrough);
     backwardSpeculationCheck(BadType, source, edge.node(), jumpToFail);
 }
 
@@ -1736,7 +1738,7 @@ void SpeculativeJIT::compileCurrentBlock()
         }
         
         m_canExit = m_currentNode->canExit();
-        bool shouldExecuteEffects = m_state.startExecuting(m_currentNode);
+        bool shouldExecuteEffects = m_interpreter.startExecuting(m_currentNode);
         m_jit.setForNode(m_currentNode);
         m_codeOriginForOSR = m_currentNode->codeOrigin;
         if (!m_currentNode->shouldGenerate()) {
@@ -1833,7 +1835,7 @@ void SpeculativeJIT::compileCurrentBlock()
         
         // Make sure that the abstract state is rematerialized for the next node.
         if (shouldExecuteEffects)
-            m_state.executeEffects(m_indexInBlock);
+            m_interpreter.executeEffects(m_indexInBlock);
         
         if (m_currentNode->shouldGenerate())
             checkConsistency();
@@ -4362,7 +4364,8 @@ void SpeculativeJIT::compileToStringOnCell(Node* node)
         GPRReg resultGPR = result.gpr();
         
         speculateStringObject(node->child1(), op1GPR);
-        m_state.filter(node->child1(), SpecStringObject);
+        m_interpreter.filter(node->child1(), SpecStringObject);
+
         m_jit.loadPtr(JITCompiler::Address(op1GPR, JSWrapperObject::internalValueCellOffset()), resultGPR);
         cellResult(resultGPR, node);
         break;
@@ -4385,7 +4388,7 @@ void SpeculativeJIT::compileToStringOnCell(Node* node)
         m_jit.move(op1GPR, resultGPR);
         done.link(&m_jit);
         
-        m_state.filter(node->child1(), SpecString | SpecStringObject);
+        m_interpreter.filter(node->child1(), SpecString | SpecStringObject);
         
         cellResult(resultGPR, node);
         break;
@@ -4601,7 +4604,7 @@ void SpeculativeJIT::speculateStringIdentAndLoadStorage(Edge edge, GPRReg string
             MacroAssembler::Address(storage, StringImpl::flagsOffset()),
             MacroAssembler::TrustedImm32(StringImpl::flagIsIdentifier())));
     
-    m_state.filter(edge, SpecStringIdent);
+    m_interpreter.filter(edge, SpecStringIdent);
 }
 
 void SpeculativeJIT::speculateStringIdent(Edge edge, GPRReg string)
@@ -4649,7 +4652,7 @@ void SpeculativeJIT::speculateStringObject(Edge edge)
         return;
     
     speculateStringObject(edge, gpr);
-    m_state.filter(edge, SpecStringObject);
+    m_interpreter.filter(edge, SpecStringObject);
 }
 
 void SpeculativeJIT::speculateStringOrStringObject(Edge edge)
@@ -4674,7 +4677,7 @@ void SpeculativeJIT::speculateStringOrStringObject(Edge edge)
     
     isString.link(&m_jit);
     
-    m_state.filter(edge, SpecString | SpecStringObject);
+    m_interpreter.filter(edge, SpecString | SpecStringObject);
 }
 
 void SpeculativeJIT::speculateNotCell(Edge edge)
index 383f701..519e0de 100644 (file)
@@ -30,8 +30,9 @@
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGAbstractState.h"
+#include "DFGAbstractInterpreter.h"
 #include "DFGGenerationInfo.h"
+#include "DFGInPlaceAbstractState.h"
 #include "DFGJITCompiler.h"
 #include "DFGOSRExit.h"
 #include "DFGOSRExitJumpPlaceholder.h"
@@ -2082,7 +2083,7 @@ public:
     void terminateSpeculativeExecution(ExitKind, JSValueRegs, Edge);
     
     // Helpers for performing type checks on an edge stored in the given registers.
-    bool needsTypeCheck(Edge edge, SpeculatedType typesPassedThrough) { return m_state.needsTypeCheck(edge, typesPassedThrough); }
+    bool needsTypeCheck(Edge edge, SpeculatedType typesPassedThrough) { return m_interpreter.needsTypeCheck(edge, typesPassedThrough); }
     void backwardTypeCheck(JSValueSource, Edge, SpeculatedType typesPassedThrough, MacroAssembler::Jump jumpToFail);
     void typeCheck(JSValueSource, Edge, SpeculatedType typesPassedThrough, MacroAssembler::Jump jumpToFail);
     void forwardTypeCheck(JSValueSource, Edge, SpeculatedType typesPassedThrough, MacroAssembler::Jump jumpToFail, const ValueRecovery&);
@@ -2194,7 +2195,8 @@ public:
     int m_lastSetOperand;
     CodeOrigin m_codeOriginForOSR;
     
-    AbstractState m_state;
+    InPlaceAbstractState m_state;
+    AbstractInterpreter<InPlaceAbstractState> m_interpreter;
     
     VariableEventStream* m_stream;
     MinifiedGraph* m_minifiedGraph;
index d164e09..dadce56 100644 (file)
@@ -30,6 +30,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "ArrayPrototype.h"
+#include "DFGAbstractInterpreterInlines.h"
 #include "DFGCallArrayAllocatorSlowPathGenerator.h"
 #include "DFGSlowPathGenerator.h"
 #include "JSActivation.h"
@@ -862,7 +863,7 @@ GPRReg SpeculativeJIT::fillSpeculateIntInternal(Edge edge, DataFormat& returnFor
     AbstractValue& value = m_state.forNode(edge);
     SpeculatedType type = value.m_type;
     ASSERT(edge.useKind() != KnownInt32Use || !(value.m_type & ~SpecInt32));
-    m_state.filter(value, SpecInt32);
+    m_interpreter.filter(value, SpecInt32);
     VirtualRegister virtualRegister = edge->virtualRegister();
     GenerationInfo& info = m_generationInfo[virtualRegister];
 
@@ -963,7 +964,7 @@ FPRReg SpeculativeJIT::fillSpeculateDouble(Edge edge)
     AbstractValue& value = m_state.forNode(edge);
     SpeculatedType type = value.m_type;
     ASSERT(edge.useKind() != KnownNumberUse || !(value.m_type & ~SpecNumber));
-    m_state.filter(value, SpecNumber);
+    m_interpreter.filter(value, SpecNumber);
     VirtualRegister virtualRegister = edge->virtualRegister();
     GenerationInfo& info = m_generationInfo[virtualRegister];
 
@@ -1100,7 +1101,7 @@ GPRReg SpeculativeJIT::fillSpeculateCell(Edge edge)
     AbstractValue& value = m_state.forNode(edge);
     SpeculatedType type = value.m_type;
     ASSERT((edge.useKind() != KnownCellUse && edge.useKind() != KnownStringUse) || !(value.m_type & ~SpecCell));
-    m_state.filter(value, SpecCell);
+    m_interpreter.filter(value, SpecCell);
     VirtualRegister virtualRegister = edge->virtualRegister();
     GenerationInfo& info = m_generationInfo[virtualRegister];
 
@@ -1177,7 +1178,7 @@ GPRReg SpeculativeJIT::fillSpeculateBoolean(Edge edge)
 #endif
     AbstractValue& value = m_state.forNode(edge);
     SpeculatedType type = value.m_type;
-    m_state.filter(value, SpecBoolean);
+    m_interpreter.filter(value, SpecBoolean);
     VirtualRegister virtualRegister = edge->virtualRegister();
     GenerationInfo& info = m_generationInfo[virtualRegister];
 
index a6408e9..5f00a89 100644 (file)
@@ -30,6 +30,7 @@
 
 #include "Arguments.h"
 #include "ArrayPrototype.h"
+#include "DFGAbstractInterpreterInlines.h"
 #include "DFGCallArrayAllocatorSlowPathGenerator.h"
 #include "DFGSlowPathGenerator.h"
 #include "JSCJSValueInlines.h"
@@ -822,7 +823,7 @@ GPRReg SpeculativeJIT::fillSpeculateIntInternal(Edge edge, DataFormat& returnFor
     AbstractValue& value = m_state.forNode(edge);
     SpeculatedType type = value.m_type;
     ASSERT(edge.useKind() != KnownInt32Use || !(value.m_type & ~SpecInt32));
-    m_state.filter(value, SpecInt32);
+    m_interpreter.filter(value, SpecInt32);
     VirtualRegister virtualRegister = edge->virtualRegister();
     GenerationInfo& info = m_generationInfo[virtualRegister];
 
@@ -972,7 +973,7 @@ FPRReg SpeculativeJIT::fillSpeculateDouble(Edge edge)
     AbstractValue& value = m_state.forNode(edge);
     SpeculatedType type = value.m_type;
     ASSERT(edge.useKind() != KnownNumberUse || !(value.m_type & ~SpecNumber));
-    m_state.filter(value, SpecNumber);
+    m_interpreter.filter(value, SpecNumber);
     VirtualRegister virtualRegister = edge->virtualRegister();
     GenerationInfo& info = m_generationInfo[virtualRegister];
 
@@ -1128,7 +1129,7 @@ GPRReg SpeculativeJIT::fillSpeculateCell(Edge edge)
     AbstractValue& value = m_state.forNode(edge);
     SpeculatedType type = value.m_type;
     ASSERT((edge.useKind() != KnownCellUse && edge.useKind() != KnownStringUse) || !(value.m_type & ~SpecCell));
-    m_state.filter(value, SpecCell);
+    m_interpreter.filter(value, SpecCell);
     VirtualRegister virtualRegister = edge->virtualRegister();
     GenerationInfo& info = m_generationInfo[virtualRegister];
 
@@ -1205,7 +1206,7 @@ GPRReg SpeculativeJIT::fillSpeculateBoolean(Edge edge)
 #endif
     AbstractValue& value = m_state.forNode(edge);
     SpeculatedType type = value.m_type;
-    m_state.filter(value, SpecBoolean);
+    m_interpreter.filter(value, SpecBoolean);
     VirtualRegister virtualRegister = edge->virtualRegister();
     GenerationInfo& info = m_generationInfo[virtualRegister];
 
index c5ee509..c7d011f 100644 (file)
@@ -29,7 +29,8 @@
 #if ENABLE(FTL_JIT)
 
 #include "CodeBlockWithJITType.h"
-#include "DFGAbstractState.h"
+#include "DFGAbstractInterpreterInlines.h"
+#include "DFGInPlaceAbstractState.h"
 #include "FTLAbstractHeapRepository.h"
 #include "FTLExitThunkGenerator.h"
 #include "FTLFormattedValue.h"
@@ -53,7 +54,7 @@ static int compileCounter;
         FormattedValue _ftc_lowValue = (lowValue);                      \
         Edge _ftc_highValue = (highValue);                              \
         SpeculatedType _ftc_typesPassedThrough = (typesPassedThrough);  \
-        if (!m_state.needsTypeCheck(_ftc_highValue, _ftc_typesPassedThrough)) \
+        if (!m_interpreter.needsTypeCheck(_ftc_highValue, _ftc_typesPassedThrough)) \
             break;                                                      \
         typeCheck(_ftc_lowValue, _ftc_highValue, _ftc_typesPassedThrough, (failCondition)); \
     } while (false)
@@ -69,6 +70,7 @@ public:
         , m_lastSetOperand(std::numeric_limits<int>::max())
         , m_exitThunkGenerator(state)
         , m_state(state.graph)
+        , m_interpreter(state.graph, m_state)
     {
     }
     
@@ -219,7 +221,7 @@ private:
         if (verboseCompilationEnabled())
             dataLog("Lowering ", m_node, "\n");
         
-        bool shouldExecuteEffects = m_state.startExecuting(m_node);
+        bool shouldExecuteEffects = m_interpreter.startExecuting(m_node);
         
         m_direction = (m_node->flags() & NodeExitsForward) ? ForwardSpeculation : BackwardSpeculation;
         
@@ -408,7 +410,7 @@ private:
             m_live.add(m_node);
         
         if (shouldExecuteEffects)
-            m_state.executeEffects(nodeIndex);
+            m_interpreter.executeEffects(nodeIndex);
         
         return true;
     }
@@ -1929,11 +1931,11 @@ private:
         FormattedValue lowValue, Edge highValue, SpeculatedType typesPassedThrough,
         LValue failCondition, SpeculationDirection direction, FormattedValue recovery)
     {
-        if (!m_state.needsTypeCheck(highValue, typesPassedThrough))
+        if (!m_interpreter.needsTypeCheck(highValue, typesPassedThrough))
             return;
         ASSERT(mayHaveTypeCheck(highValue.useKind()));
         appendOSRExit(BadType, lowValue, highValue.node(), failCondition, direction, recovery);
-        m_state.filter(highValue, typesPassedThrough);
+        m_interpreter.filter(highValue, typesPassedThrough);
     }
     
     LValue lowInt32(Edge edge, OperandSpeculationMode mode = AutomaticOperandSpeculation)
@@ -2178,7 +2180,7 @@ private:
             break;
         case KnownInt32Use:
         case KnownNumberUse:
-            ASSERT(!m_state.needsTypeCheck(edge));
+            ASSERT(!m_interpreter.needsTypeCheck(edge));
             break;
         case Int32Use:
             speculateInt32(edge);
@@ -2187,7 +2189,7 @@ private:
             speculateCell(edge);
             break;
         case KnownCellUse:
-            ASSERT(!m_state.needsTypeCheck(edge));
+            ASSERT(!m_interpreter.needsTypeCheck(edge));
             break;
         case ObjectUse:
             speculateObject(edge);
@@ -2287,7 +2289,7 @@ private:
     void speculateNumber(Edge edge)
     {
         // Do an early return here because lowDouble() can create a lot of control flow.
-        if (!m_state.needsTypeCheck(edge))
+        if (!m_interpreter.needsTypeCheck(edge))
             return;
         
         lowDouble(edge);
@@ -2296,7 +2298,7 @@ private:
     void speculateRealNumber(Edge edge)
     {
         // Do an early return here because lowDouble() can create a lot of control flow.
-        if (!m_state.needsTypeCheck(edge))
+        if (!m_interpreter.needsTypeCheck(edge))
             return;
         
         LValue value = lowDouble(edge);
@@ -2862,7 +2864,8 @@ private:
     int m_lastSetOperand;
     ExitThunkGenerator m_exitThunkGenerator;
     
-    AbstractState m_state;
+    InPlaceAbstractState m_state;
+    AbstractInterpreter<InPlaceAbstractState> m_interpreter;
     BasicBlock* m_highBlock;
     BasicBlock* m_nextHighBlock;
     LBasicBlock m_nextLowBlock;