Range should have a constructor which takes a double

RESOLVED FIXED in mozilla27

Status

()

Core
JavaScript Engine: JIT
--
enhancement
RESOLVED FIXED
5 years ago
4 years ago

People

(Reporter: sunfish, Assigned: sunfish)

Tracking

unspecified
mozilla27
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

5 years ago
Following up on comment 29 of bug 915846 [0], Range should have a constructor and/or set methods which take a double argument, which could take on most of the logic that currently lives in MConstant::computeRange, and which could then be used from more places.

[0] https://bugzilla.mozilla.org/show_bug.cgi?id=915846#c29
(Assignee)

Updated

5 years ago
Depends on: 923659
(Assignee)

Comment 1

5 years ago
Created attachment 814570 [details] [diff] [review]
range-double-ctor.patch
Attachment #814570 - Flags: review?(nicolas.b.pierron)

Updated

5 years ago
Component: JavaScript Engine → JavaScript Engine: JIT
Comment on attachment 814570 [details] [diff] [review]
range-double-ctor.patch

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

::: js/src/jit/RangeAnalysis.cpp
@@ +438,5 @@
> +Range::setDouble(double l, double h)
> +{
> +    int_fast16_t extractedExp = Max(ExponentComponent(l), ExponentComponent(h));
> +
> +    int_fast16_t adjustedExp;

int_fast16_t adjuestedExp = 0;

@@ +446,5 @@
> +        adjustedExp = IncludesInfinity;
> +    else
> +        adjustedExp = extractedExp;
> +
> +    if (l >= INT32_MIN && l <= INT32_MAX) {

double newLower = IsNaN(l) ? NegativeInfinity() : l;
// IncludesInfinity is the same infinity value as the double exponent representation.
int_fast16_t lExp = IsNaN(l) ? IncludesInfinityAndNaN : ExponentComponent(l);
if (lExp < Range::MaxTruncatableExponent) {

@@ +451,5 @@
> +        double newLower = floor(l);
> +        lower_ = int32_t(newLower);
> +        hasInt32LowerBound_ = true;
> +        adjustedExp = Max(adjustedExp, ExponentComponent(newLower));
> +    }

lExp = ExponentComponent(newLower);
}
adjustedExp = Max(adjustedExp, lExp);

@@ +462,5 @@
> +
> +    max_exponent_ = Max(adjustedExp, int_fast16_t(0));
> +    canHaveFractionalPart_ = IsNegative(IsNaN(l) ? NegativeInfinity() : l) !=
> +                             IsNegative(IsNaN(h) ? PositiveInfinity() : h) ||
> +                             extractedExp <= Range::MaxTruncatableExponent;

if (newLower == newUpper)
  canHaveFractionalPart_ = false;
else
  canHaveFractionalPart_ = … || Min(lExp, hExp) <= Range::MaxTruncatableExponent;

And add a comment that the range can have a fractional part if any of the double in the range can have an exponent below the Max truncatable exponent (i-e changing sign, or one of the extremity has a lower exponent).  We also need the '<=' instead of '<' because of floor & ceil.

::: js/src/jit/RangeAnalysis.h
@@ +182,5 @@
> +
> +        // 2147483647.9 is greater than INT32_MAX but still has an exponent
> +        // of 30. Add 1 to account for ranges including such numbers.
> +        JS_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_,
> +                     max_exponent_ + canHaveFractionalPart_ >= MaxInt32Exponent);

We should not need that, because this means that we should replace all uses of max_exponent_ by this addition all over the place.

@@ +190,5 @@
>                    max_exponent_ == IncludesInfinityAndNaN);
> +        JS_ASSERT_IF(hasInt32UpperBound_,
> +                     max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(upper_)));
> +        JS_ASSERT_IF(hasInt32LowerBound_,
> +                     max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(lower_)));

We want the exponent to be correct in all cases, why adding a condition on the bound?
Attachment #814570 - Flags: review?(nicolas.b.pierron)
(Assignee)

Comment 3

5 years ago
Created attachment 815015 [details] [diff] [review]
range-double-ctor.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #2)
> Comment on attachment 814570 [details] [diff] [review]
> range-double-ctor.patch
> 
> Review of attachment 814570 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +438,5 @@
> > +Range::setDouble(double l, double h)
> > +{
> > +    int_fast16_t extractedExp = Max(ExponentComponent(l), ExponentComponent(h));
> > +
> > +    int_fast16_t adjustedExp;
> 
> int_fast16_t adjuestedExp = 0;

Ok.

> @@ +446,5 @@
> > +        adjustedExp = IncludesInfinity;
> > +    else
> > +        adjustedExp = extractedExp;
> > +
> > +    if (l >= INT32_MIN && l <= INT32_MAX) {
> 
> double newLower = IsNaN(l) ? NegativeInfinity() : l;
> // IncludesInfinity is the same infinity value as the double exponent
> representation.
> int_fast16_t lExp = IsNaN(l) ? IncludesInfinityAndNaN : ExponentComponent(l);
> if (lExp < Range::MaxTruncatableExponent) {
> 
> @@ +451,5 @@
> > +        double newLower = floor(l);
> > +        lower_ = int32_t(newLower);
> > +        hasInt32LowerBound_ = true;
> > +        adjustedExp = Max(adjustedExp, ExponentComponent(newLower));
> > +    }
> 
> lExp = ExponentComponent(newLower);
> }
> adjustedExp = Max(adjustedExp, lExp);

I don't understand what your proposed changes here are doing. The lower_ and upper_ fields are int32_t, so it's not useful to convert l and h into lower_ and upper_ values if they're outside [INT32_MIN,INT32_MAX].

One thing that is non-obvious about my change here is that it doesn't set lower_ and upper_ at all in the case where l and h are outside the int32_t range. I've now corrected that.

> @@ +462,5 @@
> > +
> > +    max_exponent_ = Max(adjustedExp, int_fast16_t(0));
> > +    canHaveFractionalPart_ = IsNegative(IsNaN(l) ? NegativeInfinity() : l) !=
> > +                             IsNegative(IsNaN(h) ? PositiveInfinity() : h) ||
> > +                             extractedExp <= Range::MaxTruncatableExponent;
> 
> if (newLower == newUpper)
>   canHaveFractionalPart_ = false;
> else
>   canHaveFractionalPart_ = … || Min(lExp, hExp) <=
> Range::MaxTruncatableExponent;
> 
> And add a comment that the range can have a fractional part if any of the
> double in the range can have an exponent below the Max truncatable exponent
> (i-e changing sign, or one of the extremity has a lower exponent).  We also
> need the '<=' instead of '<' because of floor & ceil.

Ok, I added some comments. And actually, I believe the <= isn't needed anymore. We're considering the exponent of the actual value, before floor/ceil are applied.

> ::: js/src/jit/RangeAnalysis.h
> @@ +182,5 @@
> > +
> > +        // 2147483647.9 is greater than INT32_MAX but still has an exponent
> > +        // of 30. Add 1 to account for ranges including such numbers.
> > +        JS_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_,
> > +                     max_exponent_ + canHaveFractionalPart_ >= MaxInt32Exponent);
> 
> We should not need that, because this means that we should replace all uses
> of max_exponent_ by this addition all over the place.

The exponent of 2147483647.9 is 30. A range containing 2147483647.9 should have hasInt32UpperBound_ set to false, since there is no int32_t value which works as an upper bound. The old assert fails on such a range, even though the range is valid. The new assert does not fail on such a range. I believe this is a correct change.

This assert is admittedly a little odd though. Right now, when lower_ and upper_ imply a tighter bound than what max_exponent_ implies, optimize() silently recomputes max_exponent_. However, when max_exponent_ implies a tighter bound than what lower_ and upper_ imply, assertInvariants() aborts. Would you prefer optimize() to silently handle both cases?

> @@ +190,5 @@
> >                    max_exponent_ == IncludesInfinityAndNaN);
> > +        JS_ASSERT_IF(hasInt32UpperBound_,
> > +                     max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(upper_)));
> > +        JS_ASSERT_IF(hasInt32LowerBound_,
> > +                     max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(lower_)));
> 
> We want the exponent to be correct in all cases, why adding a condition on
> the bound?

upper_ and lower_ don't have their literal meaning when !hasInt32UpperBound_ and !hasInt32LowerBound_, respectively, so it seemed logical to disable this check in those cases, but I guess it works either way. I reverted this.
Attachment #814570 - Attachment is obsolete: true
Attachment #815015 - Flags: review?(nicolas.b.pierron)
(In reply to Dan Gohman [:sunfish] from comment #3)
> Created attachment 815015 [details] [diff] [review]
> range-double-ctor.patch
> 
> (In reply to Nicolas B. Pierron [:nbp] from comment #2)
> > @@ +446,5 @@
> > > +        adjustedExp = IncludesInfinity;
> > > +    else
> > > +        adjustedExp = extractedExp;
> > > +
> > > +    if (l >= INT32_MIN && l <= INT32_MAX) {
> > 
> > double newLower = IsNaN(l) ? NegativeInfinity() : l;
> > // IncludesInfinity is the same infinity value as the double exponent
> > representation.
> > int_fast16_t lExp = IsNaN(l) ? IncludesInfinityAndNaN : ExponentComponent(l);
> > if (lExp < Range::MaxTruncatableExponent) {
> > 
> > @@ +451,5 @@
> > > +        double newLower = floor(l);
> > > +        lower_ = int32_t(newLower);
> > > +        hasInt32LowerBound_ = true;
> > > +        adjustedExp = Max(adjustedExp, ExponentComponent(newLower));
> > > +    }
> > 
> > lExp = ExponentComponent(newLower);
> > }
> > adjustedExp = Max(adjustedExp, lExp);
> 
> I don't understand what your proposed changes here are doing. The lower_ and
> upper_ fields are int32_t, so it's not useful to convert l and h into lower_
> and upper_ values if they're outside [INT32_MIN,INT32_MAX].

One thing is that we can remove the if for the computation of adjustedExp, and do that while we are manipulating l and h.

Remove the extractedExp, as the only useful use of it is to do a Max(0, ExponentComponent(l), ExponentComponent(h)) and we can compute them incrementally.

> > @@ +462,5 @@
> > > +
> > > +    max_exponent_ = Max(adjustedExp, int_fast16_t(0));
> > > +    canHaveFractionalPart_ = IsNegative(IsNaN(l) ? NegativeInfinity() : l) !=
> > > +                             IsNegative(IsNaN(h) ? PositiveInfinity() : h) ||
> > > +                             extractedExp <= Range::MaxTruncatableExponent;
> > 
> > if (newLower == newUpper)
> >   canHaveFractionalPart_ = false;
> > else
> >   canHaveFractionalPart_ = … || Min(lExp, hExp) <=
> > Range::MaxTruncatableExponent;
> > 
> > And add a comment that the range can have a fractional part if any of the
> > double in the range can have an exponent below the Max truncatable exponent
> > (i-e changing sign, or one of the extremity has a lower exponent).  We also
> > need the '<=' instead of '<' because of floor & ceil.
> 
> Ok, I added some comments. And actually, I believe the <= isn't needed
> anymore. We're considering the exponent of the actual value, before
> floor/ceil are applied.
> 
> > ::: js/src/jit/RangeAnalysis.h
> > @@ +182,5 @@
> > > +
> > > +        // 2147483647.9 is greater than INT32_MAX but still has an exponent
> > > +        // of 30. Add 1 to account for ranges including such numbers.
> > > +        JS_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_,
> > > +                     max_exponent_ + canHaveFractionalPart_ >= MaxInt32Exponent);
> > 
> > We should not need that, because this means that we should replace all uses
> > of max_exponent_ by this addition all over the place.
> 
> The exponent of 2147483647.9 is 30. A range containing 2147483647.9 should
> have hasInt32UpperBound_ set to false, since there is no int32_t value which
> works as an upper bound. The old assert fails on such a range, even though
> the range is valid. The new assert does not fail on such a range. I believe
> this is a correct change.

Ok, so:

        JS_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_,
                     max_exponent_ >= ExponentComponent(double(INT32_MAX)));
        JS_ASSERT_IF(hasInt32LowerBound_ && hasInt32UpperBound_,
                     max_exponent_ <= ExponentComponent(double(INT32_MIN)));

> This assert is admittedly a little odd though. Right now, when lower_ and
> upper_ imply a tighter bound than what max_exponent_ implies, optimize()
> silently recomputes max_exponent_.

This is fine, as max_exponent_ is an over-approximation.

> However, when max_exponent_ implies a
> tighter bound than what lower_ and upper_ imply, assertInvariants() aborts.
> Would you prefer optimize() to silently handle both cases?

No, asserting is the right thing to do.

> > @@ +190,5 @@
> > >                    max_exponent_ == IncludesInfinityAndNaN);
> > > +        JS_ASSERT_IF(hasInt32UpperBound_,
> > > +                     max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(upper_)));
> > > +        JS_ASSERT_IF(hasInt32LowerBound_,
> > > +                     max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(lower_)));
> > 
> > We want the exponent to be correct in all cases, why adding a condition on
> > the bound?
> 
> upper_ and lower_ don't have their literal meaning when !hasInt32UpperBound_
> and !hasInt32LowerBound_, respectively, so it seemed logical to disable this
> check in those cases, but I guess it works either way. I reverted this.

I think this should be part of a follow-up patch, to make sure we do not add any additional bug.
On the other hand, I am not sure this is worth avoiding, as we are able to assert more by maintaining this invariant.
Comment on attachment 815015 [details] [diff] [review]
range-double-ctor.patch

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

::: js/src/jit/RangeAnalysis.cpp
@@ +484,5 @@
> +    // which double precision values don't have enough precision to represent
> +    // fractional values.
> +    canHaveFractionalPart_ = IsNegative(IsNaN(l) ? NegativeInfinity() : l) !=
> +                             IsNegative(IsNaN(h) ? PositiveInfinity() : h) ||
> +                             extractedExp < MaxTruncatableExponent;

We need a Min(lExp, uExp) instead of extractExp.
Attachment #815015 - Flags: review?(nicolas.b.pierron)
(Assignee)

Comment 6

5 years ago
Created attachment 815346 [details] [diff] [review]
range-double-ctor.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #4)
> (In reply to Dan Gohman [:sunfish] from comment #3)
> > I don't understand what your proposed changes here are doing. The lower_ and
> > upper_ fields are int32_t, so it's not useful to convert l and h into lower_
> > and upper_ values if they're outside [INT32_MIN,INT32_MAX].
> 
> One thing is that we can remove the if for the computation of adjustedExp,
> and do that while we are manipulating l and h.
> 
> Remove the extractedExp, as the only useful use of it is to do a Max(0,
> ExponentComponent(l), ExponentComponent(h)) and we can compute them
> incrementally.

Looking at this again, it isn't actually necessary to adjust the exponent after doing the floor/ceil. That significantly simplifies this code. Take a look at the Range::setDouble code in this new patch and see what you think.

> > > ::: js/src/jit/RangeAnalysis.h
> > > @@ +182,5 @@
> > > > +
> > > > +        // 2147483647.9 is greater than INT32_MAX but still has an exponent
> > > > +        // of 30. Add 1 to account for ranges including such numbers.
> > > > +        JS_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_,
> > > > +                     max_exponent_ + canHaveFractionalPart_ >= MaxInt32Exponent);
> > > 
> > > We should not need that, because this means that we should replace all uses
> > > of max_exponent_ by this addition all over the place.
> > 
> > The exponent of 2147483647.9 is 30. A range containing 2147483647.9 should
> > have hasInt32UpperBound_ set to false, since there is no int32_t value which
> > works as an upper bound. The old assert fails on such a range, even though
> > the range is valid. The new assert does not fail on such a range. I believe
> > this is a correct change.
> 
> Ok, so:
> 
>         JS_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_,
>                      max_exponent_ >= ExponentComponent(double(INT32_MAX)));

I like the idea, though it is strictly less strict than the assertions in the patch. Also, the assertions which compare max_exponent_ with lower_/upper_ also need canHaveFractionalPart_ adjustments. I reorganized this code and added some comments; let me know what you think.

And actually, this extra strictness caught an interesting case. Consider Range::intersect on I[0,10], and F[3.0,3.5] which is actually represented as F[3,4] (< pow(2, 1+1)). max_exponent_ for the second range is 1, which is more precise than upper_ here because upper_ has to be rounded up to the nearest int32. The assertion was aborting because Range::intersect was returning I[3,4] (< pow(2, 1+1)). I added some new code to Range::exponent to handle cases like this, and it now returns I[3,3], which passes the assertion.

>         JS_ASSERT_IF(hasInt32LowerBound_ && hasInt32UpperBound_,
>                      max_exponent_ <= ExponentComponent(double(INT32_MIN)));

This is actually putting an upper bound on max_exponent_, which isn't one of the intended invariants.

> > > @@ +190,5 @@
> > > >                    max_exponent_ == IncludesInfinityAndNaN);
> > > > +        JS_ASSERT_IF(hasInt32UpperBound_,
> > > > +                     max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(upper_)));
> > > > +        JS_ASSERT_IF(hasInt32LowerBound_,
> > > > +                     max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(lower_)));
> > > 
> > > We want the exponent to be correct in all cases, why adding a condition on
> > > the bound?
> > 
> > upper_ and lower_ don't have their literal meaning when !hasInt32UpperBound_
> > and !hasInt32LowerBound_, respectively, so it seemed logical to disable this
> > check in those cases, but I guess it works either way. I reverted this.
> 
> I think this should be part of a follow-up patch, to make sure we do not add
> any additional bug.
> On the other hand, I am not sure this is worth avoiding, as we are able to
> assert more by maintaining this invariant.

Ok. I left this change out.

(In reply to Nicolas B. Pierron [:nbp] from comment #5)
> Comment on attachment 815015 [details] [diff] [review]
> range-double-ctor.patch
> 
> Review of attachment 815015 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +484,5 @@
> > +    // which double precision values don't have enough precision to represent
> > +    // fractional values.
> > +    canHaveFractionalPart_ = IsNegative(IsNaN(l) ? NegativeInfinity() : l) !=
> > +                             IsNegative(IsNaN(h) ? PositiveInfinity() : h) ||
> > +                             extractedExp < MaxTruncatableExponent;
> 
> We need a Min(lExp, uExp) instead of extractExp.

Oops, yes. Fixed. I also simplified this code.
Attachment #815015 - Attachment is obsolete: true
Attachment #815346 - Flags: review?(nicolas.b.pierron)
Comment on attachment 815346 [details] [diff] [review]
range-double-ctor.patch

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

Awesome work! This are really hard pieces that you are putting together as Range analysis implies thinking of all corner cases simultaneously.

::: js/src/jit/RangeAnalysis.cpp
@@ +380,5 @@
> +    // For example, when the floating-point range has an actual maximum value
> +    // of 1.5, it may have a range like [0,2] and the max_exponent may be zero.
> +    // When intersecting such a range with an integer range, the fractional part
> +    // of the range is dropped, but the max exponent of 0 remains valid.
> +    if (newExponent < MaxInt32Exponent) {

if (lhs->canHaveFractionalPart_ != rhs->canHaveFractionalPart_ && newExponent < MaxInt32Exponent)

If both have a fractional part, then we remain with a range which has a more precise exponent than its boundaries.
If both are integers, then the exponent cannot be more precise than any of the boundaries.

@@ +476,5 @@
> +    return uint16_t(Max(int_fast16_t(0), ExponentComponent(d)));
> +}
> +
> +void
> +Range::setDouble(double l, double h)

This looks better :)

::: js/src/jit/RangeAnalysis.h
@@ +180,1 @@
>          JS_ASSERT(lower_ <= upper_);

nit: Because we also need a bit of insanity to think of anything related to range analysis :)

@@ +202,5 @@
> +                     max_exponent_ + canHaveFractionalPart_ >= MaxInt32Exponent);
> +        JS_ASSERT(max_exponent_ + canHaveFractionalPart_ >=
> +                  mozilla::FloorLog2(mozilla::Abs(upper_)));
> +        JS_ASSERT(max_exponent_ + canHaveFractionalPart_ >=
> +                  mozilla::FloorLog2(mozilla::Abs(lower_)));

Now that I see the use of it in Range::intersect, it makes sense to have these assertions, otherwise it felt just like a weakening of the assertion.
Attachment #815346 - Flags: review?(nicolas.b.pierron) → review+
(Assignee)

Comment 8

5 years ago
(In reply to Nicolas B. Pierron [:nbp] from comment #7)
> Comment on attachment 815346 [details] [diff] [review]
> range-double-ctor.patch
> 
> Review of attachment 815346 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Awesome work! This are really hard pieces that you are putting together as
> Range analysis implies thinking of all corner cases simultaneously.
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +380,5 @@
> > +    // For example, when the floating-point range has an actual maximum value
> > +    // of 1.5, it may have a range like [0,2] and the max_exponent may be zero.
> > +    // When intersecting such a range with an integer range, the fractional part
> > +    // of the range is dropped, but the max exponent of 0 remains valid.
> > +    if (newExponent < MaxInt32Exponent) {
> 
> if (lhs->canHaveFractionalPart_ != rhs->canHaveFractionalPart_ &&
> newExponent < MaxInt32Exponent)
> 
> If both have a fractional part, then we remain with a range which has a more
> precise exponent than its boundaries.
> If both are integers, then the exponent cannot be more precise than any of
> the boundaries.

Good idea. This resulted in a nice simplification.

> ::: js/src/jit/RangeAnalysis.h
> @@ +180,1 @@
> >          JS_ASSERT(lower_ <= upper_);
> 
> nit: Because we also need a bit of insanity to think of anything related to
> range analysis :)

:)

https://hg.mozilla.org/integration/mozilla-inbound/rev/42a20a0d4269
https://hg.mozilla.org/mozilla-central/rev/42a20a0d4269
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla27
Depends on: 927389
Depends on: 928450
Depends on: 936737
Depends on: 1008106
You need to log in before you can comment on or make changes to this bug.