RegisterSet should use a Bitmap instead of a BitVector so that it never allocates...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 18 Jul 2016 19:51:45 +0000 (19:51 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 18 Jul 2016 19:51:45 +0000 (19:51 +0000)
https://bugs.webkit.org/show_bug.cgi?id=159863

Reviewed by Saam Barati.

Source/JavaScriptCore:

Switch RegisterSet set to Bitmap because Bitmap doesn't ever allocate memory and can be
assigned by memcpy. This should be a performance improvement for compiler code that does a
lot of things with RegisterSet. For example, it's one of the fundamental data structures in
Air. The previous use of BitVector meant that almost every operation on RegisterSet would
have a slow path call. On ARM64, it would mean memory allocation for any RegisterSet that
used all available registers.

This meant adding even more GPR/FPR reflection to the MacroAssembler API: we now have consts
called numGPRs and numFPRs. This is necessary to statically size the Bitmap in RegisterSet.

Here's the breakdown of sizes of RegisterSet on different CPUs:

x86-32: 8 bits (GPRs) + 8 bits (FPRs) + 1 bit (is deleted) = 1x uint32_t.
x86-64: 16 bits + 16 bits + 1 bit = 2x uint32_t.
ARMv7: 16 bits + 16 bits + 1 bit = 2x uint32_t.
ARM64: 32 bits + 32 bits + 1 bit = 3x uint32_t.

* assembler/MacroAssemblerARM.h:
* assembler/MacroAssemblerARM64.h:
* assembler/MacroAssemblerARMv7.h:
* assembler/MacroAssemblerX86.h:
* assembler/MacroAssemblerX86Common.h:
(JSC::MacroAssemblerX86Common::scratchRegister):
* assembler/MacroAssemblerX86_64.h:
* jit/RegisterSet.h:
(JSC::RegisterSet::set):
(JSC::RegisterSet::get):
(JSC::RegisterSet::setAll):
(JSC::RegisterSet::merge):
(JSC::RegisterSet::filter):
(JSC::RegisterSet::exclude):
(JSC::RegisterSet::numberOfSetRegisters):
(JSC::RegisterSet::RegisterSet):
(JSC::RegisterSet::isEmptyValue):
(JSC::RegisterSet::isDeletedValue):
(JSC::RegisterSet::operator==):
(JSC::RegisterSet::operator!=):
(JSC::RegisterSet::hash):
(JSC::RegisterSet::forEach):
(JSC::RegisterSet::setMany):

Source/WTF:

Give Bitmap all of the power of BitVector (except for automatic resizing). This means a
variant of set() that takes a bool, and a bunch of helper methods (merge, filter, exclude,
forEachSetBit, ==, !=, and hash).

* wtf/Bitmap.h:
(WTF::WordType>::set):
(WTF::WordType>::testAndSet):
(WTF::WordType>::isFull):
(WTF::WordType>::merge):
(WTF::WordType>::filter):
(WTF::WordType>::exclude):
(WTF::WordType>::forEachSetBit):
(WTF::=):
(WTF::WordType>::hash):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/assembler/MacroAssemblerARM.h
Source/JavaScriptCore/assembler/MacroAssemblerARM64.h
Source/JavaScriptCore/assembler/MacroAssemblerARMv7.h
Source/JavaScriptCore/assembler/MacroAssemblerX86.h
Source/JavaScriptCore/assembler/MacroAssemblerX86Common.h
Source/JavaScriptCore/assembler/MacroAssemblerX86_64.h
Source/JavaScriptCore/jit/RegisterSet.h
Source/WTF/ChangeLog
Source/WTF/wtf/Bitmap.h

index 63c754d..6d70276 100644 (file)
@@ -1,3 +1,51 @@
+2016-07-17  Filip Pizlo  <fpizlo@apple.com>
+
+        RegisterSet should use a Bitmap instead of a BitVector so that it never allocates memory and is trivial to copy
+        https://bugs.webkit.org/show_bug.cgi?id=159863
+
+        Reviewed by Saam Barati.
+        
+        Switch RegisterSet set to Bitmap because Bitmap doesn't ever allocate memory and can be
+        assigned by memcpy. This should be a performance improvement for compiler code that does a
+        lot of things with RegisterSet. For example, it's one of the fundamental data structures in
+        Air. The previous use of BitVector meant that almost every operation on RegisterSet would
+        have a slow path call. On ARM64, it would mean memory allocation for any RegisterSet that
+        used all available registers.
+        
+        This meant adding even more GPR/FPR reflection to the MacroAssembler API: we now have consts
+        called numGPRs and numFPRs. This is necessary to statically size the Bitmap in RegisterSet.
+        
+        Here's the breakdown of sizes of RegisterSet on different CPUs:
+        
+        x86-32: 8 bits (GPRs) + 8 bits (FPRs) + 1 bit (is deleted) = 1x uint32_t.
+        x86-64: 16 bits + 16 bits + 1 bit = 2x uint32_t.
+        ARMv7: 16 bits + 16 bits + 1 bit = 2x uint32_t.
+        ARM64: 32 bits + 32 bits + 1 bit = 3x uint32_t.
+
+        * assembler/MacroAssemblerARM.h:
+        * assembler/MacroAssemblerARM64.h:
+        * assembler/MacroAssemblerARMv7.h:
+        * assembler/MacroAssemblerX86.h:
+        * assembler/MacroAssemblerX86Common.h:
+        (JSC::MacroAssemblerX86Common::scratchRegister):
+        * assembler/MacroAssemblerX86_64.h:
+        * jit/RegisterSet.h:
+        (JSC::RegisterSet::set):
+        (JSC::RegisterSet::get):
+        (JSC::RegisterSet::setAll):
+        (JSC::RegisterSet::merge):
+        (JSC::RegisterSet::filter):
+        (JSC::RegisterSet::exclude):
+        (JSC::RegisterSet::numberOfSetRegisters):
+        (JSC::RegisterSet::RegisterSet):
+        (JSC::RegisterSet::isEmptyValue):
+        (JSC::RegisterSet::isDeletedValue):
+        (JSC::RegisterSet::operator==):
+        (JSC::RegisterSet::operator!=):
+        (JSC::RegisterSet::hash):
+        (JSC::RegisterSet::forEach):
+        (JSC::RegisterSet::setMany):
+
 2016-07-15  Filip Pizlo  <fpizlo@apple.com>
 
         DFG and FTL should support op_call_eval
index 3e1062c..8e7bd05 100644 (file)
@@ -40,6 +40,9 @@ class MacroAssemblerARM : public AbstractMacroAssembler<ARMAssembler, MacroAssem
     static const int DoubleConditionBitSpecial = 0x10;
     COMPILE_ASSERT(!(DoubleConditionBitSpecial & DoubleConditionMask), DoubleConditionBitSpecial_should_not_interfere_with_ARMAssembler_Condition_codes);
 public:
+    static const unsigned numGPRs = 16;
+    static const unsigned numFPRs = 16;
+    
     typedef ARMRegisters::FPRegisterID FPRegisterID;
 
     enum RelationalCondition {
index 6e78c7c..f23dff6 100644 (file)
@@ -37,6 +37,9 @@ namespace JSC {
 
 class MacroAssemblerARM64 : public AbstractMacroAssembler<ARM64Assembler, MacroAssemblerARM64> {
 public:
+    static const unsigned numGPRs = 32;
+    static const unsigned numFPRs = 32;
+    
     static const RegisterID dataTempRegister = ARM64Registers::ip0;
     static const RegisterID memoryTempRegister = ARM64Registers::ip1;
 
index 3c8c48d..4513ed2 100644 (file)
@@ -42,6 +42,9 @@ class MacroAssemblerARMv7 : public AbstractMacroAssembler<ARMv7Assembler, MacroA
     inline ARMRegisters::FPSingleRegisterID fpTempRegisterAsSingle() { return ARMRegisters::asSingle(fpTempRegister); }
 
 public:
+    static const unsigned numGPRs = 16;
+    static const unsigned numFPRs = 16;
+    
     MacroAssemblerARMv7()
         : m_makeJumpPatchable(false)
     {
index d9b236b..87c3a3a 100644 (file)
@@ -34,6 +34,9 @@ namespace JSC {
 
 class MacroAssemblerX86 : public MacroAssemblerX86Common {
 public:
+    static const unsigned numGPRs = 8;
+    static const unsigned numFPRs = 8;
+    
     static const Scale ScalePtr = TimesFour;
 
     using MacroAssemblerX86Common::add32;
index be2efd7..2052ae0 100644 (file)
@@ -48,7 +48,7 @@ public:
         return s_scratchRegister;
     }
 #endif
-
+    
 protected:
     static const int DoubleConditionBitInvert = 0x10;
     static const int DoubleConditionBitSpecial = 0x20;
index d9858f3..ff3b9dd 100644 (file)
@@ -38,6 +38,9 @@ namespace JSC {
 
 class MacroAssemblerX86_64 : public MacroAssemblerX86Common {
 public:
+    static const unsigned numGPRs = 16;
+    static const unsigned numFPRs = 16;
+    
     static const Scale ScalePtr = TimesEight;
 
     using MacroAssemblerX86Common::add32;
index 7d96fbf..370d6d0 100644 (file)
@@ -33,7 +33,7 @@
 #include "MacroAssembler.h"
 #include "Reg.h"
 #include "TempRegisterSet.h"
-#include <wtf/BitVector.h>
+#include <wtf/Bitmap.h>
 
 namespace JSC {
 
@@ -71,7 +71,7 @@ public:
     void set(Reg reg, bool value = true)
     {
         ASSERT(!!reg);
-        m_vector.set(reg.index(), value);
+        m_bits.set(reg.index(), value);
     }
     
     void set(JSValueRegs regs, bool value = true)
@@ -90,9 +90,9 @@ public:
     bool get(Reg reg) const
     {
         ASSERT(!!reg);
-        return m_vector.get(reg.index());
+        return m_bits.get(reg.index());
     }
-
+    
     template<typename Iterable>
     void setAll(const Iterable& iterable)
     {
@@ -100,13 +100,13 @@ public:
             set(reg);
     }
     
-    void merge(const RegisterSet& other) { m_vector.merge(other.m_vector); }
-    void filter(const RegisterSet& other) { m_vector.filter(other.m_vector); }
-    void exclude(const RegisterSet& other) { m_vector.exclude(other.m_vector); }
+    void merge(const RegisterSet& other) { m_bits.merge(other.m_bits); }
+    void filter(const RegisterSet& other) { m_bits.filter(other.m_bits); }
+    void exclude(const RegisterSet& other) { m_bits.exclude(other.m_bits); }
     
     size_t numberOfSetGPRs() const;
     size_t numberOfSetFPRs() const;
-    size_t numberOfSetRegisters() const { return m_vector.bitCount(); }
+    size_t numberOfSetRegisters() const { return m_bits.count(); }
     
     void dump(PrintStream&) const;
     
@@ -114,26 +114,38 @@ public:
     enum DeletedValueTag { DeletedValue };
     
     RegisterSet(EmptyValueTag)
-        : m_vector(BitVector::EmptyValue)
     {
+        m_bits.set(hashSpecialBitIndex);
     }
     
     RegisterSet(DeletedValueTag)
-        : m_vector(BitVector::DeletedValue)
     {
+        m_bits.set(hashSpecialBitIndex);
+        m_bits.set(deletedBitIndex);
     }
     
-    bool isEmptyValue() const { return m_vector.isEmptyValue(); }
-    bool isDeletedValue() const { return m_vector.isDeletedValue(); }
+    bool isEmptyValue() const
+    {
+        return m_bits.get(hashSpecialBitIndex) && !m_bits.get(deletedBitIndex);
+    }
     
-    bool operator==(const RegisterSet& other) const { return m_vector == other.m_vector; }
-    unsigned hash() const { return m_vector.hash(); }
-
-    template<typename Functor>
-    void forEach(const Functor& functor) const
+    bool isDeletedValue() const
     {
-        for (size_t index : m_vector)
-            functor(Reg::fromIndex(index));
+        return m_bits.get(hashSpecialBitIndex) && m_bits.get(deletedBitIndex);
+    }
+    
+    bool operator==(const RegisterSet& other) const { return m_bits == other.m_bits; }
+    bool operator!=(const RegisterSet& other) const { return m_bits != other.m_bits; }
+    
+    unsigned hash() const { return m_bits.hash(); }
+    
+    template<typename Func>
+    void forEach(const Func& func) const
+    {
+        m_bits.forEachSetBit(
+            [&] (size_t index) {
+                func(Reg::fromIndex(index));
+            });
     }
     
 private:
@@ -147,7 +159,13 @@ private:
         setMany(regs...);
     }
 
-    BitVector m_vector;
+    // These offsets mirror the logic in Reg.h.
+    static const unsigned gprOffset = 0;
+    static const unsigned fprOffset = gprOffset + MacroAssembler::numGPRs;
+    static const unsigned hashSpecialBitIndex = fprOffset + MacroAssembler::numFPRs;
+    static const unsigned deletedBitIndex = 0;
+    
+    Bitmap<MacroAssembler::numGPRs + MacroAssembler::numFPRs + 1> m_bits;
 };
 
 struct RegisterSetHash {
index 632e777..c584178 100644 (file)
@@ -1,3 +1,25 @@
+2016-07-17  Filip Pizlo  <fpizlo@apple.com>
+
+        RegisterSet should use a Bitmap instead of a BitVector so that it never allocates memory and is trivial to copy
+        https://bugs.webkit.org/show_bug.cgi?id=159863
+
+        Reviewed by Saam Barati.
+        
+        Give Bitmap all of the power of BitVector (except for automatic resizing). This means a
+        variant of set() that takes a bool, and a bunch of helper methods (merge, filter, exclude,
+        forEachSetBit, ==, !=, and hash).
+
+        * wtf/Bitmap.h:
+        (WTF::WordType>::set):
+        (WTF::WordType>::testAndSet):
+        (WTF::WordType>::isFull):
+        (WTF::WordType>::merge):
+        (WTF::WordType>::filter):
+        (WTF::WordType>::exclude):
+        (WTF::WordType>::forEachSetBit):
+        (WTF::=):
+        (WTF::WordType>::hash):
+
 2016-07-02  Filip Pizlo  <fpizlo@apple.com>
 
         WTF::Lock should be fair eventually
index 07e962e..9bd3d84 100644 (file)
@@ -1,5 +1,5 @@
 /*
- *  Copyright (C) 2010 Apple Inc. All rights reserved.
+ *  Copyright (C) 2010, 2016 Apple Inc. All rights reserved.
  *
  *  This library is free software; you can redistribute it and/or
  *  modify it under the terms of the GNU Lesser General Public
@@ -39,6 +39,8 @@ enum BitmapAtomicMode {
 template<size_t bitmapSize, BitmapAtomicMode atomicMode = BitmapNotAtomic, typename WordType = uint32_t>
 class Bitmap {
     WTF_MAKE_FAST_ALLOCATED;
+    
+    static_assert(sizeof(WordType) <= sizeof(unsigned), "WordType must not be bigger than unsigned");
 public:
     Bitmap();
 
@@ -49,6 +51,7 @@ public:
 
     bool get(size_t) const;
     void set(size_t);
+    void set(size_t, bool);
     bool testAndSet(size_t);
     bool testAndClear(size_t);
     bool concurrentTestAndSet(size_t);
@@ -60,6 +63,18 @@ public:
     size_t count(size_t = 0) const;
     size_t isEmpty() const;
     size_t isFull() const;
+    
+    void merge(const Bitmap&);
+    void filter(const Bitmap&);
+    void exclude(const Bitmap&);
+    
+    template<typename Func>
+    void forEachSetBit(const Func&) const;
+    
+    bool operator==(const Bitmap&) const;
+    bool operator!=(const Bitmap&) const;
+    
+    unsigned hash() const;
 
 private:
     static const unsigned wordSize = sizeof(WordType) * 8;
@@ -94,6 +109,15 @@ inline void Bitmap<bitmapSize, atomicMode, WordType>::set(size_t n)
 }
 
 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
+inline void Bitmap<bitmapSize, atomicMode, WordType>::set(size_t n, bool value)
+{
+    if (value)
+        set(n);
+    else
+        clear(n);
+}
+
+template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
 inline bool Bitmap<bitmapSize, atomicMode, WordType>::testAndSet(size_t n)
 {
     WordType mask = one << (n % wordSize);
@@ -224,5 +248,71 @@ inline size_t Bitmap<bitmapSize, atomicMode, WordType>::isFull() const
     return true;
 }
 
+template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
+inline void Bitmap<bitmapSize, atomicMode, WordType>::merge(const Bitmap& other)
+{
+    for (size_t i = 0; i < words; ++i)
+        bits[i] |= other.bits[i];
+}
+
+template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
+inline void Bitmap<bitmapSize, atomicMode, WordType>::filter(const Bitmap& other)
+{
+    for (size_t i = 0; i < words; ++i)
+        bits[i] &= other.bits[i];
+}
+
+template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
+inline void Bitmap<bitmapSize, atomicMode, WordType>::exclude(const Bitmap& other)
+{
+    for (size_t i = 0; i < words; ++i)
+        bits[i] &= ~other.bits[i];
+}
+
+template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
+template<typename Func>
+inline void Bitmap<bitmapSize, atomicMode, WordType>::forEachSetBit(const Func& func) const
+{
+    for (size_t i = 0; i < words; ++i) {
+        WordType word = bits[i];
+        if (!word)
+            continue;
+        size_t base = i * wordSize;
+        for (size_t j = 0; j < wordSize; ++j) {
+            if (word & 1)
+                func(base + j);
+            word >>= 1;
+        }
+    }
+}
+
+template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
+inline bool Bitmap<bitmapSize, atomicMode, WordType>::operator==(const Bitmap& other) const
+{
+    for (size_t i = 0; i < words; ++i) {
+        if (bits[i] != other.bits[i])
+            return false;
+    }
+    return true;
+}
+
+template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
+inline bool Bitmap<bitmapSize, atomicMode, WordType>::operator!=(const Bitmap& other) const
+{
+    return !(*this == other);
+}
+
+template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
+inline unsigned Bitmap<bitmapSize, atomicMode, WordType>::hash() const
+{
+    unsigned result = 0;
+    for (size_t i = 0; i < words; ++i)
+        result ^= IntHash<WordType>::hash(bits[i]);
+    return result;
 }
+
+} // namespace WTF
+
+using WTF::Bitmap;
+
 #endif