Skip to content

Commit d0a4b6a

Browse files
author
Filip Pizlo
committed
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): Canonical link: https://commits.webkit.org/180007@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@205794 268f45cc-cd09-0410-ab3c-d52691b4dbfc
1 parent 8e675a2 commit d0a4b6a

18 files changed

Lines changed: 661 additions & 184 deletions

‎Source/JavaScriptCore/ChangeLog‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,35 @@
1+
2016-09-11 Filip Pizlo <fpizlo@apple.com>
2+
3+
FastBitVector should have efficient and easy-to-use vector-vector operations
4+
https://bugs.webkit.org/show_bug.cgi?id=161847
5+
6+
Reviewed by Saam Barati.
7+
8+
Adapt existing users of FastBitVector to the new API.
9+
10+
* bytecode/BytecodeLivenessAnalysis.cpp:
11+
(JSC::BytecodeLivenessAnalysis::computeKills):
12+
(JSC::BytecodeLivenessAnalysis::dumpResults):
13+
* bytecode/BytecodeLivenessAnalysisInlines.h:
14+
(JSC::operandThatIsNotAlwaysLiveIsLive):
15+
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::stepOverInstruction):
16+
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::runLivenessFixpoint):
17+
* bytecode/CodeBlock.cpp:
18+
(JSC::CodeBlock::validate):
19+
* dfg/DFGByteCodeParser.cpp:
20+
(JSC::DFG::ByteCodeParser::flushForTerminal):
21+
* dfg/DFGForAllKills.h:
22+
(JSC::DFG::forAllKilledOperands):
23+
* dfg/DFGGraph.h:
24+
(JSC::DFG::Graph::forAllLocalsLiveInBytecode):
25+
* dfg/DFGLiveCatchVariablePreservationPhase.cpp:
26+
(JSC::DFG::LiveCatchVariablePreservationPhase::willCatchException):
27+
(JSC::DFG::LiveCatchVariablePreservationPhase::handleBlock):
28+
* dfg/DFGNaturalLoops.cpp:
29+
(JSC::DFG::NaturalLoops::NaturalLoops):
30+
* dfg/DFGPlan.cpp:
31+
(JSC::DFG::Plan::cleanMustHandleValuesIfNecessary):
32+
133
2016-09-10 Chris Dumez <cdumez@apple.com>
234

335
parseHTMLInteger() should take a StringView in parameter

‎Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -121,14 +121,14 @@ void BytecodeLivenessAnalysis::computeKills(BytecodeKills& result)
121121
m_graph, bytecodeOffset, out,
122122
[&] (unsigned index) {
123123
// This is for uses.
124-
if (out.get(index))
124+
if (out[index])
125125
return;
126126
result.m_killSets[bytecodeOffset].add(index);
127-
out.set(index);
127+
out[index] = true;
128128
},
129129
[&] (unsigned index) {
130130
// This is for defs.
131-
out.clear(index);
131+
out[index] = false;
132132
});
133133
}
134134
}
@@ -163,7 +163,7 @@ void BytecodeLivenessAnalysis::dumpResults()
163163
dataLogF("Live variables: ");
164164
FastBitVector liveBefore = getLivenessInfoAtBytecodeOffset(bytecodeOffset);
165165
for (unsigned j = 0; j < liveBefore.numBits(); j++) {
166-
if (liveBefore.get(j))
166+
if (liveBefore[j])
167167
dataLogF("%u ", j);
168168
}
169169
dataLogF("\n");
@@ -177,7 +177,7 @@ void BytecodeLivenessAnalysis::dumpResults()
177177
dataLogF("Live variables: ");
178178
FastBitVector liveAfter = block->out();
179179
for (unsigned j = 0; j < liveAfter.numBits(); j++) {
180-
if (liveAfter.get(j))
180+
if (liveAfter[j])
181181
dataLogF("%u ", j);
182182
}
183183
dataLogF("\n");

‎Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysisInlines.h‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,7 @@ inline bool operandThatIsNotAlwaysLiveIsLive(const FastBitVector& out, int opera
4343
unsigned local = VirtualRegister(operand).toLocal();
4444
if (local >= out.numBits())
4545
return false;
46-
return out.get(local);
46+
return out[local];
4747
}
4848

4949
inline bool operandIsLive(const FastBitVector& out, int operand)
@@ -117,11 +117,11 @@ inline void BytecodeLivenessPropagation<DerivedAnalysis>::stepOverInstruction(Gr
117117
graph, bytecodeOffset, out,
118118
[&] (unsigned bitIndex) {
119119
// This is the use functor, so we set the bit.
120-
out.set(bitIndex);
120+
out[bitIndex] = true;
121121
},
122122
[&] (unsigned bitIndex) {
123123
// This is the def functor, so we clear the bit.
124-
out.clear(bitIndex);
124+
out[bitIndex] = false;
125125
});
126126
}
127127

@@ -191,8 +191,8 @@ inline void BytecodeLivenessPropagation<DerivedAnalysis>::runLivenessFixpoint(Gr
191191
for (std::unique_ptr<BytecodeBasicBlock>& block : graph.basicBlocksInReverseOrder()) {
192192
newOut.clearAll();
193193
for (BytecodeBasicBlock* successor : block->successors())
194-
newOut.merge(successor->in());
195-
block->out().set(newOut);
194+
newOut |= successor->in();
195+
block->out() = newOut;
196196
changed |= computeLocalLivenessForBlock(graph, block.get());
197197
}
198198
} while (changed);

‎Source/JavaScriptCore/bytecode/CodeBlock.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4292,7 +4292,7 @@ void CodeBlock::validate()
42924292
for (unsigned i = m_numCalleeLocals; i--;) {
42934293
VirtualRegister reg = virtualRegisterForLocal(i);
42944294

4295-
if (liveAtHead.get(i)) {
4295+
if (liveAtHead[i]) {
42964296
beginValidationDidFail();
42974297
dataLog(" Variable ", reg, " is expected to be dead.\n");
42984298
dataLog(" Result: ", liveAtHead, "\n");

‎Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -638,7 +638,7 @@ class ByteCodeParser {
638638
const FastBitVector& livenessAtBytecode = fullLiveness.getLiveness(bytecodeIndex);
639639

640640
for (unsigned local = codeBlock->m_numCalleeLocals; local--;) {
641-
if (livenessAtBytecode.get(local)) {
641+
if (livenessAtBytecode[local]) {
642642
VirtualRegister reg = virtualRegisterForLocal(local);
643643
if (inlineCallFrame)
644644
reg = inlineStackEntry->remapOperand(reg);

‎Source/JavaScriptCore/dfg/DFGForAllKills.h‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -76,8 +76,11 @@ void forAllKilledOperands(Graph& graph, Node* nodeBefore, Node* nodeAfter, const
7676
const FastBitVector& liveBefore = fullLiveness.getLiveness(before.bytecodeIndex);
7777
const FastBitVector& liveAfter = fullLiveness.getLiveness(after.bytecodeIndex);
7878

79+
// FIXME: Consider doing this instead:
80+
// (liveBefore & ~liveAfter).forEachSetBit(...)
81+
// https://bugs.webkit.org/show_bug.cgi?id=161849
7982
for (unsigned relativeLocal = codeBlock->m_numCalleeLocals; relativeLocal--;) {
80-
if (liveBefore.get(relativeLocal) && !liveAfter.get(relativeLocal))
83+
if (liveBefore[relativeLocal] && !liveAfter[relativeLocal])
8184
functor(virtualRegisterForLocal(relativeLocal) + stackOffset);
8285
}
8386

‎Source/JavaScriptCore/dfg/DFGGraph.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -745,7 +745,7 @@ class Graph : public virtual Scannable {
745745
if (reg >= exclusionStart && reg < exclusionEnd)
746746
continue;
747747

748-
if (liveness.get(relativeLocal))
748+
if (liveness[relativeLocal])
749749
functor(reg);
750750
}
751751

‎Source/JavaScriptCore/dfg/DFGLiveCatchVariablePreservationPhase.cpp‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
/*
2-
* Copyright (C) 2015 Apple Inc. All rights reserved.
2+
* Copyright (C) 2015-2016 Apple Inc. All rights reserved.
33
*
44
* Redistribution and use in source and binary forms, with or without
55
* modification, are permitted provided that the following conditions
@@ -73,7 +73,7 @@ class LiveCatchVariablePreservationPhase : public Phase {
7373
if (HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeIndexToCheck)) {
7474
unsigned catchBytecodeIndex = handler->target;
7575
m_graph.forAllLocalsLiveInBytecode(CodeOrigin(catchBytecodeIndex, inlineCallFrame), [&] (VirtualRegister operand) {
76-
m_currentBlockLiveness.set(operand.toLocal(), true);
76+
m_currentBlockLiveness[operand.toLocal()] = true;
7777
});
7878
return true;
7979
}
@@ -110,7 +110,7 @@ class LiveCatchVariablePreservationPhase : public Phase {
110110
VirtualRegister operand = node->local();
111111

112112
int stackOffset = inlineCallFrame ? inlineCallFrame->stackOffset : 0;
113-
if ((operand.isLocal() && m_currentBlockLiveness.get(operand.toLocal()))
113+
if ((operand.isLocal() && m_currentBlockLiveness[operand.toLocal()])
114114
|| (operand.offset() == stackOffset + CallFrame::thisArgumentOffset())) {
115115

116116
VariableAccessData* variableAccessData = currentBlockAccessData.operand(operand);
@@ -131,7 +131,7 @@ class LiveCatchVariablePreservationPhase : public Phase {
131131
{
132132
NodeOrigin origin = block->at(block->size() - 1)->origin;
133133
auto preserveLivenessAtEndOfBlock = [&] (VirtualRegister operand, bool alwaysInsert) {
134-
if ((operand.isLocal() && m_currentBlockLiveness.get(operand.toLocal()))
134+
if ((operand.isLocal() && m_currentBlockLiveness[operand.toLocal()])
135135
|| operand.isArgument()
136136
|| alwaysInsert) {
137137
VariableAccessData* accessData = currentBlockAccessData.operand(operand);

‎Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -105,7 +105,7 @@ NaturalLoops::NaturalLoops(Graph& graph)
105105
dataLog("Dealing with loop ", loop, "\n");
106106

107107
for (unsigned j = loop.size(); j--;) {
108-
seenBlocks.set(loop[j]->index);
108+
seenBlocks[loop[j]->index] = true;
109109
blockWorklist.append(loop[j]);
110110
}
111111

@@ -120,12 +120,12 @@ NaturalLoops::NaturalLoops(Graph& graph)
120120

121121
for (unsigned j = block->predecessors.size(); j--;) {
122122
BasicBlock* predecessor = block->predecessors[j];
123-
if (seenBlocks.get(predecessor->index))
123+
if (seenBlocks[predecessor->index])
124124
continue;
125125

126126
loop.addBlock(predecessor);
127127
blockWorklist.append(predecessor);
128-
seenBlocks.set(predecessor->index);
128+
seenBlocks[predecessor->index] = true;
129129
}
130130
}
131131
}

‎Source/JavaScriptCore/dfg/DFGPlan.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -691,7 +691,7 @@ void Plan::cleanMustHandleValuesIfNecessary()
691691
FastBitVector liveness = codeBlock->alternative()->livenessAnalysis().getLivenessInfoAtBytecodeOffset(osrEntryBytecodeIndex);
692692

693693
for (unsigned local = mustHandleValues.numberOfLocals(); local--;) {
694-
if (!liveness.get(local))
694+
if (!liveness[local])
695695
mustHandleValues.local(local) = jsUndefined();
696696
}
697697
}

0 commit comments

Comments
 (0)