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)
commitf6413bb3fd2b5f68657f30ac13642f2c4e0dd035
tree887f15d2fd19ab3c739205d7226276aac3b2a3d8
parentb1029e460f2c8d3bb2d4034c890a4be481a406c6
FastBitVector should have efficient and easy-to-use vector-vector operations
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