Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 126d2027f1ce6c13bd147e6307b7edb1b821599e
https://github.com/WebKit/WebKit/commit/126d2027f1ce6c13bd147e6307b7edb1b821599e
Author: Mark Lam <[email protected]>
Date: 2024-01-19 (Fri, 19 Jan 2024)
Changed paths:
M JSTests/wasm/references/externref_table.js
M JSTests/wasm/references/func_ref.js
M JSTests/wasm/references/multitable.js
M JSTests/wasm/references/table_misc.js
M JSTests/wasm/regress/unmatched-else.js
M Source/JavaScriptCore/CMakeLists.txt
M Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
M Source/JavaScriptCore/Sources.txt
M Source/JavaScriptCore/bytecode/BytecodeRewriter.h
M Source/JavaScriptCore/bytecode/CodeBlock.cpp
M Source/JavaScriptCore/bytecode/CodeBlock.h
A Source/JavaScriptCore/bytecode/ExpressionInfo.cpp
A Source/JavaScriptCore/bytecode/ExpressionInfo.h
A Source/JavaScriptCore/bytecode/ExpressionInfoInlines.h
R Source/JavaScriptCore/bytecode/ExpressionRangeInfo.h
M Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp
M Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h
M Source/JavaScriptCore/bytecode/UnlinkedCodeBlockGenerator.cpp
M Source/JavaScriptCore/bytecode/UnlinkedCodeBlockGenerator.h
M Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h
M Source/JavaScriptCore/runtime/CachedTypes.cpp
M Source/JavaScriptCore/runtime/ErrorInstance.cpp
M Source/JavaScriptCore/runtime/FileBasedFuzzerAgent.cpp
M Source/JavaScriptCore/runtime/FileBasedFuzzerAgentBase.cpp
M Source/JavaScriptCore/runtime/FileBasedFuzzerAgentBase.h
M Source/JavaScriptCore/runtime/SamplingProfiler.cpp
M Source/WTF/wtf/HashMap.h
M Source/WTF/wtf/HashTable.h
Log Message:
-----------
Introduce ExpressionInfo as a replacement for ExpressionRangeInfo.
https://bugs.webkit.org/show_bug.cgi?id=260324
rdar://problem/114357179
Reviewed by Justin Michaud.
Previously, ExpressionRangeInfo takes 24 bytes for every entry, plus
potentially a FatPosition
entry for large line and column values. It would also just clear divot and its
start and end
offsets to 0 if they are too large.
The new ExpressionInfo compresses most expression info into just 4 bytes, with
occasional
exceptions. I estimate that this change may yield a 0.4% improvement on
Membuster.
Here's how ExpressionInfo works (from a comment in ExpressionInfo.cpp):
Since ExpressionInfo is only used to get source position info (e.g. line
and column)
for error messages / stacks and debugging, it need not be fast. However,
empirical data
shows that there is a lot of it on websites that are especially memory
hungry. So, it
behooves us to reduce this memory burden.
ExpressionInfo is a data structure that contains:
a. EncodedInfo entries.
This is where the expression info data is really stored.
b. Chapter marks in the list of EncodedInfo entries.
This is just an optimization aid to speed up reconstruction of
expression info
from the EncodedInfo.
c. A LineColumnMap cache.
This is to speed up look up of LineColumn values we have looked up
before.
Encoding of EncodedInfo words
=============================
Extension: [ 11111b | 1b | offset:26 ]
AbsInstPC: [ 11111b | 0b | value:26 ]
MultiWide: [ 11110b | 1b | 111b | numFields:5 | fields[6]:18
] [ value:32 ] ...
DuoWide: [ 11110b | 1b | field2:3 | value2:10 | field1:3 | value1:10 ]
SingleWide: [ 11110b | 0b | field:3 | value:23 ]
ExtensionEnd: [ 11110b | 0b | 111b | 0:23 ]
Basic: [ instPC:5 | divot:7 | start:6 | end:6 | line:3 | column:5 ]
Details of what these encodings are used for follows.
EncodedInfo
===========
Abstractly, each expression info defines 6 fields of unsigned type:
1. InstPC: bytecodeIndex offset.
2. Divot: the execution point in an expression.
3. Start: the offset from the Divot to the start of the expression.
4. End: the offset from the Divot to the end of the expression.
5. Line: the line number at the Divot.
6. Column: the column number at the Divot.
Let's call this an expression info entry, represented by
ExpressionInfo::Entry.
However, we know that the delta values of these fields between consecutive
entries tend to be
small. So, instead of encoding an Entry with 24 bytes, we aim to encode the
info in just 4 bytes
in an EncodedInfo word. See the encoding of the Basic word above.
UnlinkedCodeBlockGenerator::addExpressionInfo() triggers the addition of
EncodedInfo.
Each call of addExpressionInfo() may add 1 or more EncodedInfo. It can be
more than 1 because
the delta of some of the fields may exceed the capacity afforded them in
the Basic word.
To compensate for this, we introduce Wide Encodings of the EncodedInfo word.
Wide Encodings
==============
Wide Encodings specify additional delta to add to each field value. Wide
Encodings must
eventually be followed by a Basic word. The Basic word acts as the
terminator for each
expression info entry.
The 3 types of Wide Encodings are:
1. SingleWide: encodes a single field value with size singleValueBits
(currently 23) bits.
2. DuoWide: encodes 2 field values with size duoValueBits (currently 10)
bits each.
3. MultiWide: encodes up to 6 field values (because there are only 6 fields
in an expression
info record). The 1st word will be a header specifying the FieldIDs.
Subsequent words are
full 32-bit values for those respective fields.
Extension Encodings
===================
Some additional consideration: after
UnlinkedCodeBlockGenerator::addExpressionInfo() is done,
UnlinkedCodeBlockGenerator::applyModification() may insert, remove, add new
bytecode due to
generatorification. Hence, the InstPC the EncodedInfo defining each Entry
needs to be adjusted
accordingly. Similarly, we also need to adjust the Chapter marks in the
EncodedInfo.
Given that the EncodedInfo is a compressed form of the Entry fields, there
may or may not be
sufficient bits to encode the new InstPC. The straightforward
implementation would be to
insert some Wide Encodings to add additional delta for the InstPC. However,
this will result
in a lot of shifting of the EncodedInfo vector.
For simplicity and performance (given these adjustments are more rare),
rather than actually
inserting additional EncodedInfo, we do an inplace replacement of the first
EncodedInfo for the
Entry with an Extension (see encodings above) with an offset to an
extension section in the
EncodedInfo vector (pass the end of the normal non-Extension info). This
effectively behaves
like a call to an extension routine to apply some additional EncodedInfo to
adjust the InstPC
as needed.
The original first EncodedInfo for the Entry will be copied over as the
first EncodedInfo in
the extension section. The only exception to this is when the first
EncodedInfo is a Basic
word. By definition, the Basic word is the terminator i.e. it must be the
last EncodedInfo in
the sequence for each Entry.
To terminate the extension island, we introduce an ExtensionEnd word that
tells the decoder
to resume decoding in the original EncodedInfo stream (effectively a return
operation).
This is needed if the replaced word is not a Basic word (which again is the
terminator).
If the replaced word is the Basic word, then we don't need to append an
ExtensionEnd at the
end of the extension and will execute the "return" operation.
Miscellaneous details:
1. Currently, the code expects that Extensions cannot be nested. There is
no need to nest,
and there are ASSERTs in the decoder to check for this. However, if we
find a need in the
future, this can certainly be changed.
2. The inplace replacement works on the assumption that we can move a
"complete" EncodedInfo
over to the extension island. For all encodings, this is just a single
word. The only
exception is the MultiWide encoding, which are followed by N value
words. Because the
decoder expects these words to be contiguous, we move all the value
words over too. The
slots of the original value words will not be replaced by no-ops
(SingleWide with 0).
AbsInstPC and Chapters
======================
One downside of this compressed encoding scheme is that every time we need
the Entry value
for a given InstPC, we need to decode from the start of the EncodedInfo
vector to compute the
cummulative value of all the deltas up to the Entry of interest. This can
be slow if the
EncodedInfo vector is large.
To mitigate against this, we break the EncodedInfo regions into Chapters
every
numberOfWordsBetweenChapters (currently 10000) words or so. A Chapter is
always started
with an AbsInstPC (Absolute Instruction PC) word. Unlike other EncodedInfo
words with defines
delta values for fields to add, AbsInstPC defines an absolute value
(currently 26 bits) for
the InstPC to mark the start of the Chapter. If 26-bits isn't enough, we
can always add
SingleWide or MultiWide words to make up the difference of the InstPC for
this Entry.
Apart from resetting the cummulative InstPC to this new value, AbsInstPC
also implicitly
clears to 0 the cummulative delta for all the other fields. As a result, we
can always jump
to the start of a Chapter and start decoding from there (instead of
starting from the start
of the EncodedInfo vector). It limits the number of words that we need to
decode to around
numberOfWordsBetweenChapters.
Now, all we need to know is which Chapter a given InstPC falls into.
Finding Chapters
================
For this, we have a vector of Chapter info, where each Chapter defines its
starting InstPC
and the EncodedInfo word index for the start of the first encoded Entry in
that Chapter.
The first Chapter always starts at InstPC 0 and EncodedInfo index 0. Hence,
we do not emit
a Chapter entry for the 1st Chapter. Hence, for most small functions that
do not have
more than numberOfWordsBetweenChapters EncodedInfo, there is no Chapter
info in the
ExpressionInfo.
Additional Compression Details (of Basic word fields)
=====================================================
1. Column Reset on Line change
When Line changes from the last Entry, we always reset the cummulative
Column to 0. This makes
sense because Column is relative to the start of the Line. Without this
reset, the delta for
Column may be some huge negative value (which hurts compression).
2. Column same as Divot
Column often has the same value as Divot. This is because a lot of websites
use compacted
and obfuscated JS code in a single line. Therefore, the column position is
exactly the Divot
position. So, the Basic word reserves the value sameAsDivotValue (currently
0b1111) as an
indicator that the Column delta to apply is same as the Divot delta for
this Entry. This
reduces the number of Wide values we need to encode both if the Divot is
large.
3. Biased fields
Divot, Line, and Column deltas are signed ints, not unsigned. This is
because the evaluation
of an expression isn't in sequential order. For example, consider this
expression:
foo(bar())
^ ^-------- Divot, Line, and Column for bar()
`------------ Divot, Line, and Column for foo()
The order of evaluation is first to evaluate the call to bar() followed by
the call to foo().
As a result, the Divot delta for the call to foo() is a negative value
relative to the Divot
for the call to bar(). Similarly, this is true for Line and Column.
Since the delta values for these 3 fields are signed, instead of storing an
unsigned value at
their bitfield positions in the Basic word, we store a biased value: Divot
+ divotBias,
Line + lineBias, and Column + columnBias. This maps the values into an
unsigned, and makes it
easy to do a bounds check against the max capacity of the bitfield.
Similarly, ExpressionInfo::Diff which is used to track the delta for each
field has signed int
for these fields. This is in contrast to Entry and LineColumn where these
fields are stored
as unsigned.
Backing Store and Shape
=======================
The ExpressionInfo and its backing store (with the exception of the
contents of the
LineColumnMap cache) is allocated as a contiguous slab. We first compute
the size of the slab,
then allocate it, and lastly use placement new to instantiate the
ExpressionInfo.
The shape of ExpressionInfo looks like this:
ExpressionInfo: [ m_cachedLineColumns ]
[ m_numberOfChapters ]
[ m_numberOfEncodedInfo ]
[ m_numberOfEncodedInfoExtensions ]
Chapters Start: [ chapters()[0] ]
...
[ chapters()[m_numberOfChapters - 1] ]
EncodedInfo Start: [ encodedInfo()[0] ]
...
[ encodedInfo()[m_numberOfEncodedInfo - 1] ]
Extensions Start: [ encodedInfo()[m_numberOfEncodedInfo] ]
...
[ encodedInfo()[m_numberOfEncodedInfo +
m_numberOfEncodedInfoExtensions - 1] ]
Extensions End:
* JSTests/wasm/references/externref_table.js:
* JSTests/wasm/references/func_ref.js:
(string_appeared_here.End.End.Function.End.Code.End.WebAssembly.imp.ref):
(string_appeared_here.End.End.Function.End.Code.End.WebAssembly):
* JSTests/wasm/references/multitable.js:
* JSTests/wasm/references/table_misc.js:
(GetLocal.0.GetLocal.1.TableGrow.0.End.End.WebAssembly):
* JSTests/wasm/regress/unmatched-else.js:
(catch):
* Source/JavaScriptCore/CMakeLists.txt:
* Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:
* Source/JavaScriptCore/Sources.txt:
* Source/JavaScriptCore/bytecode/BytecodeRewriter.h:
(JSC::BytecodeRewriter::forEachLabelPoint):
* Source/JavaScriptCore/bytecode/CodeBlock.cpp:
(JSC::CodeBlock::expressionInfoForBytecodeIndex const):
(JSC::CodeBlock::expressionRangeForBytecodeIndex const): Deleted.
* Source/JavaScriptCore/bytecode/CodeBlock.h:
* Source/JavaScriptCore/bytecode/ExpressionInfo.cpp: Added.
(JSC::ExpressionInfo::Diff::set):
(JSC::ExpressionInfo::Diff::reset):
(JSC::ExpressionInfo::EncodedInfo::isAbsInstPC const):
(JSC::ExpressionInfo::EncodedInfo::isExtension const):
(JSC::ExpressionInfo::Encoder::encodeAbsInstPC):
(JSC::ExpressionInfo::Encoder::encodeExtension):
(JSC::ExpressionInfo::Encoder::encodeExtensionEnd):
(JSC::ExpressionInfo::Encoder::encodeSingle):
(JSC::ExpressionInfo::Encoder::encodeDuo):
(JSC::ExpressionInfo::Encoder::encodeMultiHeader):
(JSC::ExpressionInfo::Encoder::encodeBasic):
(JSC::ExpressionInfo::Encoder::adjustInstPC):
(JSC::ExpressionInfo::Encoder::encode):
(JSC::ExpressionInfo::Encoder::fits):
(JSC::ExpressionInfo::Encoder::createExpressionInfo):
(JSC::ExpressionInfo::Decoder::Decoder):
(JSC::ExpressionInfo::Decoder::recacheInfo):
(JSC::ExpressionInfo::cast):
(JSC::ExpressionInfo::isSpecial):
(JSC::ExpressionInfo::isWideOrSpecial):
(JSC::ExpressionInfo::Decoder::decode):
(JSC::ExpressionInfo::createUninitialized):
(JSC::ExpressionInfo::ExpressionInfo):
(JSC::ExpressionInfo::byteSize const):
(JSC::ExpressionInfo::lineColumnForInstPC):
(JSC::ExpressionInfo::findChapterEncodedInfoJustBelow const):
(JSC::ExpressionInfo::entryForInstPC):
(JSC::ExpressionInfo::print):
(JSC::ExpressionInfo::dumpEncodedInfo):
(WTF::printInternal):
* Source/JavaScriptCore/bytecode/ExpressionInfo.h: Added.
(JSC::ExpressionInfo::Entry::reset):
(JSC::ExpressionInfo::Encoder::entry const):
(JSC::ExpressionInfo::Encoder::dumpEncodedInfo):
(JSC::ExpressionInfo::Decoder::currentInfo const):
(JSC::ExpressionInfo::Decoder::setNextInfo):
(JSC::ExpressionInfo::Decoder::entry const):
(JSC::ExpressionInfo::Decoder::setEntry):
(JSC::ExpressionInfo::Decoder::instPC const):
(JSC::ExpressionInfo::Decoder::divot const):
(JSC::ExpressionInfo::Decoder::startOffset const):
(JSC::ExpressionInfo::Decoder::endOffset const):
(JSC::ExpressionInfo::Decoder::lineColumn const):
(JSC::ExpressionInfo::Decoder::appendWide):
(JSC::ExpressionInfo::isEmpty const):
(JSC::ExpressionInfo::payloadSizeInBytes):
(JSC::ExpressionInfo::totalSizeInBytes):
(JSC::ExpressionInfo::chapters const):
(JSC::ExpressionInfo::encodedInfo const):
(JSC::ExpressionInfo::endEncodedInfo const):
(JSC::ExpressionInfo::endExtensionEncodedInfo const):
(JSC::ExpressionInfo::payloadSize const):
(JSC::ExpressionInfo::payload const):
* Source/JavaScriptCore/bytecode/ExpressionInfoInlines.h: Added.
(JSC::ExpressionInfo::Encoder::remap):
* Source/JavaScriptCore/bytecode/ExpressionRangeInfo.h: Removed.
* Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp:
(JSC::UnlinkedCodeBlock::visitChildrenImpl):
(JSC::UnlinkedCodeBlock::RareData::sizeInBytes const):
(JSC::UnlinkedCodeBlock::lineColumnForBytecodeIndex):
(JSC::UnlinkedCodeBlock::expressionInfoForBytecodeIndex):
(JSC::dumpExpressionInfoDetails):
(JSC::UnlinkedCodeBlock::dumpExpressionInfo):
(JSC::UnlinkedCodeBlock::getLineAndColumn const): Deleted.
(JSC::dumpLineColumnEntry): Deleted.
(JSC::UnlinkedCodeBlock::dumpExpressionRangeInfo): Deleted.
(JSC::UnlinkedCodeBlock::expressionRangeForBytecodeIndex const): Deleted.
* Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h:
(JSC::UnlinkedCodeBlock::hasExpressionInfo):
(JSC::UnlinkedCodeBlock::expressionInfo): Deleted.
* Source/JavaScriptCore/bytecode/UnlinkedCodeBlockGenerator.cpp:
(JSC::UnlinkedCodeBlockGenerator::addExpressionInfo):
(JSC::UnlinkedCodeBlockGenerator::finalize):
(JSC::UnlinkedCodeBlockGenerator::applyModification):
* Source/JavaScriptCore/bytecode/UnlinkedCodeBlockGenerator.h:
* Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h:
* Source/JavaScriptCore/runtime/CachedTypes.cpp:
(JSC::CachedArray::encode):
(JSC::CachedArray::decode const):
(JSC::CachedCodeBlockRareData::encode):
(JSC::CachedCodeBlockRareData::decode const):
(JSC::CachedExpressionInfo::encode):
(JSC::CachedExpressionInfo::decode const):
(JSC::CachedCodeBlock<CodeBlockType>::decode const):
(JSC::CachedCodeBlock<CodeBlockType>::encode):
* Source/JavaScriptCore/runtime/ErrorInstance.cpp:
(JSC::appendSourceToErrorMessage):
* Source/JavaScriptCore/runtime/FileBasedFuzzerAgent.cpp:
(JSC::FileBasedFuzzerAgent::getPredictionInternal):
* Source/JavaScriptCore/runtime/FileBasedFuzzerAgentBase.cpp:
(JSC::FileBasedFuzzerAgentBase::getPrediction):
* Source/JavaScriptCore/runtime/FileBasedFuzzerAgentBase.h:
* Source/JavaScriptCore/runtime/SamplingProfiler.cpp:
(JSC::SamplingProfiler::processUnverifiedStackTraces):
* Source/WTF/wtf/HashMap.h:
(WTF::Y>::byteSize const):
* Source/WTF/wtf/HashTable.h:
(WTF::HashTable::byteSize const):
Canonical link: https://commits.webkit.org/273233@main
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
