FastBitVector should have efficient and easy-to-use vector-vector operations
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 12 Sep 2016 04:03:36 +0000 (04:03 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 12 Sep 2016 04:03:36 +0000 (04:03 +0000)
https://bugs.webkit.org/show_bug.cgi?id=161847

Reviewed by Saam Barati.

Source/JavaScriptCore:

Adapt existing users of FastBitVector to the new API.

* bytecode/BytecodeLivenessAnalysis.cpp:
(JSC::BytecodeLivenessAnalysis::computeKills):
(JSC::BytecodeLivenessAnalysis::dumpResults):
* bytecode/BytecodeLivenessAnalysisInlines.h:
(JSC::operandThatIsNotAlwaysLiveIsLive):
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::stepOverInstruction):
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::runLivenessFixpoint):
* bytecode/CodeBlock.cpp:
(JSC::CodeBlock::validate):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::flushForTerminal):
* dfg/DFGForAllKills.h:
(JSC::DFG::forAllKilledOperands):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::forAllLocalsLiveInBytecode):
* dfg/DFGLiveCatchVariablePreservationPhase.cpp:
(JSC::DFG::LiveCatchVariablePreservationPhase::willCatchException):
(JSC::DFG::LiveCatchVariablePreservationPhase::handleBlock):
* dfg/DFGNaturalLoops.cpp:
(JSC::DFG::NaturalLoops::NaturalLoops):
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::cleanMustHandleValuesIfNecessary):

Source/WTF:

FastBitVector is a bitvector representation that supports manual dynamic resizing and is
optimized for speed, not space. (BitVector supports automatic dynamic resizing and is
optimized for space, while Bitmap is sized statically and is optimized for both speed and
space.) This change greatly increases the power of FastBitVector. We will use these new
powers for changing the JSC GC to use FastBitVectors to track sets of MarkedBlocks (bug
161581) instead of using a combination of Vectors and doubly-linked lists.

This change splits FastBitVector into two parts:

- A thing that manages the storage of a bitvector: a uint32_t array and a size_t numBits.
  We call this the word view.
- A thing that takes some kind of abstract array of uint32_t's and does bitvector
  operations to it. We call this the FastBitVectorImpl.

FastBitVectorImpl and word views are immutable. The FastBitVector class is a subclass of
FastBitVectorImpl specialized on a word view that owns its words and has additional
support for mutable operations.

Doing this allows us to efficiently support things like this without any unnecessary
memory allocation or copying:

FastBitVector a, b, c; // Assume that there is code to initialize these.
a &= b | ~c;

Previously, this kind of operation would not be efficient, because "~c" would have to
create a whole new FastBitVector. But now, it just returns a FastBitVectorImpl whose
underlying word view bitnots (~) its words on the fly. Using template magic, this can get
pretty complex. For example "b | ~c" returns a FastBitVectorImpl that wraps a word view
whose implementation of WordView::word(size_t index) is something like:

uint32_t word(size_t index) { return b.m_words.word(index) | ~c.m_words.word(index); }

FastBitVectorImpl supports all of the fast bulk bitvector operations, like
forEachSetBit(), bitCount(), etc. So, when you say "a &= b | ~c", the actual
implementation is going to run these bit operations on word granularity directly over the
storage inside a, b, c.

The use of operator overloading is worth explaining a bit. Previously, FastBitVector
avoided operator overloading. For example, the &= operation was called filter(). I think
that this was a pretty good approach at the time. I tried using non-operator methods in
this FastBitVector rewrite, but I found it very odd to say things like:

a.filter(b.bitOr(c.bitNot()));

I think that it's harder to see what is going on here, then using operators, because infix
notation is always better.

* WTF.xcodeproj/project.pbxproj:
* wtf/BitVector.h:
(WTF::BitVector::findBitInWord): Deleted.
* wtf/CMakeLists.txt:
* wtf/Dominators.h:
(WTF::Dominators::NaiveDominators::NaiveDominators):
(WTF::Dominators::NaiveDominators::dominates):
(WTF::Dominators::NaiveDominators::pruneDominators):
* wtf/FastBitVector.cpp: Removed.
* wtf/FastBitVector.h:
(WTF::fastBitVectorArrayLength):
(WTF::FastBitVectorWordView::FastBitVectorWordView):
(WTF::FastBitVectorWordView::numBits):
(WTF::FastBitVectorWordView::word):
(WTF::FastBitVectorWordOwner::FastBitVectorWordOwner):
(WTF::FastBitVectorWordOwner::~FastBitVectorWordOwner):
(WTF::FastBitVectorWordOwner::view):
(WTF::FastBitVectorWordOwner::operator=):
(WTF::FastBitVectorWordOwner::setAll):
(WTF::FastBitVectorWordOwner::clearAll):
(WTF::FastBitVectorWordOwner::set):
(WTF::FastBitVectorWordOwner::numBits):
(WTF::FastBitVectorWordOwner::arrayLength):
(WTF::FastBitVectorWordOwner::resize):
(WTF::FastBitVectorWordOwner::word):
(WTF::FastBitVectorWordOwner::words):
(WTF::FastBitVectorAndWords::FastBitVectorAndWords):
(WTF::FastBitVectorAndWords::view):
(WTF::FastBitVectorAndWords::numBits):
(WTF::FastBitVectorAndWords::word):
(WTF::FastBitVectorOrWords::FastBitVectorOrWords):
(WTF::FastBitVectorOrWords::view):
(WTF::FastBitVectorOrWords::numBits):
(WTF::FastBitVectorOrWords::word):
(WTF::FastBitVectorNotWords::FastBitVectorNotWords):
(WTF::FastBitVectorNotWords::view):
(WTF::FastBitVectorNotWords::numBits):
(WTF::FastBitVectorNotWords::word):
(WTF::FastBitVectorImpl::FastBitVectorImpl):
(WTF::FastBitVectorImpl::numBits):
(WTF::FastBitVectorImpl::size):
(WTF::FastBitVectorImpl::arrayLength):
(WTF::FastBitVectorImpl::operator==):
(WTF::FastBitVectorImpl::operator!=):
(WTF::FastBitVectorImpl::at):
(WTF::FastBitVectorImpl::operator[]):
(WTF::FastBitVectorImpl::bitCount):
(WTF::FastBitVectorImpl::operator&):
(WTF::FastBitVectorImpl::operator|):
(WTF::FastBitVectorImpl::operator~):
(WTF::FastBitVectorImpl::forEachSetBit):
(WTF::FastBitVectorImpl::forEachClearBit):
(WTF::FastBitVectorImpl::forEachBit):
(WTF::FastBitVectorImpl::findBit):
(WTF::FastBitVectorImpl::findSetBit):
(WTF::FastBitVectorImpl::findClearBit):
(WTF::FastBitVectorImpl::dump):
(WTF::FastBitVectorImpl::atImpl):
(WTF::FastBitVector::FastBitVector):
(WTF::FastBitVector::operator=):
(WTF::FastBitVector::resize):
(WTF::FastBitVector::setAll):
(WTF::FastBitVector::clearAll):
(WTF::FastBitVector::setAndCheck):
(WTF::FastBitVector::operator|=):
(WTF::FastBitVector::operator&=):
(WTF::FastBitVector::at):
(WTF::FastBitVector::operator[]):
(WTF::FastBitVector::BitReference::BitReference):
(WTF::FastBitVector::BitReference::operator bool):
(WTF::FastBitVector::BitReference::operator=):
(WTF::FastBitVector::~FastBitVector): Deleted.
(WTF::FastBitVector::numBits): Deleted.
(WTF::FastBitVector::set): Deleted.
(WTF::FastBitVector::equals): Deleted.
(WTF::FastBitVector::merge): Deleted.
(WTF::FastBitVector::filter): Deleted.
(WTF::FastBitVector::exclude): Deleted.
(WTF::FastBitVector::clear): Deleted.
(WTF::FastBitVector::get): Deleted.
(WTF::FastBitVector::bitCount): Deleted.
(WTF::FastBitVector::forEachSetBit): Deleted.
(WTF::FastBitVector::arrayLength): Deleted.
* wtf/StdLibExtras.h:
(WTF::findBitInWord):

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

18 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp
Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysisInlines.h
Source/JavaScriptCore/bytecode/CodeBlock.cpp
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGForAllKills.h
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGLiveCatchVariablePreservationPhase.cpp
Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp
Source/JavaScriptCore/dfg/DFGPlan.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/BitVector.h
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Dominators.h
Source/WTF/wtf/FastBitVector.cpp [deleted file]
Source/WTF/wtf/FastBitVector.h
Source/WTF/wtf/StdLibExtras.h

index 1c47403..a3d5680 100644 (file)
@@ -1,3 +1,35 @@
+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
+
+        Reviewed by Saam Barati.
+        
+        Adapt existing users of FastBitVector to the new API.
+
+        * bytecode/BytecodeLivenessAnalysis.cpp:
+        (JSC::BytecodeLivenessAnalysis::computeKills):
+        (JSC::BytecodeLivenessAnalysis::dumpResults):
+        * bytecode/BytecodeLivenessAnalysisInlines.h:
+        (JSC::operandThatIsNotAlwaysLiveIsLive):
+        (JSC::BytecodeLivenessPropagation<DerivedAnalysis>::stepOverInstruction):
+        (JSC::BytecodeLivenessPropagation<DerivedAnalysis>::runLivenessFixpoint):
+        * bytecode/CodeBlock.cpp:
+        (JSC::CodeBlock::validate):
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::flushForTerminal):
+        * dfg/DFGForAllKills.h:
+        (JSC::DFG::forAllKilledOperands):
+        * dfg/DFGGraph.h:
+        (JSC::DFG::Graph::forAllLocalsLiveInBytecode):
+        * dfg/DFGLiveCatchVariablePreservationPhase.cpp:
+        (JSC::DFG::LiveCatchVariablePreservationPhase::willCatchException):
+        (JSC::DFG::LiveCatchVariablePreservationPhase::handleBlock):
+        * dfg/DFGNaturalLoops.cpp:
+        (JSC::DFG::NaturalLoops::NaturalLoops):
+        * dfg/DFGPlan.cpp:
+        (JSC::DFG::Plan::cleanMustHandleValuesIfNecessary):
+
 2016-09-10  Chris Dumez  <cdumez@apple.com>
 
         parseHTMLInteger() should take a StringView in parameter
index d7868a8..b215ce3 100644 (file)
@@ -121,14 +121,14 @@ void BytecodeLivenessAnalysis::computeKills(BytecodeKills& result)
                 m_graph, bytecodeOffset, out,
                 [&] (unsigned index) {
                     // This is for uses.
-                    if (out.get(index))
+                    if (out[index])
                         return;
                     result.m_killSets[bytecodeOffset].add(index);
-                    out.set(index);
+                    out[index] = true;
                 },
                 [&] (unsigned index) {
                     // This is for defs.
-                    out.clear(index);
+                    out[index] = false;
                 });
         }
     }
@@ -163,7 +163,7 @@ void BytecodeLivenessAnalysis::dumpResults()
             dataLogF("Live variables: ");
             FastBitVector liveBefore = getLivenessInfoAtBytecodeOffset(bytecodeOffset);
             for (unsigned j = 0; j < liveBefore.numBits(); j++) {
-                if (liveBefore.get(j))
+                if (liveBefore[j])
                     dataLogF("%u ", j);
             }
             dataLogF("\n");
@@ -177,7 +177,7 @@ void BytecodeLivenessAnalysis::dumpResults()
         dataLogF("Live variables: ");
         FastBitVector liveAfter = block->out();
         for (unsigned j = 0; j < liveAfter.numBits(); j++) {
-            if (liveAfter.get(j))
+            if (liveAfter[j])
                 dataLogF("%u ", j);
         }
         dataLogF("\n");
index 178d02f..3371237 100644 (file)
@@ -43,7 +43,7 @@ inline bool operandThatIsNotAlwaysLiveIsLive(const FastBitVector& out, int opera
     unsigned local = VirtualRegister(operand).toLocal();
     if (local >= out.numBits())
         return false;
-    return out.get(local);
+    return out[local];
 }
 
 inline bool operandIsLive(const FastBitVector& out, int operand)
@@ -117,11 +117,11 @@ inline void BytecodeLivenessPropagation<DerivedAnalysis>::stepOverInstruction(Gr
         graph, bytecodeOffset, out,
         [&] (unsigned bitIndex) {
             // This is the use functor, so we set the bit.
-            out.set(bitIndex);
+            out[bitIndex] = true;
         },
         [&] (unsigned bitIndex) {
             // This is the def functor, so we clear the bit.
-            out.clear(bitIndex);
+            out[bitIndex] = false;
         });
 }
 
@@ -191,8 +191,8 @@ inline void BytecodeLivenessPropagation<DerivedAnalysis>::runLivenessFixpoint(Gr
         for (std::unique_ptr<BytecodeBasicBlock>& block : graph.basicBlocksInReverseOrder()) {
             newOut.clearAll();
             for (BytecodeBasicBlock* successor : block->successors())
-                newOut.merge(successor->in());
-            block->out().set(newOut);
+                newOut |= successor->in();
+            block->out() = newOut;
             changed |= computeLocalLivenessForBlock(graph, block.get());
         }
     } while (changed);
index 9a8dc0c..fa3f236 100644 (file)
@@ -4292,7 +4292,7 @@ void CodeBlock::validate()
     for (unsigned i = m_numCalleeLocals; i--;) {
         VirtualRegister reg = virtualRegisterForLocal(i);
         
-        if (liveAtHead.get(i)) {
+        if (liveAtHead[i]) {
             beginValidationDidFail();
             dataLog("    Variable ", reg, " is expected to be dead.\n");
             dataLog("    Result: ", liveAtHead, "\n");
index 4647046..6af9427 100644 (file)
@@ -638,7 +638,7 @@ private:
             const FastBitVector& livenessAtBytecode = fullLiveness.getLiveness(bytecodeIndex);
 
             for (unsigned local = codeBlock->m_numCalleeLocals; local--;) {
-                if (livenessAtBytecode.get(local)) {
+                if (livenessAtBytecode[local]) {
                     VirtualRegister reg = virtualRegisterForLocal(local);
                     if (inlineCallFrame)
                         reg = inlineStackEntry->remapOperand(reg);
index f5f4cb5..481b8ac 100644 (file)
@@ -76,8 +76,11 @@ 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.get(relativeLocal) && !liveAfter.get(relativeLocal))
+            if (liveBefore[relativeLocal] && !liveAfter[relativeLocal])
                 functor(virtualRegisterForLocal(relativeLocal) + stackOffset);
         }
         
index 6a8a38d..1c04bc1 100644 (file)
@@ -745,7 +745,7 @@ public:
                 if (reg >= exclusionStart && reg < exclusionEnd)
                     continue;
                 
-                if (liveness.get(relativeLocal))
+                if (liveness[relativeLocal])
                     functor(reg);
             }
             
index 8a71c7a..db36999 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -73,7 +73,7 @@ public:
             if (HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeIndexToCheck)) {
                 unsigned catchBytecodeIndex = handler->target;
                 m_graph.forAllLocalsLiveInBytecode(CodeOrigin(catchBytecodeIndex, inlineCallFrame), [&] (VirtualRegister operand) {
-                    m_currentBlockLiveness.set(operand.toLocal(), true); 
+                    m_currentBlockLiveness[operand.toLocal()] = true;
                 });
                 return true;
             }
@@ -110,7 +110,7 @@ public:
                     VirtualRegister operand = node->local();
 
                     int stackOffset = inlineCallFrame ? inlineCallFrame->stackOffset : 0;
-                    if ((operand.isLocal() && m_currentBlockLiveness.get(operand.toLocal()))
+                    if ((operand.isLocal() && m_currentBlockLiveness[operand.toLocal()])
                         || (operand.offset() == stackOffset + CallFrame::thisArgumentOffset())) {
 
                         VariableAccessData* variableAccessData = currentBlockAccessData.operand(operand);
@@ -131,7 +131,7 @@ public:
         {
             NodeOrigin origin = block->at(block->size() - 1)->origin;
             auto preserveLivenessAtEndOfBlock = [&] (VirtualRegister operand, bool alwaysInsert) {
-                if ((operand.isLocal() && m_currentBlockLiveness.get(operand.toLocal())
+                if ((operand.isLocal() && m_currentBlockLiveness[operand.toLocal()]
                     || operand.isArgument()
                     || alwaysInsert) {
                     VariableAccessData* accessData = currentBlockAccessData.operand(operand);
index 89ca68b..1b74724 100644 (file)
@@ -105,7 +105,7 @@ NaturalLoops::NaturalLoops(Graph& graph)
             dataLog("Dealing with loop ", loop, "\n");
         
         for (unsigned j = loop.size(); j--;) {
-            seenBlocks.set(loop[j]->index);
+            seenBlocks[loop[j]->index] = true;
             blockWorklist.append(loop[j]);
         }
         
@@ -120,12 +120,12 @@ NaturalLoops::NaturalLoops(Graph& graph)
             
             for (unsigned j = block->predecessors.size(); j--;) {
                 BasicBlock* predecessor = block->predecessors[j];
-                if (seenBlocks.get(predecessor->index))
+                if (seenBlocks[predecessor->index])
                     continue;
                 
                 loop.addBlock(predecessor);
                 blockWorklist.append(predecessor);
-                seenBlocks.set(predecessor->index);
+                seenBlocks[predecessor->index] = true;
             }
         }
     }
index 09db8e0..7416a67 100644 (file)
@@ -691,7 +691,7 @@ void Plan::cleanMustHandleValuesIfNecessary()
     FastBitVector liveness = codeBlock->alternative()->livenessAnalysis().getLivenessInfoAtBytecodeOffset(osrEntryBytecodeIndex);
     
     for (unsigned local = mustHandleValues.numberOfLocals(); local--;) {
-        if (!liveness.get(local))
+        if (!liveness[local])
             mustHandleValues.local(local) = jsUndefined();
     }
 }
index 410a4e8..fa67c35 100644 (file)
@@ -1,3 +1,143 @@
+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
+
+        Reviewed by Saam Barati.
+        
+        FastBitVector is a bitvector representation that supports manual dynamic resizing and is
+        optimized for speed, not space. (BitVector supports automatic dynamic resizing and is
+        optimized for space, while Bitmap is sized statically and is optimized for both speed and
+        space.) This change greatly increases the power of FastBitVector. We will use these new
+        powers for changing the JSC GC to use FastBitVectors to track sets of MarkedBlocks (bug
+        161581) instead of using a combination of Vectors and doubly-linked lists.
+        
+        This change splits FastBitVector into two parts:
+        
+        - A thing that manages the storage of a bitvector: a uint32_t array and a size_t numBits.
+          We call this the word view.
+        - A thing that takes some kind of abstract array of uint32_t's and does bitvector
+          operations to it. We call this the FastBitVectorImpl.
+        
+        FastBitVectorImpl and word views are immutable. The FastBitVector class is a subclass of
+        FastBitVectorImpl specialized on a word view that owns its words and has additional
+        support for mutable operations.
+        
+        Doing this allows us to efficiently support things like this without any unnecessary
+        memory allocation or copying:
+        
+        FastBitVector a, b, c; // Assume that there is code to initialize these.
+        a &= b | ~c;
+        
+        Previously, this kind of operation would not be efficient, because "~c" would have to
+        create a whole new FastBitVector. But now, it just returns a FastBitVectorImpl whose
+        underlying word view bitnots (~) its words on the fly. Using template magic, this can get
+        pretty complex. For example "b | ~c" returns a FastBitVectorImpl that wraps a word view
+        whose implementation of WordView::word(size_t index) is something like:
+        
+        uint32_t word(size_t index) { return b.m_words.word(index) | ~c.m_words.word(index); }
+        
+        FastBitVectorImpl supports all of the fast bulk bitvector operations, like
+        forEachSetBit(), bitCount(), etc. So, when you say "a &= b | ~c", the actual
+        implementation is going to run these bit operations on word granularity directly over the
+        storage inside a, b, c.
+        
+        The use of operator overloading is worth explaining a bit. Previously, FastBitVector
+        avoided operator overloading. For example, the &= operation was called filter(). I think
+        that this was a pretty good approach at the time. I tried using non-operator methods in
+        this FastBitVector rewrite, but I found it very odd to say things like:
+        
+        a.filter(b.bitOr(c.bitNot()));
+        
+        I think that it's harder to see what is going on here, then using operators, because infix
+        notation is always better.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/BitVector.h:
+        (WTF::BitVector::findBitInWord): Deleted.
+        * wtf/CMakeLists.txt:
+        * wtf/Dominators.h:
+        (WTF::Dominators::NaiveDominators::NaiveDominators):
+        (WTF::Dominators::NaiveDominators::dominates):
+        (WTF::Dominators::NaiveDominators::pruneDominators):
+        * wtf/FastBitVector.cpp: Removed.
+        * wtf/FastBitVector.h:
+        (WTF::fastBitVectorArrayLength):
+        (WTF::FastBitVectorWordView::FastBitVectorWordView):
+        (WTF::FastBitVectorWordView::numBits):
+        (WTF::FastBitVectorWordView::word):
+        (WTF::FastBitVectorWordOwner::FastBitVectorWordOwner):
+        (WTF::FastBitVectorWordOwner::~FastBitVectorWordOwner):
+        (WTF::FastBitVectorWordOwner::view):
+        (WTF::FastBitVectorWordOwner::operator=):
+        (WTF::FastBitVectorWordOwner::setAll):
+        (WTF::FastBitVectorWordOwner::clearAll):
+        (WTF::FastBitVectorWordOwner::set):
+        (WTF::FastBitVectorWordOwner::numBits):
+        (WTF::FastBitVectorWordOwner::arrayLength):
+        (WTF::FastBitVectorWordOwner::resize):
+        (WTF::FastBitVectorWordOwner::word):
+        (WTF::FastBitVectorWordOwner::words):
+        (WTF::FastBitVectorAndWords::FastBitVectorAndWords):
+        (WTF::FastBitVectorAndWords::view):
+        (WTF::FastBitVectorAndWords::numBits):
+        (WTF::FastBitVectorAndWords::word):
+        (WTF::FastBitVectorOrWords::FastBitVectorOrWords):
+        (WTF::FastBitVectorOrWords::view):
+        (WTF::FastBitVectorOrWords::numBits):
+        (WTF::FastBitVectorOrWords::word):
+        (WTF::FastBitVectorNotWords::FastBitVectorNotWords):
+        (WTF::FastBitVectorNotWords::view):
+        (WTF::FastBitVectorNotWords::numBits):
+        (WTF::FastBitVectorNotWords::word):
+        (WTF::FastBitVectorImpl::FastBitVectorImpl):
+        (WTF::FastBitVectorImpl::numBits):
+        (WTF::FastBitVectorImpl::size):
+        (WTF::FastBitVectorImpl::arrayLength):
+        (WTF::FastBitVectorImpl::operator==):
+        (WTF::FastBitVectorImpl::operator!=):
+        (WTF::FastBitVectorImpl::at):
+        (WTF::FastBitVectorImpl::operator[]):
+        (WTF::FastBitVectorImpl::bitCount):
+        (WTF::FastBitVectorImpl::operator&):
+        (WTF::FastBitVectorImpl::operator|):
+        (WTF::FastBitVectorImpl::operator~):
+        (WTF::FastBitVectorImpl::forEachSetBit):
+        (WTF::FastBitVectorImpl::forEachClearBit):
+        (WTF::FastBitVectorImpl::forEachBit):
+        (WTF::FastBitVectorImpl::findBit):
+        (WTF::FastBitVectorImpl::findSetBit):
+        (WTF::FastBitVectorImpl::findClearBit):
+        (WTF::FastBitVectorImpl::dump):
+        (WTF::FastBitVectorImpl::atImpl):
+        (WTF::FastBitVector::FastBitVector):
+        (WTF::FastBitVector::operator=):
+        (WTF::FastBitVector::resize):
+        (WTF::FastBitVector::setAll):
+        (WTF::FastBitVector::clearAll):
+        (WTF::FastBitVector::setAndCheck):
+        (WTF::FastBitVector::operator|=):
+        (WTF::FastBitVector::operator&=):
+        (WTF::FastBitVector::at):
+        (WTF::FastBitVector::operator[]):
+        (WTF::FastBitVector::BitReference::BitReference):
+        (WTF::FastBitVector::BitReference::operator bool):
+        (WTF::FastBitVector::BitReference::operator=):
+        (WTF::FastBitVector::~FastBitVector): Deleted.
+        (WTF::FastBitVector::numBits): Deleted.
+        (WTF::FastBitVector::set): Deleted.
+        (WTF::FastBitVector::equals): Deleted.
+        (WTF::FastBitVector::merge): Deleted.
+        (WTF::FastBitVector::filter): Deleted.
+        (WTF::FastBitVector::exclude): Deleted.
+        (WTF::FastBitVector::clear): Deleted.
+        (WTF::FastBitVector::get): Deleted.
+        (WTF::FastBitVector::bitCount): Deleted.
+        (WTF::FastBitVector::forEachSetBit): Deleted.
+        (WTF::FastBitVector::arrayLength): Deleted.
+        * wtf/StdLibExtras.h:
+        (WTF::findBitInWord):
+
 2016-09-10  Chris Dumez  <cdumez@apple.com>
 
         parseHTMLInteger() should take a StringView in parameter
index 6e585a8..f8b2121 100644 (file)
@@ -31,7 +31,6 @@
                0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
                0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
                0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
-               0F885E0F1845AEA900F1E3FA /* FastBitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F885E0E1845AE9F00F1E3FA /* FastBitVector.cpp */; };
                0F8F2B91172E00FC007DBDA5 /* CompilationThread.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8F2B90172E00F0007DBDA5 /* CompilationThread.h */; };
                0F8F2B92172E0103007DBDA5 /* CompilationThread.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8F2B8F172E00F0007DBDA5 /* CompilationThread.cpp */; };
                0F8F2B9C172F2596007DBDA5 /* ConversionMode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8F2B9B172F2594007DBDA5 /* ConversionMode.h */; };
                2CDED0F318115C85004DBA70 /* RunLoop.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2CDED0F118115C85004DBA70 /* RunLoop.cpp */; };
                2CDED0F418115C85004DBA70 /* RunLoop.h in Headers */ = {isa = PBXBuildFile; fileRef = 2CDED0F218115C85004DBA70 /* RunLoop.h */; };
                430B47891AAAAC1A001223DA /* StringCommon.h in Headers */ = {isa = PBXBuildFile; fileRef = 430B47871AAAAC1A001223DA /* StringCommon.h */; };
+               4B2680DD9B974402899ED572 /* IndexedContainerIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 9C67C542589348E285B49699 /* IndexedContainerIterator.h */; };
                513E170B1CD7D5BF00E3650B /* LoggingAccumulator.h in Headers */ = {isa = PBXBuildFile; fileRef = 513E170A1CD7D5BF00E3650B /* LoggingAccumulator.h */; };
                515F794E1CFC9F4A00CCED93 /* CrossThreadCopier.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 515F794B1CFC9F4A00CCED93 /* CrossThreadCopier.cpp */; };
                515F794F1CFC9F4A00CCED93 /* CrossThreadCopier.h in Headers */ = {isa = PBXBuildFile; fileRef = 515F794C1CFC9F4A00CCED93 /* CrossThreadCopier.h */; };
                A8A4748C151A8264004123FF /* config.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4748B151A8264004123FF /* config.h */; };
                B38FD7BD168953E80065C969 /* FeatureDefines.h in Headers */ = {isa = PBXBuildFile; fileRef = B38FD7BC168953E80065C969 /* FeatureDefines.h */; };
                C4F8A93719C65EB400B2B15D /* Stopwatch.h in Headers */ = {isa = PBXBuildFile; fileRef = C4F8A93619C65EB400B2B15D /* Stopwatch.h */; };
+               C8B0E1A1E01A486EB95E0D11 /* IndexSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 3137E1D7DBD84AC38FAE4D34 /* IndexSet.h */; };
+               C916B975F02F4F7E8B4AB12D /* IndexMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 5B43383A5D0B463C9433D933 /* IndexMap.h */; };
                CD5497AC15857D0300B5BC30 /* MediaTime.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CD5497AA15857D0300B5BC30 /* MediaTime.cpp */; };
                CD5497AD15857D0300B5BC30 /* MediaTime.h in Headers */ = {isa = PBXBuildFile; fileRef = CD5497AB15857D0300B5BC30 /* MediaTime.h */; };
                CE46516E19DB1FB4003ECA05 /* NSMapTableSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */; };
                FE8925B01D00DAEC0046907E /* Indenter.h in Headers */ = {isa = PBXBuildFile; fileRef = FE8925AF1D00DAEC0046907E /* Indenter.h */; };
                FEDACD3D1630F83F00C69634 /* StackStats.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEDACD3B1630F83F00C69634 /* StackStats.cpp */; };
                FEDACD3E1630F83F00C69634 /* StackStats.h in Headers */ = {isa = PBXBuildFile; fileRef = FEDACD3C1630F83F00C69634 /* StackStats.h */; };
-               C8B0E1A1E01A486EB95E0D11 /* IndexSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 3137E1D7DBD84AC38FAE4D34 /* IndexSet.h */; };
-               C916B975F02F4F7E8B4AB12D /* IndexMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 5B43383A5D0B463C9433D933 /* IndexMap.h */; };
-               4B2680DD9B974402899ED572 /* IndexedContainerIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 9C67C542589348E285B49699 /* IndexedContainerIterator.h */; };
 /* End PBXBuildFile section */
 
 /* Begin PBXContainerItemProxy section */
                0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
                0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
                0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
-               0F885E0E1845AE9F00F1E3FA /* FastBitVector.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = FastBitVector.cpp; sourceTree = "<group>"; };
                0F8F2B8F172E00F0007DBDA5 /* CompilationThread.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = CompilationThread.cpp; sourceTree = "<group>"; };
                0F8F2B90172E00F0007DBDA5 /* CompilationThread.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = CompilationThread.h; sourceTree = "<group>"; };
                0F8F2B9B172F2594007DBDA5 /* ConversionMode.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = ConversionMode.h; sourceTree = "<group>"; };
                2CDED0EE18115C38004DBA70 /* RunLoopCF.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RunLoopCF.cpp; sourceTree = "<group>"; };
                2CDED0F118115C85004DBA70 /* RunLoop.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RunLoop.cpp; sourceTree = "<group>"; };
                2CDED0F218115C85004DBA70 /* RunLoop.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RunLoop.h; sourceTree = "<group>"; };
+               3137E1D7DBD84AC38FAE4D34 /* IndexSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexSet.h; sourceTree = "<group>"; };
                430B47871AAAAC1A001223DA /* StringCommon.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringCommon.h; sourceTree = "<group>"; };
                513E170A1CD7D5BF00E3650B /* LoggingAccumulator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LoggingAccumulator.h; sourceTree = "<group>"; };
                515F794B1CFC9F4A00CCED93 /* CrossThreadCopier.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CrossThreadCopier.cpp; sourceTree = "<group>"; };
                515F79551CFD3A6900CCED93 /* CrossThreadQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CrossThreadQueue.h; sourceTree = "<group>"; };
                539EB0621D55284200C82EF7 /* LEBDecoder.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LEBDecoder.h; sourceTree = "<group>"; };
                553071C91C40427200384898 /* TinyLRUCache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyLRUCache.h; sourceTree = "<group>"; };
+               5B43383A5D0B463C9433D933 /* IndexMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexMap.h; sourceTree = "<group>"; };
                5C7C88D31D0A3A0A009D2F6D /* UniqueRef.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniqueRef.h; sourceTree = "<group>"; };
                5D247B6214689B8600E78B76 /* libWTF.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libWTF.a; sourceTree = BUILT_PRODUCTS_DIR; };
                5D247B6E14689C4700E78B76 /* Base.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = Base.xcconfig; sourceTree = "<group>"; };
                974CFC8D16A4F327006D5404 /* WeakPtr.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakPtr.h; sourceTree = "<group>"; };
                9BC70F04176C379D00101DEC /* AtomicStringTable.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringTable.cpp; sourceTree = "<group>"; };
                9BD8F40A176C2AD80002D865 /* AtomicStringTable.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = AtomicStringTable.h; sourceTree = "<group>"; };
+               9C67C542589348E285B49699 /* IndexedContainerIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexedContainerIterator.h; sourceTree = "<group>"; };
                A5098AFF1C169E0700087797 /* SandboxSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SandboxSPI.h; sourceTree = "<group>"; };
                A5098B011C16A4F900087797 /* SecuritySPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SecuritySPI.h; sourceTree = "<group>"; };
                A5BA15F2182433A900A82E69 /* StringMac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = StringMac.mm; path = mac/StringMac.mm; sourceTree = "<group>"; };
                FE8925AF1D00DAEC0046907E /* Indenter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Indenter.h; sourceTree = "<group>"; };
                FEDACD3B1630F83F00C69634 /* StackStats.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StackStats.cpp; sourceTree = "<group>"; };
                FEDACD3C1630F83F00C69634 /* StackStats.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StackStats.h; sourceTree = "<group>"; };
-               3137E1D7DBD84AC38FAE4D34 /* IndexSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IndexSet.h; path = IndexSet.h; sourceTree = "<group>"; };
-               5B43383A5D0B463C9433D933 /* IndexMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IndexMap.h; path = IndexMap.h; sourceTree = "<group>"; };
-               9C67C542589348E285B49699 /* IndexedContainerIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IndexedContainerIterator.h; path = IndexedContainerIterator.h; sourceTree = "<group>"; };
 /* End PBXFileReference section */
 
 /* Begin PBXFrameworksBuildPhase section */
                                A8A47298151A825A004123FF /* dtoa.h */,
                                1AEA88E11D6BBCF400E5AD64 /* EnumTraits.h */,
                                A8A4729F151A825A004123FF /* ExportMacros.h */,
-                               0F885E0E1845AE9F00F1E3FA /* FastBitVector.cpp */,
                                0FD81AC4154FB22E00983E72 /* FastBitVector.h */,
                                A8A472A1151A825A004123FF /* FastMalloc.cpp */,
                                A8A472A2151A825A004123FF /* FastMalloc.h */,
                                A8A473B0151A825B004123FF /* double-conversion.cc in Sources */,
                                A8A473BA151A825B004123FF /* dtoa.cpp in Sources */,
                                A8A473B3151A825B004123FF /* fast-dtoa.cc in Sources */,
-                               0F885E0F1845AEA900F1E3FA /* FastBitVector.cpp in Sources */,
                                A8A473C3151A825B004123FF /* FastMalloc.cpp in Sources */,
                                0F9D3360165DBA73005AD387 /* FilePrintStream.cpp in Sources */,
                                A8A473B5151A825B004123FF /* fixed-dtoa.cc in Sources */,
index 767f223..762cc04 100644 (file)
@@ -403,21 +403,6 @@ private:
         return size();
     }
     
-    static bool findBitInWord(uintptr_t word, size_t& index, size_t endIndex, bool value)
-    {
-        word >>= index;
-        
-        while (index < endIndex) {
-            if ((word & 1) == static_cast<uintptr_t>(value))
-                return true;
-            index++;
-            word >>= 1;
-        }
-
-        index = endIndex;
-        return false;
-    }
-    
     class OutOfLineBits {
     public:
         size_t numBits() const { return m_numBits; }
index 867999e..857b06c 100644 (file)
@@ -181,7 +181,6 @@ set(WTF_SOURCES
     DataLog.cpp
     DateMath.cpp
     DecimalNumber.cpp
-    FastBitVector.cpp
     FastMalloc.cpp
     FilePrintStream.cpp
     FunctionDispatcher.cpp
index 386b3c4..dbc7240 100644 (file)
@@ -515,14 +515,14 @@ private:
 
             // We know that the entry block is only dominated by itself.
             m_results[0].clearAll();
-            m_results[0].set(0);
+            m_results[0][0] = true;
 
             // Find all of the valid blocks.
             m_scratch.clearAll();
             for (unsigned i = numBlocks; i--;) {
                 if (!graph.node(i))
                     continue;
-                m_scratch.set(i);
+                m_scratch[i] = true;
             }
     
             // Mark all nodes as dominated by everything.
@@ -530,7 +530,7 @@ private:
                 if (!graph.node(i) || !graph.predecessors(graph.node(i)).size())
                     m_results[i].clearAll();
                 else
-                    m_results[i].set(m_scratch);
+                    m_results[i] = m_scratch;
             }
 
             // Iteratively eliminate nodes that are not dominator.
@@ -553,7 +553,7 @@ private:
         
         bool dominates(unsigned from, unsigned to) const
         {
-            return m_results[to].get(from);
+            return m_results[to][from];
         }
     
         bool dominates(typename Graph::Node from, typename Graph::Node to) const
@@ -586,12 +586,12 @@ private:
                 return false;
 
             // Find the intersection of dom(preds).
-            m_scratch.set(m_results[m_graph.index(m_graph.predecessors(block)[0])]);
+            m_scratch = m_results[m_graph.index(m_graph.predecessors(block)[0])];
             for (unsigned j = m_graph.predecessors(block).size(); j-- > 1;)
-                m_scratch.filter(m_results[m_graph.index(m_graph.predecessors(block)[j])]);
+                m_scratch &= m_results[m_graph.index(m_graph.predecessors(block)[j])];
 
             // The block is also dominated by itself.
-            m_scratch.set(idx);
+            m_scratch[idx] = true;
 
             return m_results[idx].setAndCheck(m_scratch);
         }
diff --git a/Source/WTF/wtf/FastBitVector.cpp b/Source/WTF/wtf/FastBitVector.cpp
deleted file mode 100644 (file)
index 3abccea..0000000
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
- * 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 "FastBitVector.h"
-
-#include "PrintStream.h"
-
-namespace WTF {
-
-void FastBitVector::dump(PrintStream& out) const
-{
-    for (unsigned i = 0; i < m_numBits; ++i)
-        out.print(get(i) ? "1" : "-");
-}
-
-} // namespace WTF
-
index ff00b7b..6c222d7 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2012, 2013, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 #include <string.h>
 #include <wtf/FastMalloc.h>
+#include <wtf/PrintStream.h>
 #include <wtf/StdLibExtras.h>
 
 namespace WTF {
 
 class PrintStream;
 
-class FastBitVector {
+inline size_t fastBitVectorArrayLength(size_t numBits) { return (numBits + 31) / 32; }
+
+class FastBitVectorWordView {
 public:
-    FastBitVector() = default;
+    typedef FastBitVectorWordView ViewType;
+    
+    FastBitVectorWordView() { }
+    
+    FastBitVectorWordView(const uint32_t* array, size_t numBits)
+        : m_words(array)
+        , m_numBits(numBits)
+    {
+    }
+    
+    size_t numBits() const
+    {
+        return m_numBits;
+    }
+    
+    uint32_t word(size_t index) const
+    {
+        ASSERT_WITH_SECURITY_IMPLICATION(index < fastBitVectorArrayLength(numBits()));
+        return m_words[index];
+    }
+    
+private:
+    const uint32_t* m_words { nullptr };
+    size_t m_numBits { 0 };
+};
 
-    FastBitVector(FastBitVector&& other)
-        : m_array(std::exchange(other.m_array, nullptr))
+class FastBitVectorWordOwner {
+public:
+    typedef FastBitVectorWordView ViewType;
+    
+    FastBitVectorWordOwner() = default;
+    
+    FastBitVectorWordOwner(FastBitVectorWordOwner&& other)
+        : m_words(std::exchange(other.m_words, nullptr))
         , m_numBits(std::exchange(other.m_numBits, 0))
     {
     }
 
-    FastBitVector(const FastBitVector& other)
-        : m_array(0)
-        , m_numBits(0)
+    FastBitVectorWordOwner(const FastBitVectorWordOwner& other)
     {
         *this = other;
     }
     
-    ~FastBitVector()
+    ~FastBitVectorWordOwner()
     {
-        if (m_array)
-            fastFree(m_array);
+        if (m_words)
+            fastFree(m_words);
     }
     
-    FastBitVector& operator=(const FastBitVector& other)
+    FastBitVectorWordView view() const { return FastBitVectorWordView(m_words, m_numBits); }
+    
+    FastBitVectorWordOwner& operator=(const FastBitVectorWordOwner& other)
     {
         size_t length = other.arrayLength();
-        uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, 4));
-        memcpy(newArray, other.m_array, length * 4);
-        if (m_array)
-            fastFree(m_array);
-        m_array = newArray;
+        if (length == arrayLength()) {
+            memcpy(m_words, other.m_words, length * sizeof(uint32_t));
+            return *this;
+        }
+        uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, sizeof(uint32_t)));
+        memcpy(newArray, other.m_words, length * sizeof(uint32_t));
+        if (m_words)
+            fastFree(m_words);
+        m_words = newArray;
         m_numBits = other.m_numBits;
         return *this;
     }
     
-    size_t numBits() const { return m_numBits; }
+    FastBitVectorWordOwner& operator=(FastBitVectorWordOwner&& other)
+    {
+        std::swap(m_words, other.m_words);
+        std::swap(m_numBits, other.m_numBits);
+        return *this;
+    }
+    
+    void setAll()
+    {
+        memset(m_words, 255, arrayLength() * sizeof(uint32_t));
+    }
+    
+    void clearAll()
+    {
+        memset(m_words, 0, arrayLength() * sizeof(uint32_t));
+    }
+    
+    void set(const FastBitVectorWordOwner& other)
+    {
+        ASSERT_WITH_SECURITY_IMPLICATION(m_numBits == other.m_numBits);
+        memcpy(m_words, other.m_words, arrayLength() * sizeof(uint32_t));
+    }
+    
+    size_t numBits() const
+    {
+        return m_numBits;
+    }
+    
+    size_t arrayLength() const
+    {
+        return fastBitVectorArrayLength(numBits());
+    }
     
     void resize(size_t numBits)
     {
@@ -78,133 +146,408 @@ public:
         // Use fastCalloc instead of fastRealloc because we expect the common
         // use case for this method to be initializing the size of the bitvector.
         
-        size_t newLength = arrayLength(numBits);
-        uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(newLength, 4));
-        memcpy(newArray, m_array, arrayLength() * 4);
-        if (m_array)
-            fastFree(m_array);
-        m_array = newArray;
+        size_t newLength = fastBitVectorArrayLength(numBits);
+        uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(newLength, sizeof(uint32_t)));
+        memcpy(newArray, m_words, arrayLength() * sizeof(uint32_t));
+        if (m_words)
+            fastFree(m_words);
+        m_words = newArray;
         m_numBits = numBits;
     }
     
-    void setAll()
+    uint32_t word(size_t index) const
     {
-        memset(m_array, 255, arrayLength() * 4);
+        ASSERT_WITH_SECURITY_IMPLICATION(index < arrayLength());
+        return m_words[index];
     }
     
-    void clearAll()
+    uint32_t& word(size_t index)
     {
-        memset(m_array, 0, arrayLength() * 4);
+        ASSERT_WITH_SECURITY_IMPLICATION(index < arrayLength());
+        return m_words[index];
     }
     
-    void set(const FastBitVector& other)
+    const uint32_t* words() const { return m_words; }
+    uint32_t* words() { return m_words; }
+
+private:
+    uint32_t* m_words { nullptr };
+    size_t m_numBits { 0 };
+};
+
+template<typename Left, typename Right>
+class FastBitVectorAndWords {
+public:
+    typedef FastBitVectorAndWords ViewType;
+    
+    FastBitVectorAndWords(const Left& left, const Right& right)
+        : m_left(left)
+        , m_right(right)
     {
-        ASSERT(m_numBits == other.m_numBits);
-        memcpy(m_array, other.m_array, arrayLength() * 4);
+        ASSERT_WITH_SECURITY_IMPLICATION(m_left.numBits() == m_right.numBits());
     }
     
-    bool setAndCheck(const FastBitVector& other)
+    FastBitVectorAndWords view() const { return *this; }
+    
+    size_t numBits() const
     {
-        bool changed = false;
-        ASSERT(m_numBits == other.m_numBits);
-        for (unsigned i = arrayLength(); i--;) {
-            changed |= m_array[i] != other.m_array[i];
-            m_array[i] = other.m_array[i];
-        }
-        return changed;
+        return m_left.numBits();
     }
     
-    bool equals(const FastBitVector& other) const
+    uint32_t word(size_t index) const
     {
-        ASSERT(m_numBits == other.m_numBits);
-        // Use my own comparison loop because memcmp does more than what I want
-        // and bcmp is not as standard.
-        for (unsigned i = arrayLength(); i--;) {
-            if (m_array[i] != other.m_array[i])
-                return false;
-        }
-        return true;
+        return m_left.word(index) & m_right.word(index);
     }
     
-    void merge(const FastBitVector& other)
+private:
+    Left m_left;
+    Right m_right;
+};
+    
+template<typename Left, typename Right>
+class FastBitVectorOrWords {
+public:
+    typedef FastBitVectorOrWords ViewType;
+    
+    FastBitVectorOrWords(const Left& left, const Right& right)
+        : m_left(left)
+        , m_right(right)
     {
-        ASSERT(m_numBits == other.m_numBits);
-        for (unsigned i = arrayLength(); i--;)
-            m_array[i] |= other.m_array[i];
+        ASSERT_WITH_SECURITY_IMPLICATION(m_left.numBits() == m_right.numBits());
     }
     
-    void filter(const FastBitVector& other)
+    FastBitVectorOrWords view() const { return *this; }
+    
+    size_t numBits() const
     {
-        ASSERT(m_numBits == other.m_numBits);
-        for (unsigned i = arrayLength(); i--;)
-            m_array[i] &= other.m_array[i];
+        return m_left.numBits();
     }
     
-    void exclude(const FastBitVector& other)
+    uint32_t word(size_t index) const
     {
-        ASSERT(m_numBits == other.m_numBits);
-        for (unsigned i = arrayLength(); i--;)
-            m_array[i] &= ~other.m_array[i];
+        return m_left.word(index) | m_right.word(index);
     }
     
-    void set(size_t i)
+private:
+    Left m_left;
+    Right m_right;
+};
+    
+template<typename View>
+class FastBitVectorNotWords {
+public:
+    typedef FastBitVectorNotWords ViewType;
+    
+    FastBitVectorNotWords(const View& view)
+        : m_view(view)
     {
-        ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
-        m_array[i >> 5] |= (1 << (i & 31));
     }
     
-    void clear(size_t i)
+    FastBitVectorNotWords view() const { return *this; }
+    
+    size_t numBits() const
     {
-        ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
-        m_array[i >> 5] &= ~(1 << (i & 31));
+        return m_view.numBits();
     }
     
-    void set(size_t i, bool value)
+    uint32_t word(size_t index) const
     {
-        if (value)
-            set(i);
-        else
-            clear(i);
+        return ~m_view.word(index);
+    }
+    
+private:
+    View m_view;
+};
+    
+class FastBitVector;
+
+template<typename Words>
+class FastBitVectorImpl {
+public:
+    FastBitVectorImpl()
+        : m_words()
+    {
+    }
+    
+    FastBitVectorImpl(const Words& words)
+        : m_words(words)
+    {
+    }
+    
+    FastBitVectorImpl(Words&& words)
+        : m_words(WTFMove(words))
+    {
+    }
+
+    size_t numBits() const { return m_words.numBits(); }
+    size_t size() const { return numBits(); }
+    
+    size_t arrayLength() const { return fastBitVectorArrayLength(numBits()); }
+    
+    template<typename Other>
+    bool operator==(const Other& other) const
+    {
+        if (numBits() != other.numBits())
+            return false;
+        for (size_t i = arrayLength(); i--;) {
+            if (m_words.word(i) != other.m_words.word(i))
+                return false;
+        }
+        return true;
     }
     
-    bool get(size_t i) const
+    template<typename Other>
+    bool operator!=(const Other& other) const
     {
-        ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
-        return !!(m_array[i >> 5] & (1 << (i & 31)));
+        return !(*this == other);
+    }
+    
+    bool at(size_t index) const
+    {
+        return atImpl(index);
+    }
+    
+    bool operator[](size_t index) const
+    {
+        return atImpl(index);
     }
     
     size_t bitCount() const
     {
         size_t result = 0;
-        for (unsigned i = arrayLength(); i--;)
-            result += WTF::bitCount(m_array[i]);
+        for (size_t index = arrayLength(); index--;)
+            result += WTF::bitCount(m_words.word(index));
         return result;
     }
     
-    template<typename Functor>
-    void forEachSetBit(const Functor& functor) const
+    template<typename OtherWords>
+    FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>> operator&(const FastBitVectorImpl<OtherWords>& other) const
     {
-        unsigned n = arrayLength();
-        for (unsigned i = 0; i < n; ++i) {
-            uint32_t word = m_array[i];
-            unsigned j = i << 5;
+        return FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>(m_words.view(), other.m_words.view()));
+    }
+    
+    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()));
+    }
+    
+    FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>> operator~() const
+    {
+        return FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>>(FastBitVectorNotWords<typename Words::ViewType>(m_words.view()));
+    }
+    
+    template<typename Func>
+    ALWAYS_INLINE void forEachSetBit(const Func& func) const
+    {
+        size_t n = m_words.arrayLength();
+        for (size_t i = 0; i < n; ++i) {
+            uint32_t word = m_words.word(i);
+            size_t j = i * 32;
             while (word) {
                 if (word & 1)
-                    functor(j);
+                    func(j);
                 word >>= 1;
                 j++;
             }
         }
     }
-
-    WTF_EXPORT_PRIVATE void dump(PrintStream&) const;
+    
+    template<typename Func>
+    ALWAYS_INLINE void forEachClearBit(const Func& func) const
+    {
+        (~*this).forEachSetBit(func);
+    }
+    
+    template<typename Func>
+    void forEachBit(bool value, const Func& func) const
+    {
+        if (value)
+            forEachSetBit(func);
+        else
+            forEachClearBit(func);
+    }
+    
+    // Starts looking for bits at the index you pass. If that index contains the value you want,
+    // then it will return that index. Returns numBits when we get to the end. For example, you
+    // can write a loop to iterate over all set bits like this:
+    //
+    // for (size_t i = 0; i < bits.numBits(); i = bits.findBit(i + 1, true))
+    //     ...
+    ALWAYS_INLINE size_t findBit(size_t startIndex, bool value) const
+    {
+        // If value is true, this produces 0. If value is false, this produces UINT_MAX. It's
+        // written this way so that it performs well regardless of whether value is a constant.
+        uint32_t skipValue = -(static_cast<uint32_t>(value) ^ 1);
+        
+        size_t numWords = m_words.arrayLength();
+        
+        size_t wordIndex = startIndex / 32;
+        size_t startIndexInWord = startIndex - wordIndex * 32;
+        
+        while (wordIndex < numWords) {
+            uint32_t word = m_words.word(wordIndex);
+            if (word != skipValue) {
+                size_t index = startIndexInWord;
+                if (findBitInWord(word, index, 32, value))
+                    return wordIndex * 32 + index;
+            }
+            
+            wordIndex++;
+            startIndexInWord = 0;
+        }
+        
+        return numBits();
+    }
+    
+    ALWAYS_INLINE size_t findSetBit(size_t index) const
+    {
+        return findBit(index, true);
+    }
+    
+    ALWAYS_INLINE size_t findClearBit(size_t index) const
+    {
+        return findBit(index, false);
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        for (size_t i = 0; i < numBits(); ++i)
+            out.print((*this)[i] ? "1" : "-");
+    }
     
 private:
-    static size_t arrayLength(size_t numBits) { return (numBits + 31) >> 5; }
-    size_t arrayLength() const { return arrayLength(m_numBits); }
+    // You'd think that we could remove this friend if we used protected, but you'd be wrong,
+    // because templates.
+    friend class FastBitVector;
     
-    uint32_t* m_array { nullptr }; // No, this can't be an std::unique_ptr<uint32_t[]>.
-    size_t m_numBits { 0 };
+    bool atImpl(size_t index) const
+    {
+        ASSERT_WITH_SECURITY_IMPLICATION(index < numBits());
+        return !!(m_words.word(index >> 5) & (1 << (index & 31)));
+    }
+    
+    Words m_words;
+};
+
+class FastBitVector : public FastBitVectorImpl<FastBitVectorWordOwner> {
+public:
+    FastBitVector() { }
+    
+    FastBitVector(const FastBitVector&) = default;
+    FastBitVector& operator=(const FastBitVector&) = default;
+    
+    template<typename OtherWords>
+    FastBitVector(const FastBitVectorImpl<OtherWords>& other)
+    {
+        *this = other;
+    }
+    
+    template<typename OtherWords>
+    FastBitVector& operator=(const FastBitVectorImpl<OtherWords>& other)
+    {
+        if (UNLIKELY(numBits() != other.numBits()))
+            resize(other.numBits());
+        
+        for (unsigned i = arrayLength(); i--;)
+            m_words.word(i) = other.m_words.word(i);
+        return *this;
+    }
+    
+    void resize(size_t numBits)
+    {
+        m_words.resize(numBits);
+    }
+    
+    void setAll()
+    {
+        m_words.setAll();
+    }
+    
+    void clearAll()
+    {
+        m_words.clearAll();
+    }
+
+    template<typename OtherWords>
+    bool setAndCheck(const FastBitVectorImpl<OtherWords>& other)
+    {
+        bool changed = false;
+        ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
+        for (unsigned i = arrayLength(); i--;) {
+            changed |= m_words.word(i) != other.m_words.word(i);
+            m_words.word(i) = other.m_words.word(i);
+        }
+        return changed;
+    }
+    
+    template<typename OtherWords>
+    FastBitVector& operator|=(const FastBitVectorImpl<OtherWords>& other)
+    {
+        ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
+        for (unsigned i = arrayLength(); i--;)
+            m_words.word(i) |= other.m_words.word(i);
+        return *this;
+    }
+    
+    template<typename OtherWords>
+    FastBitVector& operator&=(const FastBitVectorImpl<OtherWords>& other)
+    {
+        ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
+        for (unsigned i = arrayLength(); i--;)
+            m_words.word(i) &= other.m_words.word(i);
+        return *this;
+    }
+    
+    bool at(size_t index) const
+    {
+        return atImpl(index);
+    }
+    
+    bool operator[](size_t index) const
+    {
+        return atImpl(index);
+    }
+    
+    class BitReference {
+    public:
+        BitReference() { }
+        
+        BitReference(uint32_t* word, uint32_t mask)
+            : m_word(word)
+            , m_mask(mask)
+        {
+        }
+        
+        explicit operator bool() const
+        {
+            return !!(*m_word & m_mask);
+        }
+        
+        BitReference& operator=(bool value)
+        {
+            if (value)
+                *m_word |= m_mask;
+            else
+                *m_word &= ~m_mask;
+            return *this;
+        }
+        
+    private:
+        uint32_t* m_word { nullptr };
+        uint32_t m_mask { 0 };
+    };
+    
+    BitReference at(size_t index)
+    {
+        ASSERT_WITH_SECURITY_IMPLICATION(index < numBits());
+        return BitReference(&m_words.word(index >> 5), 1 << (index & 31));
+    }
+    
+    BitReference operator[](size_t index)
+    {
+        return at(index);
+    }
 };
 
 } // namespace WTF
index 5481939..ebe30c9 100644 (file)
@@ -317,6 +317,24 @@ bool checkAndSet(T& left, U right)
     return true;
 }
 
+template<typename T>
+bool findBitInWord(T word, size_t& index, size_t endIndex, bool value)
+{
+    static_assert(std::is_unsigned<T>::value, "Type used in findBitInWord must be unsigned");
+    
+    word >>= index;
+    
+    while (index < endIndex) {
+        if ((word & 1) == static_cast<T>(value))
+            return true;
+        index++;
+        word >>= 1;
+    }
+    
+    index = endIndex;
+    return false;
+}
+
 // Visitor adapted from http://stackoverflow.com/questions/25338795/is-there-a-name-for-this-tuple-creation-idiom
 
 template <class A, class... B>
@@ -421,6 +439,7 @@ using WTF::binarySearch;
 using WTF::bitwise_cast;
 using WTF::callStatelessLambda;
 using WTF::checkAndSet;
+using WTF::findBitInWord;
 using WTF::insertIntoBoundedVector;
 using WTF::isCompilationThread;
 using WTF::isPointerAligned;