Title: [250107] trunk/Source/_javascript_Core
- Revision
- 250107
- Author
- mark....@apple.com
- Date
- 2019-09-19 15:23:50 -0700 (Thu, 19 Sep 2019)
Log Message
Reduce the number of required tag bits for the JSValue.
https://bugs.webkit.org/show_bug.cgi?id=201990
Reviewed by Yusuke Suzuki.
We're reducing the number of tag bits to 15. It should just work.
How did we arrive at 15 bits?
============================
Currently, the minimum number of top bits used by doubles is 13-bits. The
highest double bit encoding are:
"negative" pureNaN: starts with 0xfff8
negative infinity: starts with 0xfff0
highest number: starts with 0xffe*
lowest number: starts with 0x0000
Requirements:
1. We need tags for 2 range of numbers: pointers (all 0s at the top), and ints
(all 1s at the top).
2. We want to be able to add an offset to double bits and ensure that they never
end up in the ranges for pointers and ints.
3. The int tag must be higher than whatever value is produced in the top bits
when boxing a double. We have code that relies on this relationship being
true and checks if a JSValue is an int by checking if the tag bits are above
or equal to the int tag.
4. We don't want to burn more than 2 CPU registers for tag / mask registers.
Based on the bit encoding of doubles, the full number range of the top 13 bits
are used in valid double numbers. This means the minimum tag bits must be greater
than 13.
Consider a 14-bit tag. The DoubleEncodeOffset will be 1 << 50 i.e. starts with
0x0004. With this encoding,
"negative" pureNaN: maps to 0xfff8 + 0x0004 => 0xfffc
i.e. the top 14 bits are all set. This conflicts with the int number range.
Next, consider a 15-bit tag. The DoubleEncodeOffset will be 1 << 49 i.e. starts
with 0x0002. With this encoding:
"negative" pureNaN: maps to 0xfff8 + 0x0002 => 0xfffa
negative infinity: maps to 0xfff0 + 0x0002 => 0xfff2
i.e. 0xfffe (top 5 bits set) is available to represent ints. This is the encoding
that we'll adopt in this patch.
Alternate encodings schemes to consider in the future:
=====================================================
1. If we're willing and able to purifyNaN at all the places that can produce a
"negative" pureNaN, e.g. after a division, then we can remove the "negative"
pureNaN as a valid double bit encoding. With this, we can now box doubles
with just a 14-bit tag, and DoubleEncodeOffset will be 1 << 50 i.e. starts with
0x0004.
With this encoding, the top double, negative infinity, is encoded as follows:
negative infinity: maps to 0xfff0 + 0x0004 => 0xfff4
i.e. leaving 0xfffc as the tag for ints.
We didn't adopt this scheme at this time because it adds complexity, and may
have performance impact from the extra purifyNaN checks.
Ref: https://bugs.webkit.org/show_bug.cgi?id=202002
2. If we're willing to use 3 tag registers or always materialize one of them, we
can also adopt a 14-bit tag as follows:
Pointer { 0000:PPPP:PPPP:PPPP
/ 0002:****:****:****
Double { ...
\ FFFC:****:****:****
Integer { FFFF:0000:IIII:IIII
where ...
NumberMask is 0xfffc: any bits set in the top 14 bits is a number.
IntMask is 0xffff: value is int if value & IntMask == IntMask.
NotCellMask is NumberMask | OtherTag.
Since the highest double is "negative" pureNaN i.e. starts with 0xfff8, adding
a DoubleEncodeOffset of 1<<50 (starts with 0x0004) produces 0xfffc which is
still less than 0xffff.
We didn't adopt this scheme at this time because it adds complexity and may
have a performance impact from either burning another register, or materializing
the 3rd mask.
Ref: https://bugs.webkit.org/show_bug.cgi?id=202005
* runtime/JSCJSValue.h:
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (250106 => 250107)
--- trunk/Source/_javascript_Core/ChangeLog 2019-09-19 21:46:03 UTC (rev 250106)
+++ trunk/Source/_javascript_Core/ChangeLog 2019-09-19 22:23:50 UTC (rev 250107)
@@ -1,5 +1,101 @@
2019-09-19 Mark Lam <mark....@apple.com>
+ Reduce the number of required tag bits for the JSValue.
+ https://bugs.webkit.org/show_bug.cgi?id=201990
+
+ Reviewed by Yusuke Suzuki.
+
+ We're reducing the number of tag bits to 15. It should just work.
+
+ How did we arrive at 15 bits?
+ ============================
+ Currently, the minimum number of top bits used by doubles is 13-bits. The
+ highest double bit encoding are:
+
+ "negative" pureNaN: starts with 0xfff8
+ negative infinity: starts with 0xfff0
+ highest number: starts with 0xffe*
+ lowest number: starts with 0x0000
+
+ Requirements:
+ 1. We need tags for 2 range of numbers: pointers (all 0s at the top), and ints
+ (all 1s at the top).
+
+ 2. We want to be able to add an offset to double bits and ensure that they never
+ end up in the ranges for pointers and ints.
+
+ 3. The int tag must be higher than whatever value is produced in the top bits
+ when boxing a double. We have code that relies on this relationship being
+ true and checks if a JSValue is an int by checking if the tag bits are above
+ or equal to the int tag.
+
+ 4. We don't want to burn more than 2 CPU registers for tag / mask registers.
+
+ Based on the bit encoding of doubles, the full number range of the top 13 bits
+ are used in valid double numbers. This means the minimum tag bits must be greater
+ than 13.
+
+ Consider a 14-bit tag. The DoubleEncodeOffset will be 1 << 50 i.e. starts with
+ 0x0004. With this encoding,
+ "negative" pureNaN: maps to 0xfff8 + 0x0004 => 0xfffc
+
+ i.e. the top 14 bits are all set. This conflicts with the int number range.
+
+ Next, consider a 15-bit tag. The DoubleEncodeOffset will be 1 << 49 i.e. starts
+ with 0x0002. With this encoding:
+ "negative" pureNaN: maps to 0xfff8 + 0x0002 => 0xfffa
+ negative infinity: maps to 0xfff0 + 0x0002 => 0xfff2
+
+ i.e. 0xfffe (top 5 bits set) is available to represent ints. This is the encoding
+ that we'll adopt in this patch.
+
+ Alternate encodings schemes to consider in the future:
+ =====================================================
+ 1. If we're willing and able to purifyNaN at all the places that can produce a
+ "negative" pureNaN, e.g. after a division, then we can remove the "negative"
+ pureNaN as a valid double bit encoding. With this, we can now box doubles
+ with just a 14-bit tag, and DoubleEncodeOffset will be 1 << 50 i.e. starts with
+ 0x0004.
+
+ With this encoding, the top double, negative infinity, is encoded as follows:
+
+ negative infinity: maps to 0xfff0 + 0x0004 => 0xfff4
+
+ i.e. leaving 0xfffc as the tag for ints.
+
+ We didn't adopt this scheme at this time because it adds complexity, and may
+ have performance impact from the extra purifyNaN checks.
+
+ Ref: https://bugs.webkit.org/show_bug.cgi?id=202002
+
+ 2. If we're willing to use 3 tag registers or always materialize one of them, we
+ can also adopt a 14-bit tag as follows:
+
+ Pointer { 0000:PPPP:PPPP:PPPP
+ / 0002:****:****:****
+ Double { ...
+ \ FFFC:****:****:****
+ Integer { FFFF:0000:IIII:IIII
+
+ where ...
+ NumberMask is 0xfffc: any bits set in the top 14 bits is a number.
+ IntMask is 0xffff: value is int if value & IntMask == IntMask.
+ NotCellMask is NumberMask | OtherTag.
+
+ Since the highest double is "negative" pureNaN i.e. starts with 0xfff8, adding
+ a DoubleEncodeOffset of 1<<50 (starts with 0x0004) produces 0xfffc which is
+ still less than 0xffff.
+
+ We didn't adopt this scheme at this time because it adds complexity and may
+ have a performance impact from either burning another register, or materializing
+ the 3rd mask.
+
+ Ref: https://bugs.webkit.org/show_bug.cgi?id=202005
+
+ * runtime/JSCJSValue.h:
+
+2019-09-19 Mark Lam <mark....@apple.com>
+
Refactoring: fix broken indentation in JSNonDestructibleProxy.h.
https://bugs.webkit.org/show_bug.cgi?id=201989
Modified: trunk/Source/_javascript_Core/runtime/JSCJSValue.h (250106 => 250107)
--- trunk/Source/_javascript_Core/runtime/JSCJSValue.h 2019-09-19 21:46:03 UTC (rev 250106)
+++ trunk/Source/_javascript_Core/runtime/JSCJSValue.h 2019-09-19 22:23:50 UTC (rev 250107)
@@ -381,25 +381,25 @@
* ranges to encode other values (however there are also other ranges of NaN space that
* could have been selected).
*
- * This range of NaN space is represented by 64-bit numbers begining with the 16-bit
- * hex patterns 0xFFFE and 0xFFFF - we rely on the fact that no valid double-precision
+ * This range of NaN space is represented by 64-bit numbers begining with the 15-bit
+ * hex patterns 0xFFFC and 0xFFFE - we rely on the fact that no valid double-precision
* numbers will fall in these ranges.
*
- * The top 16-bits denote the type of the encoded JSValue:
+ * The top 15-bits denote the type of the encoded JSValue:
*
* Pointer { 0000:PPPP:PPPP:PPPP
- * / 0001:****:****:****
+ * / 0002:****:****:****
* Double { ...
- * \ FFFE:****:****:****
- * Integer { FFFF:0000:IIII:IIII
+ * \ FFFC:****:****:****
+ * Integer { FFFE:0000:IIII:IIII
*
* The scheme we have implemented encodes double precision values by performing a
- * 64-bit integer addition of the value 2^48 to the number. After this manipulation
- * no encoded double-precision value will begin with the pattern 0x0000 or 0xFFFF.
+ * 64-bit integer addition of the value 2^49 to the number. After this manipulation
+ * no encoded double-precision value will begin with the pattern 0x0000 or 0xFFFE.
* Values must be decoded by reversing this operation before subsequent floating point
* operations may be peformed.
*
- * 32-bit signed integers are marked with the 16-bit tag 0xFFFF.
+ * 32-bit signed integers are marked with the 16-bit tag 0xFFFE.
*
* The tag 0x0000 denotes a pointer, or another form of tagged immediate. Boolean,
* null and undefined values are represented by specific, invalid pointer values:
@@ -419,15 +419,13 @@
* holes, and as a C++ 'no value' result (e.g. JSValue() has an internal value of 0).
*/
- // These values are #defines since using static const integers here is a ~1% regression!
-
- // This value is 2^48, used to encode doubles such that the encoded value will begin
- // with a 16-bit pattern within the range 0x0001..0xFFFE.
- static constexpr size_t DoubleEncodeOffsetBit = 48;
+ // This value is 2^49, used to encode doubles such that the encoded value will begin
+ // with a 15-bit pattern within the range 0x0002..0xFFFC.
+ static constexpr size_t DoubleEncodeOffsetBit = 49;
static constexpr int64_t DoubleEncodeOffset = 1ll << DoubleEncodeOffsetBit;
// If all bits in the mask are set, this indicates an integer number,
// if any but not all are set this value is a double precision number.
- static constexpr int64_t NumberTag = 0xffff000000000000ll;
+ static constexpr int64_t NumberTag = 0xfffe000000000000ll;
// All non-numeric (bool, null, undefined) immediates have bit 2 set.
static constexpr int32_t OtherTag = 0x2;
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
