Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (205793 => 205794)
--- trunk/Source/_javascript_Core/ChangeLog 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-09-12 04:03:36 UTC (rev 205794)
@@ -1,3 +1,35 @@
+2016-09-11 Filip Pizlo <[email protected]>
+
+ 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 <[email protected]>
parseHTMLInteger() should take a StringView in parameter
Modified: trunk/Source/_javascript_Core/bytecode/BytecodeLivenessAnalysis.cpp (205793 => 205794)
--- trunk/Source/_javascript_Core/bytecode/BytecodeLivenessAnalysis.cpp 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/bytecode/BytecodeLivenessAnalysis.cpp 2016-09-12 04:03:36 UTC (rev 205794)
@@ -121,14 +121,14 @@
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 @@
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 @@
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");
Modified: trunk/Source/_javascript_Core/bytecode/BytecodeLivenessAnalysisInlines.h (205793 => 205794)
--- trunk/Source/_javascript_Core/bytecode/BytecodeLivenessAnalysisInlines.h 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/bytecode/BytecodeLivenessAnalysisInlines.h 2016-09-12 04:03:36 UTC (rev 205794)
@@ -43,7 +43,7 @@
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 @@
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 @@
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);
Modified: trunk/Source/_javascript_Core/bytecode/CodeBlock.cpp (205793 => 205794)
--- trunk/Source/_javascript_Core/bytecode/CodeBlock.cpp 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/bytecode/CodeBlock.cpp 2016-09-12 04:03:36 UTC (rev 205794)
@@ -4292,7 +4292,7 @@
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");
Modified: trunk/Source/_javascript_Core/dfg/DFGByteCodeParser.cpp (205793 => 205794)
--- trunk/Source/_javascript_Core/dfg/DFGByteCodeParser.cpp 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/dfg/DFGByteCodeParser.cpp 2016-09-12 04:03:36 UTC (rev 205794)
@@ -638,7 +638,7 @@
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);
Modified: trunk/Source/_javascript_Core/dfg/DFGForAllKills.h (205793 => 205794)
--- trunk/Source/_javascript_Core/dfg/DFGForAllKills.h 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/dfg/DFGForAllKills.h 2016-09-12 04:03:36 UTC (rev 205794)
@@ -76,8 +76,11 @@
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);
}
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (205793 => 205794)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.h 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h 2016-09-12 04:03:36 UTC (rev 205794)
@@ -745,7 +745,7 @@
if (reg >= exclusionStart && reg < exclusionEnd)
continue;
- if (liveness.get(relativeLocal))
+ if (liveness[relativeLocal])
functor(reg);
}
Modified: trunk/Source/_javascript_Core/dfg/DFGLiveCatchVariablePreservationPhase.cpp (205793 => 205794)
--- trunk/Source/_javascript_Core/dfg/DFGLiveCatchVariablePreservationPhase.cpp 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/dfg/DFGLiveCatchVariablePreservationPhase.cpp 2016-09-12 04:03:36 UTC (rev 205794)
@@ -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 @@
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 @@
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 @@
{
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);
Modified: trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp (205793 => 205794)
--- trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp 2016-09-12 04:03:36 UTC (rev 205794)
@@ -105,7 +105,7 @@
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 @@
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;
}
}
}
Modified: trunk/Source/_javascript_Core/dfg/DFGPlan.cpp (205793 => 205794)
--- trunk/Source/_javascript_Core/dfg/DFGPlan.cpp 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/_javascript_Core/dfg/DFGPlan.cpp 2016-09-12 04:03:36 UTC (rev 205794)
@@ -691,7 +691,7 @@
FastBitVector liveness = codeBlock->alternative()->livenessAnalysis().getLivenessInfoAtBytecodeOffset(osrEntryBytecodeIndex);
for (unsigned local = mustHandleValues.numberOfLocals(); local--;) {
- if (!liveness.get(local))
+ if (!liveness[local])
mustHandleValues.local(local) = jsUndefined();
}
}
Modified: trunk/Source/WTF/ChangeLog (205793 => 205794)
--- trunk/Source/WTF/ChangeLog 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/WTF/ChangeLog 2016-09-12 04:03:36 UTC (rev 205794)
@@ -1,3 +1,143 @@
+2016-09-11 Filip Pizlo <[email protected]>
+
+ 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 <[email protected]>
parseHTMLInteger() should take a StringView in parameter
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (205793 => 205794)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-09-12 04:03:36 UTC (rev 205794)
@@ -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 */; };
@@ -111,6 +110,7 @@
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 */; };
@@ -315,6 +315,8 @@
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 */; };
@@ -336,9 +338,6 @@
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 */
@@ -370,7 +369,6 @@
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>"; };
@@ -453,6 +451,7 @@
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>"; };
@@ -461,6 +460,7 @@
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>"; };
@@ -491,6 +491,7 @@
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>"; };
@@ -687,9 +688,6 @@
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 */
@@ -882,7 +880,6 @@
A8A47298151A825A004123FF /* dtoa.h */,
1AEA88E11D6BBCF400E5AD64 /* EnumTraits.h */,
A8A4729F151A825A004123FF /* ExportMacros.h */,
- 0F885E0E1845AE9F00F1E3FA /* FastBitVector.cpp */,
0FD81AC4154FB22E00983E72 /* FastBitVector.h */,
A8A472A1151A825A004123FF /* FastMalloc.cpp */,
A8A472A2151A825A004123FF /* FastMalloc.h */,
@@ -1584,7 +1581,6 @@
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 */,
Modified: trunk/Source/WTF/wtf/BitVector.h (205793 => 205794)
--- trunk/Source/WTF/wtf/BitVector.h 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/WTF/wtf/BitVector.h 2016-09-12 04:03:36 UTC (rev 205794)
@@ -403,21 +403,6 @@
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; }
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (205793 => 205794)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-09-12 04:03:36 UTC (rev 205794)
@@ -181,7 +181,6 @@
DataLog.cpp
DateMath.cpp
DecimalNumber.cpp
- FastBitVector.cpp
FastMalloc.cpp
FilePrintStream.cpp
FunctionDispatcher.cpp
Modified: trunk/Source/WTF/wtf/Dominators.h (205793 => 205794)
--- trunk/Source/WTF/wtf/Dominators.h 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/WTF/wtf/Dominators.h 2016-09-12 04:03:36 UTC (rev 205794)
@@ -515,7 +515,7 @@
// 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();
@@ -522,7 +522,7 @@
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 @@
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 @@
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 @@
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);
}
Deleted: trunk/Source/WTF/wtf/FastBitVector.cpp (205793 => 205794)
--- trunk/Source/WTF/wtf/FastBitVector.cpp 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/WTF/wtf/FastBitVector.cpp 2016-09-12 04:03:36 UTC (rev 205794)
@@ -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
-
Modified: trunk/Source/WTF/wtf/FastBitVector.h (205793 => 205794)
--- trunk/Source/WTF/wtf/FastBitVector.h 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/WTF/wtf/FastBitVector.h 2016-09-12 04:03:36 UTC (rev 205794)
@@ -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
@@ -27,6 +27,7 @@
#include <string.h>
#include <wtf/FastMalloc.h>
+#include <wtf/PrintStream.h>
#include <wtf/StdLibExtras.h>
namespace WTF {
@@ -33,43 +34,110 @@
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)
{
if (numBits == m_numBits)
@@ -78,135 +146,410 @@
// 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);
}
- bool get(size_t i) const
+private:
+ View m_view;
+};
+
+class FastBitVector;
+
+template<typename Words>
+class FastBitVectorImpl {
+public:
+ FastBitVectorImpl()
+ : m_words()
{
- ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
- return !!(m_array[i >> 5] & (1 << (i & 31)));
}
+ 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;
+ }
+
+ template<typename Other>
+ bool operator!=(const Other& other) const
+ {
+ 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
using WTF::FastBitVector;
Modified: trunk/Source/WTF/wtf/StdLibExtras.h (205793 => 205794)
--- trunk/Source/WTF/wtf/StdLibExtras.h 2016-09-12 03:29:04 UTC (rev 205793)
+++ trunk/Source/WTF/wtf/StdLibExtras.h 2016-09-12 04:03:36 UTC (rev 205794)
@@ -317,6 +317,24 @@
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::bitwise_cast;
using WTF::callStatelessLambda;
using WTF::checkAndSet;
+using WTF::findBitInWord;
using WTF::insertIntoBoundedVector;
using WTF::isCompilationThread;
using WTF::isPointerAligned;
