1. 30 Oct, 2013 1 commit
    • fpizlo@apple.com's avatar
      Add InvalidationPoints to the DFG and use them for all watchpoints · d84425d1
      fpizlo@apple.com authored
      https://bugs.webkit.org/show_bug.cgi?id=123472
      
      Reviewed by Mark Hahnenberg.
              
      This makes a fundamental change to how watchpoints work in the DFG.
              
      Previously, a watchpoint was an instruction whose execution semantics were something
      like:
              
          if (watchpoint->invalidated)
              exit
              
      We would implement this without any branch by using jump replacement.
              
      This is a very good optimization. But it's a bit awkward once you get a lot of
      watchpoints: semantically we will have lots of these branches in the code, which the
      compiler needs to reason about even though they don't actually result in any emitted
      code.
              
      Separately, we also had a mechanism for jettisoning a CodeBlock. This mechanism would
      be invoked if a CodeBlock exited a lot. It would ensure that a CodeBlock wouldn't be
      called into again, but it would do nothing for CodeBlocks that were already on the
      stack.
              
      This change flips jettisoning and watchpoint invalidation on their heads. Now, the jump
      replacement has nothing to do with watchpoints; instead it's something that happens if
      you ever jettison a CodeBlock. Jump replacement is now an all-or-nothing operation over
      all of the potential call-return safe-exit-points in a CodeBlock. We call these
      "InvalidationPoint"s. A watchpoint instruction is now "lowered" by having the DFG
      collect all of the watchpoint sets that the CodeBlock cares about, and then registering
      a CodeBlockJettisoningWatchpoint with all of them. That is, if the watchpoint fires, it
      jettisons the CodeBlock, which in turn ensures that the CodeBlock can't be called into
      (because the entrypoint now points to baseline code) and can't be returned into
      (because returning exits to baseline before the next bytecode instruction).
              
      This will allow for a sensible lowering of watchpoints to LLVM IR. It will also allow
      for jettison() to be used effectively for things like breakpointing and single-stepping
      in the debugger.
              
      Well, basically, this mechanism just takes us into the HotSpot-style world where anyone
      can, at any time and for any reason, request that an optimized CodeBlock is rendered
      immediately invalid. You can use this for many cool things, I'm sure.
      
      * CMakeLists.txt:
      * GNUmakefile.list.am:
      * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
      * JavaScriptCore.xcodeproj/project.pbxproj:
      * assembler/AbstractMacroAssembler.h:
      * bytecode/CodeBlock.cpp:
      (JSC::CodeBlock::jettison):
      * bytecode/CodeBlock.h:
      * bytecode/CodeBlockJettisoningWatchpoint.cpp: Added.
      (JSC::CodeBlockJettisoningWatchpoint::fireInternal):
      * bytecode/CodeBlockJettisoningWatchpoint.h: Added.
      (JSC::CodeBlockJettisoningWatchpoint::CodeBlockJettisoningWatchpoint):
      * bytecode/ExitKind.cpp:
      (JSC::exitKindToString):
      * bytecode/ExitKind.h:
      * bytecode/ProfiledCodeBlockJettisoningWatchpoint.cpp: Added.
      (JSC::ProfiledCodeBlockJettisoningWatchpoint::fireInternal):
      * bytecode/ProfiledCodeBlockJettisoningWatchpoint.h: Added.
      (JSC::ProfiledCodeBlockJettisoningWatchpoint::ProfiledCodeBlockJettisoningWatchpoint):
      * dfg/DFGAbstractHeap.h:
      * dfg/DFGAbstractInterpreterInlines.h:
      (JSC::DFG::::executeEffects):
      * dfg/DFGClobberize.cpp:
      (JSC::DFG::writesOverlap):
      * dfg/DFGClobberize.h:
      (JSC::DFG::clobberize):
      (JSC::DFG::AbstractHeapOverlaps::AbstractHeapOverlaps):
      (JSC::DFG::AbstractHeapOverlaps::operator()):
      (JSC::DFG::AbstractHeapOverlaps::result):
      * dfg/DFGCommonData.cpp:
      (JSC::DFG::CommonData::invalidate):
      * dfg/DFGCommonData.h:
      (JSC::DFG::CommonData::CommonData):
      * dfg/DFGDesiredWatchpoints.cpp:
      (JSC::DFG::DesiredWatchpoints::addLazily):
      (JSC::DFG::DesiredWatchpoints::reallyAdd):
      * dfg/DFGDesiredWatchpoints.h:
      (JSC::DFG::WatchpointForGenericWatchpointSet::WatchpointForGenericWatchpointSet):
      (JSC::DFG::GenericDesiredWatchpoints::addLazily):
      (JSC::DFG::GenericDesiredWatchpoints::reallyAdd):
      (JSC::DFG::GenericDesiredWatchpoints::areStillValid):
      * dfg/DFGFixupPhase.cpp:
      (JSC::DFG::FixupPhase::fixupNode):
      * dfg/DFGInvalidationPointInjectionPhase.cpp: Added.
      (JSC::DFG::InvalidationPointInjectionPhase::InvalidationPointInjectionPhase):
      (JSC::DFG::InvalidationPointInjectionPhase::run):
      (JSC::DFG::InvalidationPointInjectionPhase::handle):
      (JSC::DFG::InvalidationPointInjectionPhase::insertInvalidationCheck):
      (JSC::DFG::performInvalidationPointInjection):
      * dfg/DFGInvalidationPointInjectionPhase.h: Added.
      * dfg/DFGJITCode.h:
      * dfg/DFGJITCompiler.cpp:
      (JSC::DFG::JITCompiler::linkOSRExits):
      (JSC::DFG::JITCompiler::link):
      * dfg/DFGJITCompiler.h:
      * dfg/DFGJumpReplacement.cpp: Added.
      (JSC::DFG::JumpReplacement::fire):
      * dfg/DFGJumpReplacement.h: Added.
      (JSC::DFG::JumpReplacement::JumpReplacement):
      * dfg/DFGNodeType.h:
      * dfg/DFGOSRExitCompilationInfo.h:
      * dfg/DFGOperations.cpp:
      * dfg/DFGPlan.cpp:
      (JSC::DFG::Plan::compileInThreadImpl):
      (JSC::DFG::Plan::reallyAdd):
      * dfg/DFGPredictionPropagationPhase.cpp:
      (JSC::DFG::PredictionPropagationPhase::propagate):
      * dfg/DFGSafeToExecute.h:
      (JSC::DFG::safeToExecute):
      * dfg/DFGSpeculativeJIT.cpp:
      (JSC::DFG::SpeculativeJIT::emitInvalidationPoint):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleObjectEquality):
      (JSC::DFG::SpeculativeJIT::compileGetByValOnString):
      * dfg/DFGSpeculativeJIT.h:
      (JSC::DFG::SpeculativeJIT::masqueradesAsUndefinedWatchpointIsStillValid):
      (JSC::DFG::SpeculativeJIT::speculateStringObjectForStructure):
      * dfg/DFGSpeculativeJIT32_64.cpp:
      (JSC::DFG::SpeculativeJIT::nonSpeculativeNonPeepholeCompareNull):
      (JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranchNull):
      (JSC::DFG::SpeculativeJIT::compileObjectEquality):
      (JSC::DFG::SpeculativeJIT::compileObjectToObjectOrOtherEquality):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleObjectToObjectOrOtherEquality):
      (JSC::DFG::SpeculativeJIT::compileObjectOrOtherLogicalNot):
      (JSC::DFG::SpeculativeJIT::emitObjectOrOtherBranch):
      (JSC::DFG::SpeculativeJIT::compile):
      * dfg/DFGSpeculativeJIT64.cpp:
      (JSC::DFG::SpeculativeJIT::nonSpeculativeNonPeepholeCompareNull):
      (JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranchNull):
      (JSC::DFG::SpeculativeJIT::compileObjectEquality):
      (JSC::DFG::SpeculativeJIT::compileObjectToObjectOrOtherEquality):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleObjectToObjectOrOtherEquality):
      (JSC::DFG::SpeculativeJIT::compileObjectOrOtherLogicalNot):
      (JSC::DFG::SpeculativeJIT::emitObjectOrOtherBranch):
      (JSC::DFG::SpeculativeJIT::compile):
      * dfg/DFGWatchpointCollectionPhase.cpp: Added.
      (JSC::DFG::WatchpointCollectionPhase::WatchpointCollectionPhase):
      (JSC::DFG::WatchpointCollectionPhase::run):
      (JSC::DFG::WatchpointCollectionPhase::handle):
      (JSC::DFG::WatchpointCollectionPhase::handleEdge):
      (JSC::DFG::WatchpointCollectionPhase::handleMasqueradesAsUndefined):
      (JSC::DFG::WatchpointCollectionPhase::handleStringGetByVal):
      (JSC::DFG::WatchpointCollectionPhase::addLazily):
      (JSC::DFG::WatchpointCollectionPhase::globalObject):
      (JSC::DFG::performWatchpointCollection):
      * dfg/DFGWatchpointCollectionPhase.h: Added.
      * ftl/FTLCapabilities.cpp:
      (JSC::FTL::canCompile):
      * ftl/FTLLowerDFGToLLVM.cpp:
      (JSC::FTL::LowerDFGToLLVM::compileNode):
      (JSC::FTL::LowerDFGToLLVM::compileStructureTransitionWatchpoint):
      (JSC::FTL::LowerDFGToLLVM::compileGetByVal):
      (JSC::FTL::LowerDFGToLLVM::compileGlobalVarWatchpoint):
      (JSC::FTL::LowerDFGToLLVM::compileCompareEqConstant):
      (JSC::FTL::LowerDFGToLLVM::compileCompareStrictEq):
      (JSC::FTL::LowerDFGToLLVM::compileCompareStrictEqConstant):
      (JSC::FTL::LowerDFGToLLVM::compileInvalidationPoint):
      (JSC::FTL::LowerDFGToLLVM::equalNullOrUndefined):
      (JSC::FTL::LowerDFGToLLVM::speculateNonNullObject):
      * jit/JITOperations.cpp:
      * jit/JumpReplacementWatchpoint.cpp: Removed.
      * jit/JumpReplacementWatchpoint.h: Removed.
      
      
      
      git-svn-id: http://svn.webkit.org/repository/webkit/trunk@158304 268f45cc-cd09-0410-ab3c-d52691b4dbfc
      d84425d1
  2. 25 Jul, 2013 2 commits
    • oliver@apple.com's avatar
      fourthTier: DFG should do a high-level LICM before going to FTL · e17632e6
      oliver@apple.com authored
      https://bugs.webkit.org/show_bug.cgi?id=118749
      
      Reviewed by Oliver Hunt.
      
      Implements LICM hoisting for nodes that never write anything and never read
      things that are clobbered by the loop. There are some other preconditions for
      hoisting, see DFGLICMPhase.cpp.
      
      Also did a few fixes:
      
      - ClobberSet::add was failing to switch Super entries to Direct entries in
        some cases.
      
      - DFGClobberize.cpp needed to #include "Operations.h".
      
      - DCEPhase needs to process the graph in reverse DFS order, when we're in SSA.
      
      - AbstractInterpreter can now execute a Node without knowing its indexInBlock.
        Knowing the indexInBlock is an optional optimization that all other clients
        of AI still opt into, but LICM doesn't.
      
      This makes the FTL a 2.19x speed-up on imaging-gaussian-blur.
      
      * JavaScriptCore.xcodeproj/project.pbxproj:
      * dfg/DFGAbstractInterpreter.h:
      (AbstractInterpreter):
      * dfg/DFGAbstractInterpreterInlines.h:
      (JSC::DFG::::executeEffects):
      (JSC::DFG::::execute):
      (DFG):
      (JSC::DFG::::clobberWorld):
      (JSC::DFG::::clobberStructures):
      * dfg/DFGAtTailAbstractState.cpp: Added.
      (DFG):
      (JSC::DFG::AtTailAbstractState::AtTailAbstractState):
      (JSC::DFG::AtTailAbstractState::~AtTailAbstractState):
      (JSC::DFG::AtTailAbstractState::createValueForNode):
      (JSC::DFG::AtTailAbstractState::forNode):
      * dfg/DFGAtTailAbstractState.h: Added.
      (DFG):
      (AtTailAbstractState):
      (JSC::DFG::AtTailAbstractState::initializeTo):
      (JSC::DFG::AtTailAbstractState::forNode):
      (JSC::DFG::AtTailAbstractState::variables):
      (JSC::DFG::AtTailAbstractState::block):
      (JSC::DFG::AtTailAbstractState::isValid):
      (JSC::DFG::AtTailAbstractState::setDidClobber):
      (JSC::DFG::AtTailAbstractState::setIsValid):
      (JSC::DFG::AtTailAbstractState::setBranchDirection):
      (JSC::DFG::AtTailAbstractState::setFoundConstants):
      (JSC::DFG::AtTailAbstractState::haveStructures):
      (JSC::DFG::AtTailAbstractState::setHaveStructures):
      * dfg/DFGBasicBlock.h:
      (JSC::DFG::BasicBlock::insertBeforeLast):
      * dfg/DFGBasicBlockInlines.h:
      (DFG):
      * dfg/DFGClobberSet.cpp:
      (JSC::DFG::ClobberSet::add):
      (JSC::DFG::ClobberSet::addAll):
      * dfg/DFGClobberize.cpp:
      (JSC::DFG::doesWrites):
      * dfg/DFGClobberize.h:
      (DFG):
      * dfg/DFGDCEPhase.cpp:
      (JSC::DFG::DCEPhase::DCEPhase):
      (JSC::DFG::DCEPhase::run):
      (JSC::DFG::DCEPhase::fixupBlock):
      (DCEPhase):
      * dfg/DFGEdgeDominates.h: Added.
      (DFG):
      (EdgeDominates):
      (JSC::DFG::EdgeDominates::EdgeDominates):
      (JSC::DFG::EdgeDominates::operator()):
      (JSC::DFG::EdgeDominates::result):
      (JSC::DFG::edgesDominate):
      * dfg/DFGFixupPhase.cpp:
      (JSC::DFG::FixupPhase::fixupNode):
      (JSC::DFG::FixupPhase::checkArray):
      * dfg/DFGLICMPhase.cpp: Added.
      (LICMPhase):
      (JSC::DFG::LICMPhase::LICMPhase):
      (JSC::DFG::LICMPhase::run):
      (JSC::DFG::LICMPhase::attemptHoist):
      (DFG):
      (JSC::DFG::performLICM):
      * dfg/DFGLICMPhase.h: Added.
      (DFG):
      * dfg/DFGPlan.cpp:
      (JSC::DFG::Plan::compileInThreadImpl):
      
      git-svn-id: http://svn.webkit.org/repository/webkit/trunk@153295 268f45cc-cd09-0410-ab3c-d52691b4dbfc
      e17632e6
    • oliver@apple.com's avatar
      fourthTier: DFG Nodes should be able to abstractly tell you what they read and what they write · a0caeaa4
      oliver@apple.com authored
      https://bugs.webkit.org/show_bug.cgi?id=118910
      
      Source/JavaScriptCore:
      
      Reviewed by Sam Weinig.
      
      Add the notion of AbstractHeap to the DFG. This is analogous to the AbstractHeap in
      the FTL, except that the FTL's AbstractHeaps are used during LLVM lowering and are
      engineered to obey LLVM TBAA logic. The FTL's AbstractHeaps are also engineered to
      be inexpensive to use (they just give you a TBAA node) but expensive to create (you
      create them all up front). FTL AbstractHeaps also don't actually give you the
      ability to reason about aliasing; they are *just* a mechanism for lowering to TBAA.
      The DFG's AbstractHeaps are engineered to be both cheap to create and cheap to use.
      They also give you aliasing machinery. The DFG AbstractHeaps are represented
      internally by a int64_t. Many comparisons between them are just integer comaprisons.
      AbstractHeaps form a three-level hierarchy (World is the supertype of everything,
      Kind with a TOP payload is a direct subtype of World, and Kind with a non-TOP
      payload is the direct subtype of its corresponding TOP Kind).
      
      Add the notion of a ClobberSet. This is the set of AbstractHeaps that you had
      clobbered. It represents the set that results from unifying a bunch of
      AbstractHeaps, and is intended to quickly answer overlap questions: does the given
      AbstractHeap overlap any AbstractHeap in the ClobberSet? To this end, if you add an
      AbstractHeap to a set, it "directly" adds the heap itself, and "super" adds all of
      its ancestors. An AbstractHeap is said to overlap a set if any direct or super
      member is equal to it, or if any of its ancestors are equal to a direct member.
      
      Example #1:
      
          - I add Variables(5). I.e. Variables is the Kind and 5 is the payload. This
            is a subtype of Variables, which is a subtype of World.
          - You query Variables. I.e. Variables with a TOP payload, which is the
            supertype of Variables(X) for any X, and a subtype of World.
      
          The set will have Variables(5) as a direct member, and Variables and World as
          super members. The Variables query will immediately return true, because
          Variables is indeed a super member.
      
      Example #2:
      
          - I add Variables(5)
          - You query NamedProperties
      
          NamedProperties is not a member at all (neither direct or super). We next
          query World. World is a member, but it's a super member, so we return false.
      
      Example #3:
      
          - I add Variables
          - You query Variables(5)
      
          The set will have Variables as a direct member, and World as a super member.
          The Variables(5) query will not find Variables(5) in the set, but then it
          will query Variables. Variables is a direct member, so we return true.
      
      Example #4:
      
          - I add Variables
          - You query NamedProperties(5)
      
          Neither NamedProperties nor NamedProperties(5) are members. We next query
          World. World is a member, but it's a super member, so we return false.
      
      Overlap queries require that either the heap being queried is in the set (either
      direct or super), or that one of its ancestors is a direct member. Another way to
      think about how this works is that two heaps A and B are said to overlap if
      A.isSubtypeOf(B) or B.isSubtypeOf(A). This is sound since heaps form a
      single-inheritance heirarchy. Consider that we wanted to implement a set that holds
      heaps and answers the question, "is any member in the set an ancestor (i.e.
      supertype) of some other heap". We would have the set contain the heaps themselves,
      and we would satisfy the query "A.isSubtypeOfAny(set)" by walking the ancestor
      chain of A, and repeatedly querying its membership in the set. This is what the
      "direct" members of our set do. Now consider the other part, where we want to ask if
      any member of the set is a descendent of a heap, or "A.isSupertypeOfAny(set)". We
      would implement this by implementing set.add(B) as adding not just B but also all of
      B's ancestors; then we would answer A.isSupertypeOfAny(set) by just checking if A is
      in the set. With two such sets - one that answers isSubtypeOfAny() and another that
      answers isSupertypeOfAny() - we could answer the "do any of my heaps overlap your
      heap" question. ClobberSet does this, but combines the two sets into a single
      HashMap. The HashMap's value, "direct", means that the key is a member of both the
      supertype set and the subtype set; if it's false then it's only a member of one of
      them.
      
      Finally, this adds a functorized clobberize() method that adds the read and write
      clobbers of a DFG::Node to read and write functors. Common functors for adding to
      ClobberSets, querying overlap, and doing nothing are provided. Convenient wrappers
      are also provided. This allows you to say things like:
      
          ClobberSet set;
          addWrites(graph, node1, set);
          if (readsOverlap(graph, node2, set))
              // We know that node1 may write to something that node2 may read from.
      
      Currently this facility is only used to improve graph dumping, but it will be
      instrumental in both LICM and GVN. In the future, I want to completely kill the
      NodeClobbersWorld and NodeMightClobber flags, and eradicate CSEPhase's hackish way
      of accomplishing almost exactly what AbstractHeap gives you.
      
      * JavaScriptCore.xcodeproj/project.pbxproj:
      * dfg/DFGAbstractHeap.cpp: Added.
      (DFG):
      (JSC::DFG::AbstractHeap::Payload::dump):
      (JSC::DFG::AbstractHeap::dump):
      (WTF):
      (WTF::printInternal):
      * dfg/DFGAbstractHeap.h: Added.
      (DFG):
      (AbstractHeap):
      (Payload):
      (JSC::DFG::AbstractHeap::Payload::Payload):
      (JSC::DFG::AbstractHeap::Payload::top):
      (JSC::DFG::AbstractHeap::Payload::isTop):
      (JSC::DFG::AbstractHeap::Payload::value):
      (JSC::DFG::AbstractHeap::Payload::valueImpl):
      (JSC::DFG::AbstractHeap::Payload::operator==):
      (JSC::DFG::AbstractHeap::Payload::operator!=):
      (JSC::DFG::AbstractHeap::Payload::operator<):
      (JSC::DFG::AbstractHeap::Payload::isDisjoint):
      (JSC::DFG::AbstractHeap::Payload::overlaps):
      (JSC::DFG::AbstractHeap::AbstractHeap):
      (JSC::DFG::AbstractHeap::operator!):
      (JSC::DFG::AbstractHeap::kind):
      (JSC::DFG::AbstractHeap::payload):
      (JSC::DFG::AbstractHeap::isDisjoint):
      (JSC::DFG::AbstractHeap::overlaps):
      (JSC::DFG::AbstractHeap::supertype):
      (JSC::DFG::AbstractHeap::hash):
      (JSC::DFG::AbstractHeap::operator==):
      (JSC::DFG::AbstractHeap::operator!=):
      (JSC::DFG::AbstractHeap::operator<):
      (JSC::DFG::AbstractHeap::isHashTableDeletedValue):
      (JSC::DFG::AbstractHeap::payloadImpl):
      (JSC::DFG::AbstractHeap::encode):
      (JSC::DFG::AbstractHeapHash::hash):
      (JSC::DFG::AbstractHeapHash::equal):
      (AbstractHeapHash):
      (WTF):
      * dfg/DFGClobberSet.cpp: Added.
      (DFG):
      (JSC::DFG::ClobberSet::ClobberSet):
      (JSC::DFG::ClobberSet::~ClobberSet):
      (JSC::DFG::ClobberSet::add):
      (JSC::DFG::ClobberSet::addAll):
      (JSC::DFG::ClobberSet::contains):
      (JSC::DFG::ClobberSet::overlaps):
      (JSC::DFG::ClobberSet::clear):
      (JSC::DFG::ClobberSet::direct):
      (JSC::DFG::ClobberSet::super):
      (JSC::DFG::ClobberSet::dump):
      (JSC::DFG::ClobberSet::setOf):
      (JSC::DFG::addReads):
      (JSC::DFG::addWrites):
      (JSC::DFG::addReadsAndWrites):
      (JSC::DFG::readsOverlap):
      (JSC::DFG::writesOverlap):
      * dfg/DFGClobberSet.h: Added.
      (DFG):
      (ClobberSet):
      (JSC::DFG::ClobberSet::isEmpty):
      (ClobberSetAdd):
      (JSC::DFG::ClobberSetAdd::ClobberSetAdd):
      (JSC::DFG::ClobberSetAdd::operator()):
      (ClobberSetOverlaps):
      (JSC::DFG::ClobberSetOverlaps::ClobberSetOverlaps):
      (JSC::DFG::ClobberSetOverlaps::operator()):
      (JSC::DFG::ClobberSetOverlaps::result):
      * dfg/DFGClobberize.cpp: Added.
      (DFG):
      (JSC::DFG::didWrites):
      * dfg/DFGClobberize.h: Added.
      (DFG):
      (JSC::DFG::clobberize):
      (NoOpClobberize):
      (JSC::DFG::NoOpClobberize::NoOpClobberize):
      (JSC::DFG::NoOpClobberize::operator()):
      (CheckClobberize):
      (JSC::DFG::CheckClobberize::CheckClobberize):
      (JSC::DFG::CheckClobberize::operator()):
      (JSC::DFG::CheckClobberize::result):
      * dfg/DFGGraph.cpp:
      (JSC::DFG::Graph::dump):
      
      Source/WTF:
      
      Reviewed by Sam Weinig.
      
      Fix compile goof in sortedListDump().
      
      * wtf/ListDump.h:
      (WTF::sortedListDump):
      
      Conflicts:
      	Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
      
      git-svn-id: http://svn.webkit.org/repository/webkit/trunk@153294 268f45cc-cd09-0410-ab3c-d52691b4dbfc
      a0caeaa4