915846 - Range Analysis API changes

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Dan Gohman [:sunfish]]

Inspired by bug 910807, bug 909528, and others, I developed a series of range-analysis API patches. I'm submitting them in a new bug report to make it easier to consider altogether.

The overall goal here is to make key concepts in the range-analysis API more precise and more explicit.

Comment 1

[Dan Gohman [:sunfish]]

Attachment: range-consts.patch

Comment 2

[Dan Gohman [:sunfish]]

Attachment: range-tidy.patch

Comment 3

[Dan Gohman [:sunfish]]

Attachment: range-eliminate-bounds-check-upper.patch

Comment 4

[Dan Gohman [:sunfish]]

Attachment: range-fractional.patch

Comment 5

[Dan Gohman [:sunfish]]

Attachment: range-unbounded.patch

Comment 6

[Dan Gohman [:sunfish]]

Attachment: range-is-fully-bounded.patch

Comment 7

[Dan Gohman [:sunfish]]

Attachment: range-more-renames.patch

Comment 8

[Dan Gohman [:sunfish]]

Attachment: range-factories.patch

Comment 9

[Dan Gohman [:sunfish]]

Attachment: range-infinity-and-nan.patch

Comment 10

[Dan Gohman [:sunfish]]

Attachment: range-private-members.patch

Comment 11

[Dan Gohman [:sunfish]]

Attachment: range-helper-predicates.patch

Comment 12

[Dan Gohman [:sunfish]]

Attachment: range-use-accessors.patch

Comment 13

[Dan Gohman [:sunfish]]

Attachment: range-int32-arithmetic.patch

Comment 14

[Dan Gohman [:sunfish]]

Attachment: range-set.patch

Comment 15

[Dan Gohman [:sunfish]]

Attachment: range-doubles.patch

Comment 16

[Dan Gohman [:sunfish]]

Attachment: range-check-beta.patch

Comment 17

[Dan Gohman [:sunfish]]

Attachment: range-assert-type.patch

Comment 18

[Dan Gohman [:sunfish]]

Attachment: range-assert-invariants.patch

Comment 19

[Dan Gohman [:sunfish]]

Attachment: range-spew.patch

Comment 20

[Dan Gohman [:sunfish]]

Attachment: range-div.patch

Comment 21

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803936 [details] [diff] [review]
range-tidy.patch

Review of attachment 803936 [details] [diff] [review]:
-----------------------------------------------------------------

Is there any link-time overhead at removing the inline keywords?

::: js/src/jit/RangeAnalysis.cpp
@@ +273,4 @@
>      if (decimal_)
>          sp.printf("R");
>      else
> +        sp.printf("I");

If you are using I, then you should also replace R by F, as N stand for Natural, and R for Real.

::: js/src/jit/RangeAnalysis.h
@@ +235,5 @@
>          lower_ = JSVAL_INT_MIN;
>          if (max_exponent_ < MaxInt32Exponent)
>              max_exponent_ = MaxInt32Exponent;
>      }
> +    void makeUpperInfinite() {

We still want these functions to be inlined. Removing the inline keyword means that we would have an extra link-time overhead, right?

Could we do as we usually do, i-e moving these functions into RangaAnalysis-inl.h, and only include it when necessary?
In fact most of these functions are only supposed to be used inside RangeAnalysis.cpp, and except for the predicates, I think we should move most of these inlined functions to the RangeAnalysis.cpp file.

Comment 22

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803938 [details] [diff] [review]
range-eliminate-bounds-check-upper.patch

Review of attachment 803938 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/MIR.cpp
@@ +2388,5 @@
>  
>  bool
>  MBoundsCheckLower::fallible()
>  {
> +    return !index()->range() || index()->range()->lower() < minimum_;

Use collectRangeInfo instead of reading the state out of one of the operands.

::: js/src/jit/RangeAnalysis.cpp
@@ +1503,1 @@
>                  block->insertBefore(block->lastIns(), def->toInstruction());

Move computeRange after insertBefore, such as the definition is checked when it is already attached to the MIRGraph.

Comment 24

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #21)
> Comment on attachment 803936 [details] [diff] [review]
> range-tidy.patch
> 
> Review of attachment 803936 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Is there any link-time overhead at removing the inline keywords?

For functions defined inside of class definitions, there's no difference. They're defined to have the inline property.

> ::: js/src/jit/RangeAnalysis.cpp
> @@ +273,4 @@
> >      if (decimal_)
> >          sp.printf("R");
> >      else
> > +        sp.printf("I");
> 
> If you are using I, then you should also replace R by F, as N stand for
> Natural, and R for Real.

Ok. I've made this change in my local tree.

> ::: js/src/jit/RangeAnalysis.h
> @@ +235,5 @@
> >          lower_ = JSVAL_INT_MIN;
> >          if (max_exponent_ < MaxInt32Exponent)
> >              max_exponent_ = MaxInt32Exponent;
> >      }
> > +    void makeUpperInfinite() {
> 
> We still want these functions to be inlined. Removing the inline keyword
> means that we would have an extra link-time overhead, right?

In the case of functions defined inside of class definitions, there's no difference. They're "inline" regardless of whether they have the keyword. I mainly made this change for consistency with what I see in most of the rest of the SpiderMonkey sources.

> Could we do as we usually do, i-e moving these functions into
> RangaAnalysis-inl.h, and only include it when necessary?
> In fact most of these functions are only supposed to be used inside
> RangeAnalysis.cpp, and except for the predicates, I think we should move
> most of these inlined functions to the RangeAnalysis.cpp file.

This doesn't seem warranted here, as there's no extra link-time overhead being introduced.

Comment 25

[Dan Gohman [:sunfish]]

Attachment: range-eliminate-bounds-check-upper.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #22)
> Comment on attachment 803938 [details] [diff] [review]
> range-eliminate-bounds-check-upper.patch
> 
> Review of attachment 803938 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/MIR.cpp
> @@ +2388,5 @@
> >  
> >  bool
> >  MBoundsCheckLower::fallible()
> >  {
> > +    return !index()->range() || index()->range()->lower() < minimum_;
> 
> Use collectRangeInfo instead of reading the state out of one of the operands.

Done.

> ::: js/src/jit/RangeAnalysis.cpp
> @@ +1503,1 @@
> >                  block->insertBefore(block->lastIns(), def->toInstruction());
> 
> Move computeRange after insertBefore, such as the definition is checked when
> it is already attached to the MIRGraph.

Done.

Comment 26

[Dan Gohman [:sunfish]]

range-consts.patch:     https://hg.mozilla.org/integration/mozilla-inbound/rev/709992264f64
range-fractional.patch: https://hg.mozilla.org/integration/mozilla-inbound/rev/54adcc76078b

Comment 27

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803940 [details] [diff] [review]
range-unbounded.patch

Review of attachment 803940 [details] [diff] [review]:
-----------------------------------------------------------------

Great! This is nicer than infinite :)

As you mentioned in your patch title, unbounded is not really the meaning here, since it is still bounded by the number of bits needed to represent the maximal value (max_exponent + 1).

The patch as it is is good land, but I will also suggest other names in case we find a better compromise:
 - boundByBits
 - outInt32Range
 - outIntRange
 - useExpRange

Comment 28

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803944 [details] [diff] [review]
range-more-renames.patch

Review of attachment 803944 [details] [diff] [review]:
-----------------------------------------------------------------

nit: Fix your patch subject: Raname -> Rename.

Comment 29

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803946 [details] [diff] [review]
range-factories.patch

Review of attachment 803946 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.h
@@ +230,5 @@
> +        return new Range(l, h, true, e);
> +    }
> +
> +    static Range *NewSingleValueRange(int64_t v) {
> +        return new Range(v, v, false, MaxDoubleExponent);

We should open a follow-up bug to add a rectify exponent which is taking doubles as arguments, and move the code from MConstant to it.  This way we could take double argument here and above and get a precise exponent range instead of using MaxDoubleExponent.

Comment 30

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803948 [details] [diff] [review]
range-infinity-and-nan.patch

Review of attachment 803948 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +300,5 @@
>      }
>  
>      sp.printf("]");
> +    if (max_exponent_ == IncludesInfinityAndNaN)
> +        sp.printf(" (includes inf and NaN)", max_exponent_);

These are too verbose for the graph produced by IonGraph.  Can we use "U Inf U NaN" or something similar?

@@ +302,5 @@
>      sp.printf("]");
> +    if (max_exponent_ == IncludesInfinityAndNaN)
> +        sp.printf(" (includes inf and NaN)", max_exponent_);
> +    else if (max_exponent_ == IncludesInfinity)
> +        sp.printf(" (includes inf)");

You want to use ">=" instead of "==", some operations range computation might compute the exponent without any care, and there is no need the exponent computation is monotonous.  See the other comment below about the value of IncludesInfinityAndNaN.

@@ +304,5 @@
> +        sp.printf(" (includes inf and NaN)", max_exponent_);
> +    else if (max_exponent_ == IncludesInfinity)
> +        sp.printf(" (includes inf)");
> +    else if (upper_unbounded_ || lower_unbounded_)
> +        sp.printf(" (<= MAXp+%d)", max_exponent_);

To be exact the max value is 2**(max_exp+1)-1

@@ +418,5 @@
> +    // The exponent is at most one greater than the greater of the operands'
> +    // exponents, except for NaN and infinity cases.
> +    uint16_t e = Max(lhs->max_exponent_, rhs->max_exponent_);
> +    if (e <= Range::MaxFiniteExponent)
> +        ++e;

if (e != IncludesInfinityAndNaN)
    ++e;

In fact, this is a clampUInt16.

::: js/src/jit/RangeAnalysis.h
@@ +118,5 @@
> +    static const uint16_t IncludesInfinity = MaxFiniteExponent + 1;
> +
> +    // An special exponent value representing all possible double-precision
> +    // values. This includes finite values, the infinities, and NaNs.
> +    static const uint16_t IncludesInfinityAndNaN = IncludesInfinity + 1;

Can we use UIN16_MAX instead of IncludesInfinity + 1?

This way we can still use monotonous functions to manipulate exponents as long as we are not manipulating NaNs the same way.

@@ +198,5 @@
>            symbolicLower_(NULL),
>            symbolicUpper_(NULL)
>      {
> +        JS_ASSERT(e >= (h == INT64_MIN ? IncludesInfinityAndNaN : mozilla::FloorLog2(mozilla::Abs(h))));
> +        JS_ASSERT(e >= (l == INT64_MIN ? IncludesInfinityAndNaN : mozilla::FloorLog2(mozilla::Abs(l))));

IncludesInfinityAndNaN --> IncludesInfinity

If we have a constant double, we a known exponent we do not want to assume that it can be a NaN.

@@ +238,1 @@
>          return new Range(l, h, true, e);

same thing.

@@ +238,5 @@
>          return new Range(l, h, true, e);
>      }
>  
>      static Range *NewSingleValueRange(int64_t v) {
> +        return new Range(v, v, false, IncludesInfinityAndNaN);

Same here.

Comment 31

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803949 [details] [diff] [review]
range-private-members.patch

Review of attachment 803949 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.h
@@ +181,5 @@
> +            lower_unbounded_ = false;
> +        } else if (x < JSVAL_INT_MIN) {
> +            makeLowerUnbounded();
> +        } else {
> +            lower_ = (int32_t)x;

nit: use a C++ cast here.

@@ +192,5 @@
> +        } else if (x < JSVAL_INT_MIN) {
> +            upper_ = JSVAL_INT_MIN;
> +            upper_unbounded_ = false;
> +        } else {
> +            upper_ = (int32_t)x;

nit: same here.

Comment 32

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803950 [details] [diff] [review]
range-helper-predicates.patch

Review of attachment 803950 [details] [diff] [review]:
-----------------------------------------------------------------

If the goal is to move lower and upper to be private functions, then yes, It would make sense to have accessors for canBeLessThan & isLowerInterestingInt32 & isUpperInterestingInt32.
In the mean time, I do not see the use of it and I can r+ the rest of the patch without these 3.

::: js/src/jit/CodeGenerator.cpp
@@ +7468,5 @@
>  
>      // This code does not yet check r->canHaveFractionalPart(). This would require new
>      // assembler interfaces to make rounding instructions available.
>  
> +    if (!r->isFullyBounded() && !r->canBeInfiniteOrNaN() && r->exponent() < DoubleExponentBias) {

!canBeInfiniteOrNaN is redundant with the next check.

::: js/src/jit/MIR.cpp
@@ +2388,5 @@
>  
>  bool
>  MBoundsCheckLower::fallible()
>  {
> +    return !index()->range() || index()->range()->canBeLessThan(minimum_);

nit: take care when rebasing this patch to move this to the computeRangeInfo function.

::: js/src/jit/RangeAnalysis.h
@@ +381,5 @@
> +
> +    // Test whether a value in this range can possibly be less than the
> +    // given value.
> +    bool canBeLessThan(int32_t n) const {
> +        return lower_ < n;

nit: Move this function before isLowerInterestingInt32, such as we can keep isFiniteNegtive closer to canBeFiniteNegative.

Comment 33

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803951 [details] [diff] [review]
range-use-accessors.patch

Review of attachment 803951 [details] [diff] [review]:
-----------------------------------------------------------------

Ok, the conversion made in this patch should be good as all the lower() & upper() are all guarded by isInt32 assertions before.

On the other hand the existing one such as lhs->lower() in Range::ursh[1] are likely to produce lots of false positive in fuzzers.
Fix this case, ask for review, and ask for feedback from one of the fuzzers.

[1] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/RangeAnalysis.cpp#l677

Comment 34

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803952 [details] [diff] [review]
range-int32-arithmetic.patch

Review of attachment 803952 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +504,5 @@
>          // Both operands are non-negative, so the result won't be less than either.
>          lower = Max(lhs->lower(), rhs->lower());
>          // The result will have leading zeros where both operands have leading zeros.
> +        upper = int32_t(UINT32_MAX >> Min(CountLeadingZeroes32(lhs->upper()),
> +                                          CountLeadingZeroes32(rhs->upper())));

nit: Add a comment that CountLeadingZeroes32 of a non-negative int32 will at least be 1 to account for the bit of sign.

Comment 35

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803953 [details] [diff] [review]
range-set.patch

Review of attachment 803953 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +877,5 @@
>          // encode any values with fractional parts.
>          if (IsNegative(d))
> +            setRange(Range::NewDoubleRange(Range::UnboundedLower,
> +                                           Range::UnboundedLower,
> +                                           Range::MaxFiniteExponent));

We just computed the exponent, why not reusing it instead of using MaxFiniteExponent?
Using MaxFiniteExponent will prevent doing any truncation on operations such as:

  (0x80000000 + (x |0)) | 0

@@ +1110,5 @@
>      int64_t lower = lhs.lower() >= 0 ? 0 : -absBound;
>      int64_t upper = lhs.upper() <= 0 ? 0 : absBound;
>  
> +    setRange(new Range(lower, upper, lhs.canHaveFractionalPart() || rhs.canHaveFractionalPart(),
> +                       Range::IncludesInfinityAndNaN));

Here the exponent is Min(lhs.max_exponent_, rhs.max_exponent_).

::: js/src/jit/RangeAnalysis.h
@@ +207,5 @@
> +    // values of lower() and upper().
> +    uint16_t impliedExponent() const {
> +         // The number of bits needed to encode |max| is the power of 2 plus one.
> +         uint32_t max = Max(mozilla::Abs(lower()), mozilla::Abs(upper()));
> +         return mozilla::FloorLog2(max);

FloorLog2 does not accept 0 as a valid input, which explained why we had "max ? log2(max) : max".

Please keep the comment about the returned value for Int32 min and int32 max, as this might be confusing.

@@ +214,5 @@
> +    // Set the max_exponent_ field by infering the value from lower(), upper(),
> +    // isLowerUnbounded(), and isUpperUnbounded(). This is used during
> +    // initialization, so it doesn't look at any other fields.
> +    void autoInitializeExponent() {
> +        max_exponent_ = isFullyBounded() ? impliedExponent() : IncludesInfinityAndNaN;

IncludesInfinityAndNaN is a terrible fallback!

We only want to rectify when we are fully bounded, otherwise we expect to have a **near** over approximation.  Such default is far from being **near** and this is not sane truncation logic.

@@ +443,5 @@
>      }
>  
>      void setLower(int64_t x) {
>          setLowerInit(x);
> +        autoInitializeExponent();

This is not a good solution, see comment on autoInitializeExponent.  I guess a better solution would be to provide the exponent as argument of setLower if we want to guarantee that the exponent is optimized.

@@ +448,5 @@
>          JS_ASSERT_IF(lower_unbounded_, lower_ == JSVAL_INT_MIN);
>      }
>      void setUpper(int64_t x) {
>          setUpperInit(x);
> +        autoInitializeExponent();

same here.

@@ +461,2 @@
>          canHaveFractionalPart_ = false;
> +        autoInitializeExponent();

nit: isFullyBounded() is always true here.

  max_exponent_ = impliedExponent();

Comment 36

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/709992264f64
https://hg.mozilla.org/mozilla-central/rev/54adcc76078b

Comment 37

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #27)
> The patch as it is is good land, but I will also suggest other names in case
> we find a better compromise:
>  - boundByBits
>  - outInt32Range
>  - outIntRange
>  - useExpRange

Hmm, how about hasInt32LowerBound, hasInt32UpperBound, and hasInt32LowerAndUpperBounds? It's verbose, but pretty unambiguous.

Comment 38

[Dan Gohman [:sunfish]]

range-tidy.patch:
  https://hg.mozilla.org/integration/mozilla-inbound/rev/e8f4ce1c8390
range-eliminate-bounds-check-upper.patch:
  https://hg.mozilla.org/integration/mozilla-inbound/rev/d00e40c657a1

Comment 39

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #37)
> (In reply to Nicolas B. Pierron [:nbp] from comment #27)
> >  - boundByBits
> >  - outInt32Range
> >  - outIntRange
> >  - useExpRange
> 
> Hmm, how about hasInt32LowerBound, hasInt32UpperBound, and
> hasInt32LowerAndUpperBounds? It's verbose, but pretty unambiguous.

Mentioning the range which is bounded is good, because unbounded int32 ranges are still bound by the max_exponent_.

Maybe hasInt32Bounds instead of hasInt32LowerAndUpperBounds (isUnbounded)?

Comment 40

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #39)
> Maybe hasInt32Bounds instead of hasInt32LowerAndUpperBounds (isUnbounded)?

That works for me.

range-unbounded.patch:
  https://hg.mozilla.org/integration/mozilla-inbound/rev/a3255cb88e5e
range-is-fully-bounded.patch:
  https://hg.mozilla.org/integration/mozilla-inbound/rev/6afebbb8e595
range-factories.patch:
  https://hg.mozilla.org/integration/mozilla-inbound/rev/99240d780042
range-private-members.patch:
  https://hg.mozilla.org/integration/mozilla-inbound/rev/644fe03f2bd4
range-more-renames.patch:
  https://hg.mozilla.org/integration/mozilla-inbound/rev/bbb3d10d2c1c

Comment 41

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #29)
> We should open a follow-up bug to add a rectify exponent which is taking
> doubles as arguments, and move the code from MConstant to it.  This way we
> could take double argument here and above and get a precise exponent range
> instead of using MaxDoubleExponent.

I filed bug 915846 for this.

Comment 42

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/e8f4ce1c8390
https://hg.mozilla.org/mozilla-central/rev/d00e40c657a1
https://hg.mozilla.org/mozilla-central/rev/a3255cb88e5e
https://hg.mozilla.org/mozilla-central/rev/6afebbb8e595
https://hg.mozilla.org/mozilla-central/rev/99240d780042
https://hg.mozilla.org/mozilla-central/rev/644fe03f2bd4
https://hg.mozilla.org/mozilla-central/rev/bbb3d10d2c1c

Comment 43

[Dan Gohman [:sunfish]]

Attachment: range-infinity-and-nan.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #30)
> Comment on attachment 803948 [details] [diff] [review]
> range-infinity-and-nan.patch
> 
> Review of attachment 803948 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +300,5 @@
> >      }
> >  
> >      sp.printf("]");
> > +    if (max_exponent_ == IncludesInfinityAndNaN)
> > +        sp.printf(" (includes inf and NaN)", max_exponent_);
> 
> These are too verbose for the graph produced by IonGraph.  Can we use "U Inf
> U NaN" or something similar?

Ok.

> @@ +302,5 @@
> >      sp.printf("]");
> > +    if (max_exponent_ == IncludesInfinityAndNaN)
> > +        sp.printf(" (includes inf and NaN)", max_exponent_);
> > +    else if (max_exponent_ == IncludesInfinity)
> > +        sp.printf(" (includes inf)");
> 
> You want to use ">=" instead of "==", some operations range computation
> might compute the exponent without any care, and there is no need the
> exponent computation is monotonous.  See the other comment below about the
> value of IncludesInfinityAndNaN.

The theory in this patch is that we no longer have Ranges with a max_exponent_ that is anything other than finite, IncludesInfinity, or IncludesInfinityAndNaN. In range-assert-invariants.patch, this invariant is consistently enforced.

> @@ +304,5 @@
> > +        sp.printf(" (includes inf and NaN)", max_exponent_);
> > +    else if (max_exponent_ == IncludesInfinity)
> > +        sp.printf(" (includes inf)");
> > +    else if (upper_unbounded_ || lower_unbounded_)
> > +        sp.printf(" (<= MAXp+%d)", max_exponent_);
> 
> To be exact the max value is 2**(max_exp+1)-1

Right. I used MAX to mean the maximum mantissa, and the "p+" is in the style of C99-style hex float syntax. It's saying that the value is at most the maximum mantissa times 2**max_exp, which I think is clear. Is this confusing?

> @@ +418,5 @@
> > +    // The exponent is at most one greater than the greater of the operands'
> > +    // exponents, except for NaN and infinity cases.
> > +    uint16_t e = Max(lhs->max_exponent_, rhs->max_exponent_);
> > +    if (e <= Range::MaxFiniteExponent)
> > +        ++e;
> 
> if (e != IncludesInfinityAndNaN)
>     ++e;

I think the code in the patch is right. An add never overflows into a NaN.

> In fact, this is a clampUInt16.

I'm not sure what you mean by this.

> ::: js/src/jit/RangeAnalysis.h
> @@ +118,5 @@
> > +    static const uint16_t IncludesInfinity = MaxFiniteExponent + 1;
> > +
> > +    // An special exponent value representing all possible double-precision
> > +    // values. This includes finite values, the infinities, and NaNs.
> > +    static const uint16_t IncludesInfinityAndNaN = IncludesInfinity + 1;
> 
> Can we use UIN16_MAX instead of IncludesInfinity + 1?
> 
> This way we can still use monotonous functions to manipulate exponents as
> long as we are not manipulating NaNs the same way.

Done. It'll still require care, but I do like how this lets us distinguish between an intentional NaN and simple overflow in a range computation in many cases.

> @@ +198,5 @@
> >            symbolicLower_(NULL),
> >            symbolicUpper_(NULL)
> >      {
> > +        JS_ASSERT(e >= (h == INT64_MIN ? IncludesInfinityAndNaN : mozilla::FloorLog2(mozilla::Abs(h))));
> > +        JS_ASSERT(e >= (l == INT64_MIN ? IncludesInfinityAndNaN : mozilla::FloorLog2(mozilla::Abs(l))));
> 
> IncludesInfinityAndNaN --> IncludesInfinity
> 
> If we have a constant double, we a known exponent we do not want to assume
> that it can be a NaN.

Fixed.

> @@ +238,1 @@
> >          return new Range(l, h, true, e);
> 
> same thing.
> 
> @@ +238,5 @@
> >          return new Range(l, h, true, e);
> >      }
> >  
> >      static Range *NewSingleValueRange(int64_t v) {
> > +        return new Range(v, v, false, IncludesInfinityAndNaN);
> 
> Same here.

These are actually due to a subtlety from the original code. Because these interfaces use int64_t, they can accept NoInt32UpperBound or NoInt32LowerBound, which can include NaN.

Comment 44

[Dan Gohman [:sunfish]]

Attachment: range-use-accessors.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #33)
> Comment on attachment 803951 [details] [diff] [review]
> range-use-accessors.patch
> 
> Review of attachment 803951 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Ok, the conversion made in this patch should be good as all the lower() &
> upper() are all guarded by isInt32 assertions before.
> 
> On the other hand the existing one such as lhs->lower() in Range::ursh[1]
> are likely to produce lots of false positive in fuzzers.
> Fix this case, ask for review, and ask for feedback from one of the fuzzers.

It looks like this can't come up in practice because ursh uses the BitwisePolicy and the TypeAnalyzer always casts its operands to int32 before range analysis sees them. Nevertheless, I added code to range analysis to wrap ursh's lhs range around to int32, for consistency with the other bitwise operators.

Comment 45

[Dan Gohman [:sunfish]]

Attachment: range-set.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #35)
> Comment on attachment 803953 [details] [diff] [review]
> range-set.patch
> 
> Review of attachment 803953 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +877,5 @@
> >          // encode any values with fractional parts.
> >          if (IsNegative(d))
> > +            setRange(Range::NewDoubleRange(Range::UnboundedLower,
> > +                                           Range::UnboundedLower,
> > +                                           Range::MaxFiniteExponent));
> 
> We just computed the exponent, why not reusing it instead of using
> MaxFiniteExponent?
> Using MaxFiniteExponent will prevent doing any truncation on operations such
> as:
> 
>   (0x80000000 + (x |0)) | 0

Good idea. Done.

> @@ +1110,5 @@
> >      int64_t lower = lhs.lower() >= 0 ? 0 : -absBound;
> >      int64_t upper = lhs.upper() <= 0 ? 0 : absBound;
> >  
> > +    setRange(new Range(lower, upper, lhs.canHaveFractionalPart() || rhs.canHaveFractionalPart(),
> > +                       Range::IncludesInfinityAndNaN));
> 
> Here the exponent is Min(lhs.max_exponent_, rhs.max_exponent_).

Makes sense. Done.

> ::: js/src/jit/RangeAnalysis.h
> @@ +207,5 @@
> > +    // values of lower() and upper().
> > +    uint16_t impliedExponent() const {
> > +         // The number of bits needed to encode |max| is the power of 2 plus one.
> > +         uint32_t max = Max(mozilla::Abs(lower()), mozilla::Abs(upper()));
> > +         return mozilla::FloorLog2(max);
> 
> FloorLog2 does not accept 0 as a valid input, which explained why we had
> "max ? log2(max) : max".

The current FloorLog2 is documented to accept 0.

> Please keep the comment about the returned value for Int32 min and int32
> max, as this might be confusing.

Ok, I re-added the comment (with corrected values).

> @@ +214,5 @@
> > +    // Set the max_exponent_ field by infering the value from lower(), upper(),
> > +    // isLowerUnbounded(), and isUpperUnbounded(). This is used during
> > +    // initialization, so it doesn't look at any other fields.
> > +    void autoInitializeExponent() {
> > +        max_exponent_ = isFullyBounded() ? impliedExponent() : IncludesInfinityAndNaN;
> 
> IncludesInfinityAndNaN is a terrible fallback!
> 
> We only want to rectify when we are fully bounded, otherwise we expect to
> have a **near** over approximation.  Such default is far from being **near**
> and this is not sane truncation logic.

Good point. I eliminated this function altogether, as it no longer makes sense.

> @@ +443,5 @@
> >      }
> >  
> >      void setLower(int64_t x) {
> >          setLowerInit(x);
> > +        autoInitializeExponent();
> 
> This is not a good solution, see comment on autoInitializeExponent.  I guess
> a better solution would be to provide the exponent as argument of setLower
> if we want to guarantee that the exponent is optimized.

Yeah. On further reflection, setLower and setUpper aren't really the right interface. I renamed them to refineLower and refineUpper, and updated their users accordingly. These new functions have a narrower purpose, so they don't have to be as conservative or as complex.

> @@ +448,5 @@
> >          JS_ASSERT_IF(lower_unbounded_, lower_ == JSVAL_INT_MIN);
> >      }
> >      void setUpper(int64_t x) {
> >          setUpperInit(x);
> > +        autoInitializeExponent();
> 
> same here.

Done.

> @@ +461,2 @@
> >          canHaveFractionalPart_ = false;
> > +        autoInitializeExponent();
> 
> nit: isFullyBounded() is always true here.
> 
>   max_exponent_ = impliedExponent();

Done.

Comment 46

[Nicolas B. Pierron [:nbp]]

Comment on attachment 808986 [details] [diff] [review]
range-infinity-and-nan.patch

Review of attachment 808986 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +304,5 @@
> +        sp.printf(" (U inf U NaN)", max_exponent_);
> +    else if (max_exponent_ == IncludesInfinity)
> +        sp.printf(" (U inf)");
> +    else if (!hasInt32UpperBound_ || !hasInt32LowerBound_)
> +        sp.printf(" (<= MAXp+%d)", max_exponent_);

I never saw the p notation before, and I think it might be easier to understand with a strict inequality:
 - sp.printf(" (< 0x1p+%d)", max_exponent_ + 1);
 - sp.printf(" (< 2**%d)", max_exponent_ + 1);

@@ +850,5 @@
>      if (type() != MIRType_Double)
>          return;
>  
>      double d = value().toDouble();
> +    int exp = Range::IncludesInfinityAndNaN;

nit:
 - use Range::IncludesInfinity;
 - and move this declaration below the check of IsNaN.

Comment 47

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #44)
> Created attachment 809126 [details] [diff] [review]
> range-use-accessors.patch
> 
> (In reply to Nicolas B. Pierron [:nbp] from comment #33)
> > Comment on attachment 803951 [details] [diff] [review]
> > range-use-accessors.patch
> > 
> > Review of attachment 803951 [details] [diff] [review]:
> > -----------------------------------------------------------------
> > 
> > Ok, the conversion made in this patch should be good as all the lower() &
> > upper() are all guarded by isInt32 assertions before.
> > 
> > On the other hand the existing one such as lhs->lower() in Range::ursh[1]
> > are likely to produce lots of false positive in fuzzers.
> > Fix this case, ask for review, and ask for feedback from one of the fuzzers.
> 
> It looks like this can't come up in practice because ursh uses the
> BitwisePolicy and the TypeAnalyzer always casts its operands to int32 before
> range analysis sees them. Nevertheless, I added code to range analysis to
> wrap ursh's lhs range around to int32, for consistency with the other
> bitwise operators.

This is the corner case of Ursh, it does not convert its input to an Int32 before doing the computation.  It is not a safe assumption to wrap around the lhs range to the range of an int32, as the exponent might be shifted by one.

I know that the bitwise policy enforce that we use an infallible truncateToInt32, but the ranges of the returned values are not the same, and this is only safe if the instruction is specialized as an Int32 instruction and we are not generating asmjs code.

Comment 48

[Nicolas B. Pierron [:nbp]]

Comment on attachment 809166 [details] [diff] [review]
range-set.patch

Review of attachment 809166 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +198,3 @@
>          switch (jsop) {
>            case JSOP_LE:
> +            comp.set(Range::NoInt32LowerBound, bound, true, Range::IncludesInfinity);

(Beta nodes) If we inverted the condition or if we are on the false-side of the condition, then these ranges should include NaN.

@@ -840,5 @@
>      if (type() != MIRType_Double)
>          return;
>  
>      double d = value().toDouble();
> -    int exp = Range::IncludesInfinityAndNaN;

oh, ok, forgot my previous comment on the last patch ;)

::: js/src/jit/RangeAnalysis.h
@@ +206,5 @@
> +    // values of lower() and upper().
> +    //
> +    // Note:
> +    //     exponent of JSVAL_INT_MIN == 31
> +    //     exponent of JSVAL_INT_MAX == 30

Thanks for updating this comment :)

@@ +210,5 @@
> +    //     exponent of JSVAL_INT_MAX == 30
> +    uint16_t exponentImpliedByInt32Bounds() const {
> +         // The number of bits needed to encode |max| is the power of 2 plus one.
> +         uint32_t max = Max(mozilla::Abs(lower()), mozilla::Abs(upper()));
> +         return mozilla::FloorLog2(max);

I was thinking of suggesting a comment, but I think adding the following assertion would be even better:
  JS_ASSERT(mozilla::FloorLog2(max) == ExponentComponent(double(max)));

@@ +219,5 @@
> +    // be completely valid before and it is guaranteed to be kept valid.
> +    void optimize() {
> +        if (hasInt32Bounds()) {
> +            // Examine lower(), upper(), hasInt32LowerBound(), and hasInt32UpperBound(),
> +            // and if they imply a better exponent bound than max_exponent_, set

We no longer look at hasInt32LowerBound for the computation of the exponent.

@@ +225,5 @@
> +            // initialized before calling this method.
> +            uint16_t newExponent = exponentImpliedByInt32Bounds();
> +            if (newExponent < max_exponent_) {
> +                max_exponent_ = newExponent;
> +            }

style-nit: remove braces.

@@ +231,5 @@
> +            // If we have a completely precise range, the value is an integer,
> +            // since we can only represent integers.
> +            if (canHaveFractionalPart_ && lower_ == upper_) {
> +                canHaveFractionalPart_ = false;
> +            }

style-nit: remove braces.

@@ +249,5 @@
> +
> +    // Construct a range from the given raw values.
> +    Range(int32_t l, bool lu, int32_t h, bool hu, bool f, uint16_t e)
> +        : symbolicLower_(NULL),
> +           symbolicUpper_(NULL)

style-nit:
 - the colon is indented by 2.
 - names are aligned and indented by 4.
 - lu -> lb & hu -> hb ?

@@ +264,4 @@
>      }
>  
> +    Range(int64_t l, int64_t h, bool f, uint16_t e)
> +        : symbolicLower_(NULL),

style-nit: colon should be indented by 2.

@@ +447,1 @@
>          JS_ASSERT_IF(!hasInt32LowerBound_, lower_ == JSVAL_INT_MIN);

optimize does not update the bounds, so we can remove the JS_ASSERT_IF.

Comment 49

[Nicolas B. Pierron [:nbp]]

Comment on attachment 809126 [details] [diff] [review]
range-use-accessors.patch

Review of attachment 809126 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +668,5 @@
>  
>  Range *
>  Range::ursh(const Range *lhs, int32_t c)
>  {
> +    JS_ASSERT(lhs->isInt32());

nit: Remove it, this is not a property of ursh.

@@ +703,5 @@
>  
>  Range *
>  Range::ursh(const Range *lhs, const Range *rhs)
>  {
> +    JS_ASSERT(lhs->isInt32());

nit: Remove it, this is not a property of ursh.

@@ +992,5 @@
>  
> +    // ursh convers its left operand to uint32, but since we lack support for
> +    // unsigned ranges, wrapping the range around to signed int32 is a
> +    // conservative approximation.
> +    left.wrapAroundToInt32();

Add comment to mention that is this is not a property of Ursh but a property of enforced by the type policy and the bailout in the code generator.

Comment 50

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803954 [details] [diff] [review]
range-doubles.patch

Review of attachment 803954 [details] [diff] [review]:
-----------------------------------------------------------------

r=me, with the renaming of range-set patch.

Comment 51

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803958 [details] [diff] [review]
range-assert-type.patch

Review of attachment 803958 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/MIR.h
@@ +360,5 @@
>      // operands after the truncate phase of the range analysis will lead to
>      // errors. Instead, one should define the collectRangeInfo() to set the
>      // right set of flags which are dependent on the range of the inputs.
>      Range *range() const {
> +        JS_ASSERT(type() != MIRType_None);

could we just assert that:
  JS_ASSERT_IF(type() == MIRType_None, range_ == NULL);

instead of adding extra conditions in addition to the Range pointer?

Comment 52

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803959 [details] [diff] [review]
range-assert-invariants.patch

Review of attachment 803959 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.h
@@ +181,5 @@
> +        JS_ASSERT(lower_ <= upper_);
> +        JS_ASSERT_IF(lower_unbounded_, lower_ == JSVAL_INT_MIN);
> +        JS_ASSERT_IF(upper_unbounded_, upper_ == JSVAL_INT_MAX);
> +        JS_ASSERT_IF(lower_unbounded_ || upper_unbounded_, max_exponent_ >= MaxInt32Exponent);
> +        JS_ASSERT(max_exponent_ <= IncludesInfinityAndNaN);

Update this one based on the values of flags.

@@ +186,5 @@
> +        JS_ASSERT(max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(upper_)));
> +        JS_ASSERT(max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(lower_)));
> +
> +        // The following are essentially static assertions.
> +        JS_ASSERT(mozilla::FloorLog2(JSVAL_INT_MIN) == MaxInt32Exponent);

We have static assertions, see JS_STATIC_ASSERT.

Comment 53

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803961 [details] [diff] [review]
range-div.patch

Review of attachment 803961 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +1141,5 @@
> +    // won't be further from zero than lhs.
> +    if (rhs.lower() > 0 && lhs.lower() >= 0)
> +        setRange(new Range(Min(0, lhs.lower()),
> +                           Max(0, lhs.upper()),
> +                           true, lhs.exponent()));

Min(0, lhs.lower()) will always return 0.

@@ +1162,5 @@
> +    // Something simple for now: When taking the sqrt of a positive value, the
> +    // result won't be further from zero than the input.
> +    setRange(new Range(input.lower(),
> +                       Max(0, input.upper()),
> +                       true, input.exponent()));

the minimum is the square root of input.lower() and not input.lower() which would be higher for everything except 1.
The upper case is meaning less as input.upper() is >= 0, based on the previous condition.

Comment 54

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803950 [details] [diff] [review]
range-helper-predicates.patch

Review of attachment 803950 [details] [diff] [review]:
-----------------------------------------------------------------

Ask for review again after answering the goal of accessors for canBeLessThan & isLowerInterestingInt32 & isUpperInterestingInt32.
I Cancel the review flag for now.

Comment 55

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #46)
> Comment on attachment 808986 [details] [diff] [review]
> range-infinity-and-nan.patch
> 
> Review of attachment 808986 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +304,5 @@
> > +        sp.printf(" (U inf U NaN)", max_exponent_);
> > +    else if (max_exponent_ == IncludesInfinity)
> > +        sp.printf(" (U inf)");
> > +    else if (!hasInt32UpperBound_ || !hasInt32LowerBound_)
> > +        sp.printf(" (<= MAXp+%d)", max_exponent_);
> 
> I never saw the p notation before, and I think it might be easier to
> understand with a strict inequality:
>  - sp.printf(" (< 0x1p+%d)", max_exponent_ + 1);
>  - sp.printf(" (< 2**%d)", max_exponent_ + 1);

If printing "max_exponent_ + 1" makes it easier to understand, should we just change the meaning of max_exponent_ so that it means "< pow(2, max_exponent_)"? I'd like to have this have the property that the number printed matches the number stored in the class, so that we don't have to juggle off-by-one corrections when looking at code and debug output.

> @@ +850,5 @@
> >      if (type() != MIRType_Double)
> >          return;
> >  
> >      double d = value().toDouble();
> > +    int exp = Range::IncludesInfinityAndNaN;
> 
> nit:
>  - use Range::IncludesInfinity;
>  - and move this declaration below the check of IsNaN.

Ok. I fixed this in a different patch, but it makes sense to get it right here :). Thanks for your patience with all these patches; I should probably work to avoid having quite so many patches in flight at once.

Comment 56

[Dan Gohman [:sunfish]]

Attachment: range-div.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #53)
> Comment on attachment 803961 [details] [diff] [review]
> range-div.patch
> 
> Review of attachment 803961 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +1141,5 @@
> > +    // won't be further from zero than lhs.
> > +    if (rhs.lower() > 0 && lhs.lower() >= 0)
> > +        setRange(new Range(Min(0, lhs.lower()),
> > +                           Max(0, lhs.upper()),
> > +                           true, lhs.exponent()));
> 
> Min(0, lhs.lower()) will always return 0.

Fixed, to just use zero, since that's enough for now.

> @@ +1162,5 @@
> > +    // Something simple for now: When taking the sqrt of a positive value, the
> > +    // result won't be further from zero than the input.
> > +    setRange(new Range(input.lower(),
> > +                       Max(0, input.upper()),
> > +                       true, input.exponent()));
> 
> the minimum is the square root of input.lower() and not input.lower() which
> would be higher for everything except 1.
> The upper case is meaning less as input.upper() is >= 0, based on the
> previous condition.

Good catch. I changed it to just zero, and changed the upper bound to just input.upper(), for simplicity.

Comment 57

[Dan Gohman [:sunfish]]

Attachment: range-helper-predicates.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #54)
> Ask for review again after answering the goal of accessors for canBeLessThan
> & isLowerInterestingInt32 & isUpperInterestingInt32.

Here's the patch without those accessors.

Comment 58

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #51)
> ::: js/src/jit/MIR.h
> @@ +360,5 @@
> >      // operands after the truncate phase of the range analysis will lead to
> >      // errors. Instead, one should define the collectRangeInfo() to set the
> >      // right set of flags which are dependent on the range of the inputs.
> >      Range *range() const {
> > +        JS_ASSERT(type() != MIRType_None);
> 
> could we just assert that:
>   JS_ASSERT_IF(type() == MIRType_None, range_ == NULL);
> 
> instead of adding extra conditions in addition to the Range pointer?

For example, with MBoundsCheck, client code should call range() on the index, not on the MBoundsCheck instruction itself. Putting the assert in the range() call catches bugs like that.

The other outstanding question in this bug is this notation for printing the exponent range:

+        sp.printf(" (<= MAXp+%d)", max_exponent_);

Of the proposed alternatives, I still find this the most clear. In particular, I'd really like to avoid a hidden +1 in the printing routine.

Comment 59

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #58)
> (In reply to Nicolas B. Pierron [:nbp] from comment #51)
> > ::: js/src/jit/MIR.h
> > @@ +360,5 @@
> > >      // operands after the truncate phase of the range analysis will lead to
> > >      // errors. Instead, one should define the collectRangeInfo() to set the
> > >      // right set of flags which are dependent on the range of the inputs.
> > >      Range *range() const {
> > > +        JS_ASSERT(type() != MIRType_None);
> > 
> > could we just assert that:
> >   JS_ASSERT_IF(type() == MIRType_None, range_ == NULL);
> > 
> > instead of adding extra conditions in addition to the Range pointer?
> 
> For example, with MBoundsCheck, client code should call range() on the
> index, not on the MBoundsCheck instruction itself. Putting the assert in the
> range() call catches bugs like that.

Ok.
 
> The other outstanding question in this bug is this notation for printing the
> exponent range:
> 
> +        sp.printf(" (<= MAXp+%d)", max_exponent_);
> 
> Of the proposed alternatives, I still find this the most clear. In
> particular, I'd really like to avoid a hidden +1 in the printing routine.

Another solution is to output the +1 instead.

    sp.printf(" (< 2^(%d+1))", max_exponent_);

I really want to avoid switching everything off-by-one as this is directly coming from the double representation.  I don't see any reason why not printing max_exponent+1.

Using "MAX" and "p" is not clear, even if the notation represent the real meaning of it.

Comment 60

[Dan Gohman [:sunfish]]

Comment on attachment 803958 [details] [diff] [review]
range-assert-type.patch

In comment 59 you agreed with this change, so I'm re-requesting review :).

Comment 61

[Nicolas B. Pierron [:nbp]]

Comment on attachment 803958 [details] [diff] [review]
range-assert-type.patch

Review of attachment 803958 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks for asking again :)

Comment 62

[Steve Fink [:sfink] [:s:]]

(In reply to Nicolas B. Pierron [:nbp] from comment #52)
> We have static assertions, see JS_STATIC_ASSERT.

New code should be using static_assert now. (see bug 712939)

Comment 63

[Dan Gohman [:sunfish]]

> sp.printf(" (< 2^(%d+1))", max_exponent_);

This works for me. Of course, we can always change it if we like something else better.

> New code should be using static_assert now. (see bug 712939)

Unfortunately, the asserts in question can't be any kind of static asserts because they call FloorLog2, which not all compilers can support as constexpr.

Thanks for all the reviews! All remaining patches on this bug are now committed:

https://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?changeset=a70ad9d7e0f4

Of course, if you have any further concerns or comments on these changes, please let me know.

Comment 64

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/38ed27acd3b3
https://hg.mozilla.org/mozilla-central/rev/7d523ba71bfc
https://hg.mozilla.org/mozilla-central/rev/70147fbd31fb
https://hg.mozilla.org/mozilla-central/rev/af3b8a2268a3
https://hg.mozilla.org/mozilla-central/rev/26df5342ca05
https://hg.mozilla.org/mozilla-central/rev/27abc86d9ada
https://hg.mozilla.org/mozilla-central/rev/9392f41259bc
https://hg.mozilla.org/mozilla-central/rev/ce4fdd6c612f
https://hg.mozilla.org/mozilla-central/rev/2de50965c299
https://hg.mozilla.org/mozilla-central/rev/13a8512e04f8
https://hg.mozilla.org/mozilla-central/rev/a70ad9d7e0f4