PolymorphicAccess should buffer AccessCases before regenerating
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 12 Apr 2016 20:06:26 +0000 (20:06 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 12 Apr 2016 20:06:26 +0000 (20:06 +0000)
https://bugs.webkit.org/show_bug.cgi?id=156457

Reviewed by Benjamin Poulain.

Source/JavaScriptCore:

Prior to this change, whenever we added an AccessCase to a PolymorphicAccess, we would
regenerate the whole stub. That meant that we'd do O(N^2) work for N access cases.

One way to fix this is to have each AccessCase generate a stub just for itself, which
cascades down to the already-generated cases. But that removes the binary switch
optimization, which makes the IC perform great even when there are many cases.

This change fixes the issue by buffering access cases. When we take slow path and try to add
a new case, the StructureStubInfo will usually just buffer the new case without generating
new code. We simply guarantee that after we buffer a case, we will take at most
Options::repatchBufferingCountdown() slow path calls before generating code for it. That
option is currently 7. Taking 7 more slow paths means that we have 7 more opportunities to
gather more access cases, or to realize that this IC is too crazy to bother with.

This change ensures that the DFG still gets the same kind of profiling. This is because the
buffered AccessCases are still part of PolymorphicAccess and so are still scanned by
GetByIdStatus and PutByIdStatus. The fact that the AccessCases hadn't been generated and so
hadn't executed doesn't change much. Mainly, it increases the likelihood that the DFG will
see an access case that !couldStillSucceed(). The DFG's existing profile parsing logic can
handle this just fine.

There are a bunch of algorithmic changes here. StructureStubInfo now caches the set of
structures that it has seen as a guard to prevent adding lots of redundant cases, in case
we see the same 7 cases after buffering the first one. This cache means we won't wastefully
allocate 7 identical AccessCase instances. PolymorphicAccess is now restructured around
having separate addCase() and regenerate() calls. That means a bit more moving data around.
So far that seems OK for performance, probably since it's O(N) work rather than O(N^2) work.
There is room for improvement for future patches, to be sure.

This is benchmarking as slightly positive or neutral on JS benchmarks. It's meant to reduce
pathologies I saw in page loads.

* bytecode/GetByIdStatus.cpp:
(JSC::GetByIdStatus::computeForStubInfoWithoutExitSiteFeedback):
* bytecode/PolymorphicAccess.cpp:
(JSC::PolymorphicAccess::PolymorphicAccess):
(JSC::PolymorphicAccess::~PolymorphicAccess):
(JSC::PolymorphicAccess::addCases):
(JSC::PolymorphicAccess::addCase):
(JSC::PolymorphicAccess::visitWeak):
(JSC::PolymorphicAccess::dump):
(JSC::PolymorphicAccess::commit):
(JSC::PolymorphicAccess::regenerate):
(JSC::PolymorphicAccess::aboutToDie):
(WTF::printInternal):
(JSC::PolymorphicAccess::regenerateWithCases): Deleted.
(JSC::PolymorphicAccess::regenerateWithCase): Deleted.
* bytecode/PolymorphicAccess.h:
(JSC::AccessCase::isGetter):
(JSC::AccessCase::callLinkInfo):
(JSC::AccessGenerationResult::AccessGenerationResult):
(JSC::AccessGenerationResult::madeNoChanges):
(JSC::AccessGenerationResult::gaveUp):
(JSC::AccessGenerationResult::buffered):
(JSC::AccessGenerationResult::generatedNewCode):
(JSC::AccessGenerationResult::generatedFinalCode):
(JSC::AccessGenerationResult::shouldGiveUpNow):
(JSC::AccessGenerationResult::generatedSomeCode):
(JSC::PolymorphicAccess::isEmpty):
(JSC::PolymorphicAccess::size):
(JSC::PolymorphicAccess::at):
* bytecode/PutByIdStatus.cpp:
(JSC::PutByIdStatus::computeForStubInfo):
* bytecode/StructureStubInfo.cpp:
(JSC::StructureStubInfo::StructureStubInfo):
(JSC::StructureStubInfo::addAccessCase):
(JSC::StructureStubInfo::reset):
(JSC::StructureStubInfo::visitWeakReferences):
* bytecode/StructureStubInfo.h:
(JSC::StructureStubInfo::considerCaching):
(JSC::StructureStubInfo::willRepatch): Deleted.
(JSC::StructureStubInfo::willCoolDown): Deleted.
* jit/JITOperations.cpp:
* jit/Repatch.cpp:
(JSC::tryCacheGetByID):
(JSC::repatchGetByID):
(JSC::tryCachePutByID):
(JSC::repatchPutByID):
(JSC::tryRepatchIn):
(JSC::repatchIn):
* runtime/JSCJSValue.h:
* runtime/JSCJSValueInlines.h:
(JSC::JSValue::putByIndex):
(JSC::JSValue::structureOrNull):
(JSC::JSValue::structureOrUndefined):
* runtime/Options.h:

Source/WTF:

* wtf/TinyPtrSet.h:
(WTF::TinyPtrSet::add): Add a helpful comment because I had forgotten what the bool return meant.

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

14 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/GetByIdStatus.cpp
Source/JavaScriptCore/bytecode/PolymorphicAccess.cpp
Source/JavaScriptCore/bytecode/PolymorphicAccess.h
Source/JavaScriptCore/bytecode/PutByIdStatus.cpp
Source/JavaScriptCore/bytecode/StructureStubInfo.cpp
Source/JavaScriptCore/bytecode/StructureStubInfo.h
Source/JavaScriptCore/jit/JITOperations.cpp
Source/JavaScriptCore/jit/Repatch.cpp
Source/JavaScriptCore/runtime/JSCJSValue.h
Source/JavaScriptCore/runtime/JSCJSValueInlines.h
Source/JavaScriptCore/runtime/Options.h
Source/WTF/ChangeLog
Source/WTF/wtf/TinyPtrSet.h

index 1cfb8a8..66e07f4 100644 (file)
@@ -1,3 +1,97 @@
+2016-04-11  Filip Pizlo  <fpizlo@apple.com>
+
+        PolymorphicAccess should buffer AccessCases before regenerating
+        https://bugs.webkit.org/show_bug.cgi?id=156457
+
+        Reviewed by Benjamin Poulain.
+
+        Prior to this change, whenever we added an AccessCase to a PolymorphicAccess, we would
+        regenerate the whole stub. That meant that we'd do O(N^2) work for N access cases.
+
+        One way to fix this is to have each AccessCase generate a stub just for itself, which
+        cascades down to the already-generated cases. But that removes the binary switch
+        optimization, which makes the IC perform great even when there are many cases.
+
+        This change fixes the issue by buffering access cases. When we take slow path and try to add
+        a new case, the StructureStubInfo will usually just buffer the new case without generating
+        new code. We simply guarantee that after we buffer a case, we will take at most
+        Options::repatchBufferingCountdown() slow path calls before generating code for it. That
+        option is currently 7. Taking 7 more slow paths means that we have 7 more opportunities to
+        gather more access cases, or to realize that this IC is too crazy to bother with.
+
+        This change ensures that the DFG still gets the same kind of profiling. This is because the
+        buffered AccessCases are still part of PolymorphicAccess and so are still scanned by
+        GetByIdStatus and PutByIdStatus. The fact that the AccessCases hadn't been generated and so
+        hadn't executed doesn't change much. Mainly, it increases the likelihood that the DFG will
+        see an access case that !couldStillSucceed(). The DFG's existing profile parsing logic can
+        handle this just fine.
+        
+        There are a bunch of algorithmic changes here. StructureStubInfo now caches the set of
+        structures that it has seen as a guard to prevent adding lots of redundant cases, in case
+        we see the same 7 cases after buffering the first one. This cache means we won't wastefully
+        allocate 7 identical AccessCase instances. PolymorphicAccess is now restructured around
+        having separate addCase() and regenerate() calls. That means a bit more moving data around.
+        So far that seems OK for performance, probably since it's O(N) work rather than O(N^2) work.
+        There is room for improvement for future patches, to be sure.
+        
+        This is benchmarking as slightly positive or neutral on JS benchmarks. It's meant to reduce
+        pathologies I saw in page loads.
+
+        * bytecode/GetByIdStatus.cpp:
+        (JSC::GetByIdStatus::computeForStubInfoWithoutExitSiteFeedback):
+        * bytecode/PolymorphicAccess.cpp:
+        (JSC::PolymorphicAccess::PolymorphicAccess):
+        (JSC::PolymorphicAccess::~PolymorphicAccess):
+        (JSC::PolymorphicAccess::addCases):
+        (JSC::PolymorphicAccess::addCase):
+        (JSC::PolymorphicAccess::visitWeak):
+        (JSC::PolymorphicAccess::dump):
+        (JSC::PolymorphicAccess::commit):
+        (JSC::PolymorphicAccess::regenerate):
+        (JSC::PolymorphicAccess::aboutToDie):
+        (WTF::printInternal):
+        (JSC::PolymorphicAccess::regenerateWithCases): Deleted.
+        (JSC::PolymorphicAccess::regenerateWithCase): Deleted.
+        * bytecode/PolymorphicAccess.h:
+        (JSC::AccessCase::isGetter):
+        (JSC::AccessCase::callLinkInfo):
+        (JSC::AccessGenerationResult::AccessGenerationResult):
+        (JSC::AccessGenerationResult::madeNoChanges):
+        (JSC::AccessGenerationResult::gaveUp):
+        (JSC::AccessGenerationResult::buffered):
+        (JSC::AccessGenerationResult::generatedNewCode):
+        (JSC::AccessGenerationResult::generatedFinalCode):
+        (JSC::AccessGenerationResult::shouldGiveUpNow):
+        (JSC::AccessGenerationResult::generatedSomeCode):
+        (JSC::PolymorphicAccess::isEmpty):
+        (JSC::PolymorphicAccess::size):
+        (JSC::PolymorphicAccess::at):
+        * bytecode/PutByIdStatus.cpp:
+        (JSC::PutByIdStatus::computeForStubInfo):
+        * bytecode/StructureStubInfo.cpp:
+        (JSC::StructureStubInfo::StructureStubInfo):
+        (JSC::StructureStubInfo::addAccessCase):
+        (JSC::StructureStubInfo::reset):
+        (JSC::StructureStubInfo::visitWeakReferences):
+        * bytecode/StructureStubInfo.h:
+        (JSC::StructureStubInfo::considerCaching):
+        (JSC::StructureStubInfo::willRepatch): Deleted.
+        (JSC::StructureStubInfo::willCoolDown): Deleted.
+        * jit/JITOperations.cpp:
+        * jit/Repatch.cpp:
+        (JSC::tryCacheGetByID):
+        (JSC::repatchGetByID):
+        (JSC::tryCachePutByID):
+        (JSC::repatchPutByID):
+        (JSC::tryRepatchIn):
+        (JSC::repatchIn):
+        * runtime/JSCJSValue.h:
+        * runtime/JSCJSValueInlines.h:
+        (JSC::JSValue::putByIndex):
+        (JSC::JSValue::structureOrNull):
+        (JSC::JSValue::structureOrUndefined):
+        * runtime/Options.h:
+
 2016-04-12  Saam barati  <sbarati@apple.com>
 
         There is a race with the compiler thread and the main thread with result profiles
index dca98aa..c69514c 100644 (file)
@@ -220,11 +220,11 @@ GetByIdStatus GetByIdStatus::computeForStubInfoWithoutExitSiteFeedback(
                     break;
                 }
                 case AccessCase::Getter: {
-                    CallLinkInfo* callLinkInfo = access.callLinkInfo();
-                    ASSERT(callLinkInfo);
-                    callLinkStatus = std::make_unique<CallLinkStatus>(
-                        CallLinkStatus::computeFor(
-                            locker, profiledBlock, *callLinkInfo, callExitSiteData));
+                    callLinkStatus = std::make_unique<CallLinkStatus>();
+                    if (CallLinkInfo* callLinkInfo = access.callLinkInfo()) {
+                        *callLinkStatus = CallLinkStatus::computeFor(
+                            locker, profiledBlock, *callLinkInfo, callExitSiteData);
+                    }
                     break;
                 }
                 default: {
index a03bf88..cd93e6c 100644 (file)
@@ -1392,7 +1392,7 @@ void AccessCase::generateImpl(AccessGenerationState& state)
 PolymorphicAccess::PolymorphicAccess() { }
 PolymorphicAccess::~PolymorphicAccess() { }
 
-AccessGenerationResult PolymorphicAccess::regenerateWithCases(
+AccessGenerationResult PolymorphicAccess::addCases(
     VM& vm, CodeBlock* codeBlock, StructureStubInfo& stubInfo, const Identifier& ident,
     Vector<std::unique_ptr<AccessCase>> originalCasesToAdd)
 {
@@ -1438,76 +1438,26 @@ AccessGenerationResult PolymorphicAccess::regenerateWithCases(
     if (casesToAdd.isEmpty())
         return AccessGenerationResult::MadeNoChanges;
 
-    // Now construct the list of cases as they should appear if we are successful. This means putting
-    // all of the previous cases in this list in order but excluding those that can be replaced, and
-    // then adding the new cases.
-    ListType newCases;
-    for (auto& oldCase : m_list) {
-        // Ignore old cases that cannot possibly succeed anymore.
-        if (!oldCase->couldStillSucceed())
-            continue;
-
-        // Figure out if this is replaced by any new cases.
-        bool found = false;
-        for (auto& caseToAdd : casesToAdd) {
-            if (caseToAdd->canReplace(*oldCase)) {
-                found = true;
-                break;
-            }
-        }
-        if (found)
-            continue;
-        
-        newCases.append(oldCase->clone());
+    // Now add things to the new list. Note that at this point, we will still have old cases that
+    // may be replaced by the new ones. That's fine. We will sort that out when we regenerate.
+    for (auto& caseToAdd : casesToAdd) {
+        commit(vm, m_watchpoints, codeBlock, stubInfo, ident, *caseToAdd);
+        m_list.append(WTFMove(caseToAdd));
     }
-    for (auto& caseToAdd : casesToAdd)
-        newCases.append(WTFMove(caseToAdd));
-
-    if (verbose)
-        dataLog("newCases: ", listDump(newCases), "\n");
     
-    // See if we are close to having too many cases and if some of those cases can be subsumed by a
-    // megamorphic load.
-    if (newCases.size() >= Options::maxAccessVariantListSize()) {
-        unsigned numSelfLoads = 0;
-        for (auto& newCase : newCases) {
-            if (newCase->canBeReplacedByMegamorphicLoad())
-                numSelfLoads++;
-        }
-        
-        if (numSelfLoads >= Options::megamorphicLoadCost()) {
-            if (auto mega = AccessCase::megamorphicLoad(vm, codeBlock)) {
-                newCases.removeAllMatching(
-                    [&] (std::unique_ptr<AccessCase>& newCase) -> bool {
-                        return newCase->canBeReplacedByMegamorphicLoad();
-                    });
-                
-                newCases.append(WTFMove(mega));
-            }
-        }
-    }
-
-    if (newCases.size() > Options::maxAccessVariantListSize()) {
-        if (verbose)
-            dataLog("Too many cases.\n");
-        return AccessGenerationResult::GaveUp;
-    }
-
-    MacroAssemblerCodePtr result = regenerate(vm, codeBlock, stubInfo, ident, newCases);
-    if (!result)
-        return AccessGenerationResult::GaveUp;
+    if (verbose)
+        dataLog("After addCases: m_list: ", listDump(m_list), "\n");
 
-    m_list = WTFMove(newCases);
-    return result;
+    return AccessGenerationResult::Buffered;
 }
 
-AccessGenerationResult PolymorphicAccess::regenerateWithCase(
+AccessGenerationResult PolymorphicAccess::addCase(
     VM& vm, CodeBlock* codeBlock, StructureStubInfo& stubInfo, const Identifier& ident,
     std::unique_ptr<AccessCase> newAccess)
 {
     Vector<std::unique_ptr<AccessCase>> newAccesses;
     newAccesses.append(WTFMove(newAccess));
-    return regenerateWithCases(vm, codeBlock, stubInfo, ident, WTFMove(newAccesses));
+    return addCases(vm, codeBlock, stubInfo, ident, WTFMove(newAccesses));
 }
 
 bool PolymorphicAccess::visitWeak(VM& vm) const
@@ -1534,14 +1484,32 @@ void PolymorphicAccess::dump(PrintStream& out) const
     out.print("]");
 }
 
-MacroAssemblerCodePtr PolymorphicAccess::regenerate(
-    VM& vm, CodeBlock* codeBlock, StructureStubInfo& stubInfo, const Identifier& ident,
-    PolymorphicAccess::ListType& cases)
+void PolymorphicAccess::commit(
+    VM& vm, std::unique_ptr<WatchpointsOnStructureStubInfo>& watchpoints, CodeBlock* codeBlock,
+    StructureStubInfo& stubInfo, const Identifier& ident, AccessCase& accessCase)
+{
+    // NOTE: We currently assume that this is relatively rare. It mainly arises for accesses to
+    // properties on DOM nodes. For sure we cache many DOM node accesses, but even in
+    // Real Pages (TM), we appear to spend most of our time caching accesses to properties on
+    // vanilla objects or exotic objects from within JSC (like Arguments, those are super popular).
+    // Those common kinds of JSC object accesses don't hit this case.
+    
+    for (WatchpointSet* set : accessCase.commit(vm, ident)) {
+        Watchpoint* watchpoint =
+            WatchpointsOnStructureStubInfo::ensureReferenceAndAddWatchpoint(
+                watchpoints, codeBlock, &stubInfo, ObjectPropertyCondition());
+        
+        set->add(watchpoint);
+    }
+}
+
+AccessGenerationResult PolymorphicAccess::regenerate(
+    VM& vm, CodeBlock* codeBlock, StructureStubInfo& stubInfo, const Identifier& ident)
 {
     SuperSamplerScope superSamplerScope(false);
     
     if (verbose)
-        dataLog("Generating code for cases: ", listDump(cases), "\n");
+        dataLog("Regenerate with m_list: ", listDump(m_list), "\n");
     
     AccessGenerationState state;
 
@@ -1572,14 +1540,73 @@ MacroAssemblerCodePtr PolymorphicAccess::regenerate(
     state.preservedReusedRegisterState =
         allocator.preserveReusedRegistersByPushing(jit, ScratchRegisterAllocator::ExtraStackSpace::NoExtraSpace);
 
+    // Regenerating is our opportunity to figure out what our list of cases should look like. We
+    // do this here. The newly produced 'cases' list may be smaller than m_list. We don't edit
+    // m_list in-place because we may still fail, in which case we want the PolymorphicAccess object
+    // to be unmutated. For sure, we want it to hang onto any data structures that may be referenced
+    // from the code of the current stub (aka previous).
+    ListType cases;
+    for (unsigned i = 0; i < m_list.size(); ++i) {
+        AccessCase& someCase = *m_list[i];
+        // Ignore cases that cannot possibly succeed anymore.
+        if (!someCase.couldStillSucceed())
+            continue;
+        
+        // Figure out if this is replaced by any later case.
+        bool found = false;
+        for (unsigned j = i + 1; j < m_list.size(); ++j) {
+            if (m_list[j]->canReplace(someCase)) {
+                found = true;
+                break;
+            }
+        }
+        if (found)
+            continue;
+        
+        // FIXME: Do we have to clone cases that aren't generated? Maybe we can just take those
+        // from m_list, since we don't have to keep those alive if we fail.
+        // https://bugs.webkit.org/show_bug.cgi?id=156493
+        cases.append(someCase.clone());
+    }
+    
+    if (verbose)
+        dataLog("In regenerate: cases: ", listDump(cases), "\n");
+    
+    // Now that we've removed obviously unnecessary cases, we can check if the megamorphic load
+    // optimization is applicable. Note that we basically tune megamorphicLoadCost according to code
+    // size. It would be faster to just allow more repatching with many load cases, and avoid the
+    // megamorphicLoad optimization, if we had infinite executable memory.
+    if (cases.size() >= Options::megamorphicLoadCost()) {
+        unsigned numSelfLoads = 0;
+        for (auto& newCase : cases) {
+            if (newCase->canBeReplacedByMegamorphicLoad())
+                numSelfLoads++;
+        }
+        
+        if (numSelfLoads >= Options::megamorphicLoadCost()) {
+            if (auto mega = AccessCase::megamorphicLoad(vm, codeBlock)) {
+                cases.removeAllMatching(
+                    [&] (std::unique_ptr<AccessCase>& newCase) -> bool {
+                        return newCase->canBeReplacedByMegamorphicLoad();
+                    });
+                
+                cases.append(WTFMove(mega));
+            }
+        }
+    }
+    
+    if (verbose)
+        dataLog("Optimized cases: ", listDump(cases), "\n");
+    
+    // At this point we're convinced that 'cases' contains the cases that we want to JIT now and we
+    // won't change that set anymore.
+    
     bool allGuardedByStructureCheck = true;
     bool hasJSGetterSetterCall = false;
-    for (auto& entry : cases) {
-        for (WatchpointSet* set : entry->commit(vm, ident))
-            set->add(state.addWatchpoint());
-        
-        allGuardedByStructureCheck &= entry->guardedByStructureCheck();
-        if (entry->type() == AccessCase::Getter || entry->type() == AccessCase::Setter)
+    for (auto& newCase : cases) {
+        commit(vm, state.watchpoints, codeBlock, stubInfo, ident, *newCase);
+        allGuardedByStructureCheck &= newCase->guardedByStructureCheck();
+        if (newCase->type() == AccessCase::Getter || newCase->type() == AccessCase::Setter)
             hasJSGetterSetterCall = true;
     }
 
@@ -1677,7 +1704,7 @@ MacroAssemblerCodePtr PolymorphicAccess::regenerate(
     if (linkBuffer.didFailToAllocate()) {
         if (verbose)
             dataLog("Did fail to allocate.\n");
-        return MacroAssemblerCodePtr();
+        return AccessGenerationResult::GaveUp;
     }
 
     CodeLocationLabel successLabel =
@@ -1707,12 +1734,22 @@ MacroAssemblerCodePtr PolymorphicAccess::regenerate(
         m_weakReferences = std::make_unique<Vector<WriteBarrier<JSCell>>>(WTFMove(state.weakReferences));
     if (verbose)
         dataLog("Returning: ", code.code(), "\n");
-    return code.code();
+    
+    m_list = WTFMove(cases);
+    
+    AccessGenerationResult::Kind resultKind;
+    if (m_list.size() >= Options::maxAccessVariantListSize())
+        resultKind = AccessGenerationResult::GeneratedFinalCode;
+    else
+        resultKind = AccessGenerationResult::GeneratedNewCode;
+    
+    return AccessGenerationResult(resultKind, code.code());
 }
 
 void PolymorphicAccess::aboutToDie()
 {
-    m_stubRoutine->aboutToDie();
+    if (m_stubRoutine)
+        m_stubRoutine->aboutToDie();
 }
 
 } // namespace JSC
@@ -1730,9 +1767,15 @@ void printInternal(PrintStream& out, AccessGenerationResult::Kind kind)
     case AccessGenerationResult::GaveUp:
         out.print("GaveUp");
         return;
+    case AccessGenerationResult::Buffered:
+        out.print("Buffered");
+        return;
     case AccessGenerationResult::GeneratedNewCode:
         out.print("GeneratedNewCode");
         return;
+    case AccessGenerationResult::GeneratedFinalCode:
+        out.print("GeneratedFinalCode");
+        return;
     }
     
     RELEASE_ASSERT_NOT_REACHED();
index 9e96da9..26f9fa8 100644 (file)
@@ -216,6 +216,8 @@ public:
         }
     }
 
+    // This can return null even for a getter/setter, if it hasn't been generated yet. That's
+    // actually somewhat likely because of how we do buffering of new cases.
     CallLinkInfo* callLinkInfo() const
     {
         if (!m_rareData)
@@ -309,7 +311,9 @@ public:
     enum Kind {
         MadeNoChanges,
         GaveUp,
-        GeneratedNewCode
+        Buffered,
+        GeneratedNewCode,
+        GeneratedFinalCode // Generated so much code that we never want to generate code again.
     };
     
     AccessGenerationResult()
@@ -319,13 +323,15 @@ public:
     AccessGenerationResult(Kind kind)
         : m_kind(kind)
     {
-        ASSERT(kind != GeneratedNewCode);
+        RELEASE_ASSERT(kind != GeneratedNewCode);
+        RELEASE_ASSERT(kind != GeneratedFinalCode);
     }
     
-    AccessGenerationResult(MacroAssemblerCodePtr code)
-        : m_kind(GeneratedNewCode)
+    AccessGenerationResult(Kind kind, MacroAssemblerCodePtr code)
+        : m_kind(kind)
         , m_code(code)
     {
+        RELEASE_ASSERT(kind == GeneratedNewCode || kind == GeneratedFinalCode);
         RELEASE_ASSERT(code);
     }
     
@@ -350,7 +356,15 @@ public:
     
     bool madeNoChanges() const { return m_kind == MadeNoChanges; }
     bool gaveUp() const { return m_kind == GaveUp; }
+    bool buffered() const { return m_kind == Buffered; }
     bool generatedNewCode() const { return m_kind == GeneratedNewCode; }
+    bool generatedFinalCode() const { return m_kind == GeneratedFinalCode; }
+    
+    // If we gave up on this attempt to generate code, or if we generated the "final" code, then we
+    // should give up after this.
+    bool shouldGiveUpNow() const { return gaveUp() || generatedFinalCode(); }
+    
+    bool generatedSomeCode() const { return generatedNewCode() || generatedFinalCode(); }
     
     void dump(PrintStream&) const;
     
@@ -366,15 +380,16 @@ public:
     PolymorphicAccess();
     ~PolymorphicAccess();
 
-    // This may return null, in which case the old stub routine is left intact. You are required to
-    // pass a vector of non-null access cases. This will prune the access cases by rejecting any case
-    // in the list that is subsumed by a later case in the list.
-    AccessGenerationResult regenerateWithCases(
+    // When this fails (returns GaveUp), this will leave the old stub intact but you should not try
+    // to call this method again for that PolymorphicAccess instance.
+    AccessGenerationResult addCases(
         VM&, CodeBlock*, StructureStubInfo&, const Identifier&, Vector<std::unique_ptr<AccessCase>>);
 
-    AccessGenerationResult regenerateWithCase(
+    AccessGenerationResult addCase(
         VM&, CodeBlock*, StructureStubInfo&, const Identifier&, std::unique_ptr<AccessCase>);
     
+    AccessGenerationResult regenerate(VM&, CodeBlock*, StructureStubInfo&, const Identifier&);
+    
     bool isEmpty() const { return m_list.isEmpty(); }
     unsigned size() const { return m_list.size(); }
     const AccessCase& at(unsigned i) const { return *m_list[i]; }
@@ -401,6 +416,10 @@ private:
     friend struct AccessGenerationState;
     
     typedef Vector<std::unique_ptr<AccessCase>, 2> ListType;
+    
+    void commit(
+        VM&, std::unique_ptr<WatchpointsOnStructureStubInfo>&, CodeBlock*, StructureStubInfo&,
+        const Identifier&, AccessCase&);
 
     MacroAssemblerCodePtr regenerate(
         VM&, CodeBlock*, StructureStubInfo&, const Identifier&, ListType& cases);
index a4e18e7..43feef5 100644 (file)
@@ -225,12 +225,12 @@ PutByIdStatus PutByIdStatus::computeForStubInfo(
                     return PutByIdStatus(slowPathState);
                     
                 case ComplexGetStatus::Inlineable: {
-                    CallLinkInfo* callLinkInfo = access.callLinkInfo();
-                    ASSERT(callLinkInfo);
                     std::unique_ptr<CallLinkStatus> callLinkStatus =
-                        std::make_unique<CallLinkStatus>(
-                            CallLinkStatus::computeFor(
-                                locker, profiledBlock, *callLinkInfo, callExitSiteData));
+                        std::make_unique<CallLinkStatus>();
+                    if (CallLinkInfo* callLinkInfo = access.callLinkInfo()) {
+                        *callLinkStatus = CallLinkStatus::computeFor(
+                            locker, profiledBlock, *callLinkInfo, callExitSiteData);
+                    }
                     
                     variant = PutByIdVariant::setter(
                         structure, complexGetStatus.offset(), complexGetStatus.conditionSet(),
index a3b2c1a..f2f90ba 100644 (file)
@@ -33,6 +33,9 @@
 namespace JSC {
 
 #if ENABLE(JIT)
+
+static const bool verbose = false;
+
 StructureStubInfo::StructureStubInfo(AccessType accessType)
     : callSiteIndex(UINT_MAX)
     , accessType(accessType)
@@ -40,6 +43,7 @@ StructureStubInfo::StructureStubInfo(AccessType accessType)
     , countdown(1) // For a totally clear stub, we'll patch it after the first execution.
     , repatchCount(0)
     , numberOfCoolDowns(0)
+    , bufferingCountdown(0)
     , resetByGC(false)
     , tookSlowPath(false)
     , everConsidered(false)
@@ -109,38 +113,91 @@ AccessGenerationResult StructureStubInfo::addAccessCase(
 {
     VM& vm = *codeBlock->vm();
     
+    if (verbose)
+        dataLog("Adding access case: ", accessCase, "\n");
+    
     if (!accessCase)
         return AccessGenerationResult::GaveUp;
     
+    AccessGenerationResult result;
+    
     if (cacheType == CacheType::Stub) {
-        SuperSamplerScope superSamplerScope(true);
+        result = u.stub->addCase(vm, codeBlock, *this, ident, WTFMove(accessCase));
+        
+        if (verbose)
+            dataLog("Had stub, result: ", result, "\n");
+
+        if (!result.buffered()) {
+            bufferedStructures.clear();
+            return result;
+        }
+    } else {
+        std::unique_ptr<PolymorphicAccess> access = std::make_unique<PolymorphicAccess>();
+        
+        Vector<std::unique_ptr<AccessCase>> accessCases;
+        
+        std::unique_ptr<AccessCase> previousCase =
+            AccessCase::fromStructureStubInfo(vm, codeBlock, *this);
+        if (previousCase)
+            accessCases.append(WTFMove(previousCase));
+        
+        accessCases.append(WTFMove(accessCase));
+        
+        result = access->addCases(vm, codeBlock, *this, ident, WTFMove(accessCases));
+        
+        if (verbose)
+            dataLog("Created stub, result: ", result, "\n");
+
+        if (!result.buffered()) {
+            bufferedStructures.clear();
+            return result;
+        }
+        
+        initStub(codeBlock, WTFMove(access));
+    }
+    
+    RELEASE_ASSERT(!result.generatedSomeCode());
     
-        return u.stub->regenerateWithCase(vm, codeBlock, *this, ident, WTFMove(accessCase));
+    // If we didn't buffer any cases then bail. If this made no changes then we'll just try again
+    // subject to cool-down.
+    if (!result.buffered()) {
+        if (verbose)
+            dataLog("Didn't buffer anything, bailing.\n");
+        bufferedStructures.clear();
+        return result;
     }
     
-    std::unique_ptr<PolymorphicAccess> access = std::make_unique<PolymorphicAccess>();
+    // The buffering countdown tells us if we should be repatching now.
+    if (bufferingCountdown) {
+        if (verbose)
+            dataLog("Countdown is too high: ", bufferingCountdown, ".\n");
+        return result;
+    }
     
-    Vector<std::unique_ptr<AccessCase>> accessCases;
+    // Forget the buffered structures so that all future attempts to cache get fully handled by the
+    // PolymorphicAccess.
+    bufferedStructures.clear();
     
-    std::unique_ptr<AccessCase> previousCase =
-        AccessCase::fromStructureStubInfo(vm, codeBlock, *this);
-    if (previousCase)
-        accessCases.append(WTFMove(previousCase));
-
-    accessCases.append(WTFMove(accessCase));
-
-    AccessGenerationResult result =
-        access->regenerateWithCases(vm, codeBlock, *this, ident, WTFMove(accessCases));
-
-    if (!result.generatedNewCode())
+    result = u.stub->regenerate(vm, codeBlock, *this, ident);
+    
+    if (verbose)
+        dataLog("Regeneration result: ", result, "\n");
+    
+    RELEASE_ASSERT(!result.buffered());
+    
+    if (!result.generatedSomeCode())
         return result;
-
-    initStub(codeBlock, WTFMove(access));
+    
+    // If we generated some code then we don't want to attempt to repatch in the future until we
+    // gather enough cases.
+    bufferingCountdown = Options::repatchBufferingCountdown();
     return result;
 }
 
 void StructureStubInfo::reset(CodeBlock* codeBlock)
 {
+    bufferedStructures.clear();
+    
     if (cacheType == CacheType::Unset)
         return;
     
@@ -172,6 +229,8 @@ void StructureStubInfo::reset(CodeBlock* codeBlock)
 void StructureStubInfo::visitWeakReferences(CodeBlock* codeBlock)
 {
     VM& vm = *codeBlock->vm();
+    
+    bufferedStructures.clear();
 
     switch (cacheType) {
     case CacheType::GetByIdSelf:
index 8c4d643..390b0ed 100644 (file)
@@ -35,6 +35,7 @@
 #include "Options.h"
 #include "RegisterSet.h"
 #include "Structure.h"
+#include "StructureSet.h"
 #include "StructureStubClearingWatchpoint.h"
 
 namespace JSC {
@@ -81,13 +82,26 @@ public:
     // either entirely or just enough to ensure that those dead pointers don't get used anymore.
     void visitWeakReferences(CodeBlock*);
         
-    ALWAYS_INLINE bool considerCaching()
+    ALWAYS_INLINE bool considerCaching(Structure* structure)
     {
+        // We never cache non-cells.
+        if (!structure)
+            return false;
+        
+        // This method is called from the Optimize variants of IC slow paths. The first part of this
+        // method tries to determine if the Optimize variant should really behave like the
+        // non-Optimize variant and leave the IC untouched.
+        //
+        // If we determine that we should do something to the IC then the next order of business is
+        // to determine if this Structure would impact the IC at all. We know that it won't, if we
+        // have already buffered something on its behalf. That's what the bufferedStructures set is
+        // for.
+        
         everConsidered = true;
         if (!countdown) {
             // Check if we have been doing repatching too frequently. If so, then we should cool off
             // for a while.
-            willRepatch();
+            WTF::incrementWithSaturation(repatchCount);
             if (repatchCount > Options::repatchCountForCoolDown()) {
                 // We've been repatching too much, so don't do it now.
                 repatchCount = 0;
@@ -99,25 +113,33 @@ public:
                     static_cast<uint8_t>(Options::initialCoolDownCount()),
                     numberOfCoolDowns,
                     static_cast<uint8_t>(std::numeric_limits<uint8_t>::max() - 1));
-                willCoolDown();
-                return false;
+                WTF::incrementWithSaturation(numberOfCoolDowns);
+                
+                // We may still have had something buffered. Trigger generation now.
+                bufferingCountdown = 0;
+                return true;
+            }
+            
+            // We don't want to return false due to buffering indefinitely.
+            if (!bufferingCountdown) {
+                // Note that when this returns true, it's possible that we will not even get an
+                // AccessCase because this may cause Repatch.cpp to simply do an in-place
+                // repatching.
+                return true;
             }
-            return true;
+            
+            bufferingCountdown--;
+            
+            // Now protect the IC buffering. We want to proceed only if this is a structure that
+            // we don't already have a case buffered for. Note that if this returns true but the
+            // bufferingCountdown is not zero then we will buffer the access case for later without
+            // immediately generating code for it.
+            return bufferedStructures.add(structure);
         }
         countdown--;
         return false;
     }
 
-    ALWAYS_INLINE void willRepatch()
-    {
-        WTF::incrementWithSaturation(repatchCount);
-    }
-
-    ALWAYS_INLINE void willCoolDown()
-    {
-        WTF::incrementWithSaturation(numberOfCoolDowns);
-    }
-
     CodeLocationCall callReturnLocation;
 
     CodeOrigin codeOrigin;
@@ -132,7 +154,13 @@ public:
         } byIdSelf;
         PolymorphicAccess* stub;
     } u;
-
+    
+    // Represents those structures that already have buffered AccessCases in the PolymorphicAccess.
+    // Note that it's always safe to clear this. If we clear it prematurely, then if we see the same
+    // structure again during this buffering countdown, we will create an AccessCase object for it.
+    // That's not so bad - we'll get rid of the redundant ones once we regenerate.
+    StructureSet bufferedStructures;
+    
     struct {
         int8_t baseGPR;
 #if USE(JSVALUE32_64)
@@ -158,6 +186,7 @@ public:
     uint8_t countdown; // We repatch only when this is zero. If not zero, we decrement.
     uint8_t repatchCount;
     uint8_t numberOfCoolDowns;
+    uint8_t bufferingCountdown;
     bool resetByGC : 1;
     bool tookSlowPath : 1;
     bool everConsidered : 1;
index a6c70c5..0806277 100644 (file)
@@ -195,7 +195,7 @@ EncodedJSValue JIT_OPERATION operationTryGetByIdOptimize(ExecState* exec, Struct
     PropertySlot slot(baseValue, PropertySlot::InternalMethodType::VMInquiry);
 
     baseValue.getPropertySlot(exec, ident, slot);
-    if (stubInfo->considerCaching() && !slot.isTaintedByProxy() && (slot.isCacheableValue() || slot.isCacheableGetter() || slot.isUnset()))
+    if (stubInfo->considerCaching(baseValue.structureOrNull()) && !slot.isTaintedByProxy() && (slot.isCacheableValue() || slot.isCacheableGetter() || slot.isUnset()))
         repatchGetByID(exec, baseValue, ident, slot, *stubInfo, GetByIDKind::Pure);
 
     return JSValue::encode(slot.getPureResult());
@@ -245,7 +245,7 @@ EncodedJSValue JIT_OPERATION operationGetByIdOptimize(ExecState* exec, Structure
     PropertySlot slot(baseValue, PropertySlot::InternalMethodType::Get);
     
     bool hasResult = baseValue.getPropertySlot(exec, ident, slot);
-    if (stubInfo->considerCaching())
+    if (stubInfo->considerCaching(baseValue.structureOrNull()))
         repatchGetByID(exec, baseValue, ident, slot, *stubInfo, GetByIDKind::Normal);
     
     return JSValue::encode(hasResult? slot.getValue(exec, ident) : jsUndefined());
@@ -272,7 +272,7 @@ EncodedJSValue JIT_OPERATION operationInOptimize(ExecState* exec, StructureStubI
     
     RELEASE_ASSERT(accessType == stubInfo->accessType);
     
-    if (stubInfo->considerCaching())
+    if (stubInfo->considerCaching(asObject(base)->structure()))
         repatchIn(exec, base, ident, result, slot, *stubInfo);
     
     return JSValue::encode(jsBoolean(result));
@@ -393,7 +393,7 @@ void JIT_OPERATION operationPutByIdStrictOptimize(ExecState* exec, StructureStub
     if (accessType != static_cast<AccessType>(stubInfo->accessType))
         return;
     
-    if (stubInfo->considerCaching())
+    if (stubInfo->considerCaching(structure))
         repatchPutByID(exec, baseValue, structure, ident, slot, *stubInfo, NotDirect);
 }
 
@@ -418,7 +418,7 @@ void JIT_OPERATION operationPutByIdNonStrictOptimize(ExecState* exec, StructureS
     if (accessType != static_cast<AccessType>(stubInfo->accessType))
         return;
     
-    if (stubInfo->considerCaching())
+    if (stubInfo->considerCaching(structure))
         repatchPutByID(exec, baseValue, structure, ident, slot, *stubInfo, NotDirect);
 }
 
@@ -443,7 +443,7 @@ void JIT_OPERATION operationPutByIdDirectStrictOptimize(ExecState* exec, Structu
     if (accessType != static_cast<AccessType>(stubInfo->accessType))
         return;
     
-    if (stubInfo->considerCaching())
+    if (stubInfo->considerCaching(structure))
         repatchPutByID(exec, baseObject, structure, ident, slot, *stubInfo, Direct);
 }
 
@@ -468,7 +468,7 @@ void JIT_OPERATION operationPutByIdDirectNonStrictOptimize(ExecState* exec, Stru
     if (accessType != static_cast<AccessType>(stubInfo->accessType))
         return;
     
-    if (stubInfo->considerCaching())
+    if (stubInfo->considerCaching(structure))
         repatchPutByID(exec, baseObject, structure, ident, slot, *stubInfo, Direct);
 }
 
index fdc34c2..4bc5a15 100644 (file)
@@ -364,17 +364,14 @@ static InlineCacheAction tryCacheGetByID(ExecState* exec, JSValue baseValue, con
 
     AccessGenerationResult result = stubInfo.addAccessCase(codeBlock, propertyName, WTFMove(newCase));
 
-    if (result.gaveUp())
-        return GiveUpOnCache;
-    if (result.madeNoChanges())
-        return RetryCacheLater;
-    
-    LOG_IC((ICEvent::GetByIdReplaceWithJump, baseValue.classInfoOrNull(), propertyName));
-
-    RELEASE_ASSERT(result.code());
-    replaceWithJump(stubInfo, result.code());
+    if (result.generatedSomeCode()) {
+        LOG_IC((ICEvent::GetByIdReplaceWithJump, baseValue.classInfoOrNull(), propertyName));
+        
+        RELEASE_ASSERT(result.code());
+        replaceWithJump(stubInfo, result.code());
+    }
     
-    return RetryCacheLater;
+    return result.shouldGiveUpNow() ? GiveUpOnCache : RetryCacheLater;
 }
 
 void repatchGetByID(ExecState* exec, JSValue baseValue, const Identifier& propertyName, const PropertySlot& slot, StructureStubInfo& stubInfo, GetByIDKind kind)
@@ -515,21 +512,18 @@ static InlineCacheAction tryCachePutByID(ExecState* exec, JSValue baseValue, Str
     
     AccessGenerationResult result = stubInfo.addAccessCase(codeBlock, ident, WTFMove(newCase));
     
-    if (result.gaveUp())
-        return GiveUpOnCache;
-    if (result.madeNoChanges())
-        return RetryCacheLater;
-
-    LOG_IC((ICEvent::PutByIdReplaceWithJump, structure->classInfo(), ident));
-
-    RELEASE_ASSERT(result.code());
-    resetPutByIDCheckAndLoad(stubInfo);
-    MacroAssembler::repatchJump(
-        stubInfo.callReturnLocation.jumpAtOffset(
-            stubInfo.patch.deltaCallToJump),
-        CodeLocationLabel(result.code()));
+    if (result.generatedSomeCode()) {
+        LOG_IC((ICEvent::PutByIdReplaceWithJump, structure->classInfo(), ident));
+        
+        RELEASE_ASSERT(result.code());
+        resetPutByIDCheckAndLoad(stubInfo);
+        MacroAssembler::repatchJump(
+            stubInfo.callReturnLocation.jumpAtOffset(
+                stubInfo.patch.deltaCallToJump),
+            CodeLocationLabel(result.code()));
+    }
     
-    return RetryCacheLater;
+    return result.shouldGiveUpNow() ? GiveUpOnCache : RetryCacheLater;
 }
 
 void repatchPutByID(ExecState* exec, JSValue baseValue, Structure* structure, const Identifier& propertyName, const PutPropertySlot& slot, StructureStubInfo& stubInfo, PutKind putKind)
@@ -579,19 +573,17 @@ static InlineCacheAction tryRepatchIn(
         vm, codeBlock, wasFound ? AccessCase::InHit : AccessCase::InMiss, structure, conditionSet);
 
     AccessGenerationResult result = stubInfo.addAccessCase(codeBlock, ident, WTFMove(newCase));
-    if (result.gaveUp())
-        return GiveUpOnCache;
-    if (result.madeNoChanges())
-        return RetryCacheLater;
-
-    LOG_IC((ICEvent::InReplaceWithJump, structure->classInfo(), ident));
-
-    RELEASE_ASSERT(result.code());
-    MacroAssembler::repatchJump(
-        stubInfo.callReturnLocation.jumpAtOffset(stubInfo.patch.deltaCallToJump),
-        CodeLocationLabel(result.code()));
     
-    return RetryCacheLater;
+    if (result.generatedSomeCode()) {
+        LOG_IC((ICEvent::InReplaceWithJump, structure->classInfo(), ident));
+        
+        RELEASE_ASSERT(result.code());
+        MacroAssembler::repatchJump(
+            stubInfo.callReturnLocation.jumpAtOffset(stubInfo.patch.deltaCallToJump),
+            CodeLocationLabel(result.code()));
+    }
+    
+    return result.shouldGiveUpNow() ? GiveUpOnCache : RetryCacheLater;
 }
 
 void repatchIn(
index 35cc039..0ab3084 100644 (file)
@@ -308,6 +308,7 @@ public:
     JSCell* asCell() const;
     JS_EXPORT_PRIVATE bool isValidCallee();
 
+    Structure* structureOrNull() const;
     JSValue structureOrUndefined() const;
 
     JS_EXPORT_PRIVATE void dump(PrintStream&) const;
index 8886642..9905089 100644 (file)
@@ -849,6 +849,13 @@ inline bool JSValue::putByIndex(ExecState* exec, unsigned propertyName, JSValue
     return asCell()->methodTable(exec->vm())->putByIndex(asCell(), exec, propertyName, value, shouldThrow);
 }
 
+inline Structure* JSValue::structureOrNull() const
+{
+    if (isCell())
+        return asCell()->structure();
+    return nullptr;
+}
+
 inline JSValue JSValue::structureOrUndefined() const
 {
     if (isCell())
index 6a19083..36f4e75 100644 (file)
@@ -125,6 +125,7 @@ typedef const char* optionString;
     \
     v(unsigned, repatchCountForCoolDown, 10, nullptr) \
     v(unsigned, initialCoolDownCount, 20, nullptr) \
+    v(unsigned, repatchBufferingCountdown, 7, nullptr) \
     \
     v(bool, dumpGeneratedBytecodes, false, nullptr) \
     v(bool, dumpBytecodeLivenessResults, false, nullptr) \
index 233149b..9e6c835 100644 (file)
@@ -1,3 +1,13 @@
+2016-04-12  Filip Pizlo  <fpizlo@apple.com>
+
+        PolymorphicAccess should buffer AccessCases before regenerating
+        https://bugs.webkit.org/show_bug.cgi?id=156457
+
+        Reviewed by Benjamin Poulain.
+
+        * wtf/TinyPtrSet.h:
+        (WTF::TinyPtrSet::add): Add a helpful comment because I had forgotten what the bool return meant.
+
 2016-04-12  Tomas Popela  <tpopela@redhat.com>
 
         S390X and PPC64 architectures detection is wrong
index 93b198c..34c2c95 100644 (file)
@@ -101,6 +101,7 @@ public:
         return result;
     }
     
+    // Returns true if the value was added, or false if the value was already there.
     bool add(T value)
     {
         ASSERT(value);