DFG::forAllKilledOperands() could use a faster bitvector scan in the same-inline...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 12 Sep 2016 16:08:52 +0000 (16:08 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 12 Sep 2016 16:08:52 +0000 (16:08 +0000)
https://bugs.webkit.org/show_bug.cgi?id=161849

Reviewed by Saam Barati.

Source/JavaScriptCore:

This is a fairly obvious change. This turns a loop that would query each bit individually
into a loop that will process a word at a time. I would expect a very tiny progression in
DFG compile times.

This also gave me an opportunity to test and fix the new FastBitVector functionality.

* dfg/DFGForAllKills.h:
(JSC::DFG::forAllKilledOperands):

Source/WTF:

It turns out that templates make private fields weird. FastBitVectorImpl can't necessarily
touch privates in instances of different template specializations of itself. So, I added a
public method called wordView() that exposes the necessary private field.

* wtf/FastBitVector.h:
(WTF::FastBitVectorImpl::operator&):
(WTF::FastBitVectorImpl::operator|):
(WTF::FastBitVectorImpl::operator~):
(WTF::FastBitVectorImpl::forEachSetBit):
(WTF::FastBitVectorImpl::wordView):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGForAllKills.h
Source/WTF/ChangeLog
Source/WTF/wtf/FastBitVector.h

index a3d5680..06e068d 100644 (file)
@@ -1,5 +1,21 @@
 2016-09-11  Filip Pizlo  <fpizlo@apple.com>
 
+        DFG::forAllKilledOperands() could use a faster bitvector scan in the same-inline-stack fast path
+        https://bugs.webkit.org/show_bug.cgi?id=161849
+
+        Reviewed by Saam Barati.
+        
+        This is a fairly obvious change. This turns a loop that would query each bit individually
+        into a loop that will process a word at a time. I would expect a very tiny progression in
+        DFG compile times.
+        
+        This also gave me an opportunity to test and fix the new FastBitVector functionality.
+
+        * dfg/DFGForAllKills.h:
+        (JSC::DFG::forAllKilledOperands):
+
+2016-09-11  Filip Pizlo  <fpizlo@apple.com>
+
         FastBitVector should have efficient and easy-to-use vector-vector operations
         https://bugs.webkit.org/show_bug.cgi?id=161847
 
index 481b8ac..0d67678 100644 (file)
@@ -76,14 +76,10 @@ void forAllKilledOperands(Graph& graph, Node* nodeBefore, Node* nodeAfter, const
         const FastBitVector& liveBefore = fullLiveness.getLiveness(before.bytecodeIndex);
         const FastBitVector& liveAfter = fullLiveness.getLiveness(after.bytecodeIndex);
         
-        // FIXME: Consider doing this instead:
-        // (liveBefore & ~liveAfter).forEachSetBit(...)
-        // https://bugs.webkit.org/show_bug.cgi?id=161849
-        for (unsigned relativeLocal = codeBlock->m_numCalleeLocals; relativeLocal--;) {
-            if (liveBefore[relativeLocal] && !liveAfter[relativeLocal])
+        (liveBefore & ~liveAfter).forEachSetBit(
+            [&] (size_t relativeLocal) {
                 functor(virtualRegisterForLocal(relativeLocal) + stackOffset);
-        }
-        
+            });
         return;
     }
     
index fa67c35..8ff5d78 100644 (file)
@@ -1,5 +1,23 @@
 2016-09-11  Filip Pizlo  <fpizlo@apple.com>
 
+        DFG::forAllKilledOperands() could use a faster bitvector scan in the same-inline-stack fast path
+        https://bugs.webkit.org/show_bug.cgi?id=161849
+
+        Reviewed by Saam Barati.
+        
+        It turns out that templates make private fields weird. FastBitVectorImpl can't necessarily
+        touch privates in instances of different template specializations of itself. So, I added a
+        public method called wordView() that exposes the necessary private field.
+
+        * wtf/FastBitVector.h:
+        (WTF::FastBitVectorImpl::operator&):
+        (WTF::FastBitVectorImpl::operator|):
+        (WTF::FastBitVectorImpl::operator~):
+        (WTF::FastBitVectorImpl::forEachSetBit):
+        (WTF::FastBitVectorImpl::wordView):
+
+2016-09-11  Filip Pizlo  <fpizlo@apple.com>
+
         FastBitVector should have efficient and easy-to-use vector-vector operations
         https://bugs.webkit.org/show_bug.cgi?id=161847
 
index 6c222d7..bb2f252 100644 (file)
@@ -258,7 +258,7 @@ public:
 private:
     View m_view;
 };
-    
+
 class FastBitVector;
 
 template<typename Words>
@@ -323,24 +323,24 @@ public:
     template<typename OtherWords>
     FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>> operator&(const FastBitVectorImpl<OtherWords>& other) const
     {
-        return FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>(m_words.view(), other.m_words.view()));
+        return FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>(wordView(), other.wordView()));
     }
     
     template<typename OtherWords>
     FastBitVectorImpl<FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>> operator|(const FastBitVectorImpl<OtherWords>& other) const
     {
-        return FastBitVectorImpl<FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>(m_words.view(), other.m_words.view()));
+        return FastBitVectorImpl<FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>(wordView(), other.wordView()));
     }
     
     FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>> operator~() const
     {
-        return FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>>(FastBitVectorNotWords<typename Words::ViewType>(m_words.view()));
+        return FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>>(FastBitVectorNotWords<typename Words::ViewType>(wordView()));
     }
     
     template<typename Func>
     ALWAYS_INLINE void forEachSetBit(const Func& func) const
     {
-        size_t n = m_words.arrayLength();
+        size_t n = arrayLength();
         for (size_t i = 0; i < n; ++i) {
             uint32_t word = m_words.word(i);
             size_t j = i * 32;
@@ -416,6 +416,8 @@ public:
             out.print((*this)[i] ? "1" : "-");
     }
     
+    typename Words::ViewType wordView() const { return m_words.view(); }
+    
 private:
     // You'd think that we could remove this friend if we used protected, but you'd be wrong,
     // because templates.