Closed
Bug 918607
Opened 6 years ago
Closed 6 years ago
Range should have a constructor which takes a double
Categories
(Core :: JavaScript Engine: JIT, enhancement)
Core
JavaScript Engine: JIT
Not set
Tracking
()
RESOLVED
FIXED
mozilla27
People
(Reporter: sunfish, Assigned: sunfish)
References
Details
Attachments
(1 file, 2 obsolete files)
16.14 KB,
patch

nbp
:
review+

Details  Diff  Splinter Review 
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  
Comment 1•6 years ago


Attachment #814570 
Flags: review?(nicolas.b.pierron)
Updated•6 years ago

Component: JavaScript Engine → JavaScript Engine: JIT
Comment 2•6 years ago


Comment on attachment 814570 [details] [diff] [review] rangedoublector.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 (ie 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•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #2) > Comment on attachment 814570 [details] [diff] [review] > rangedoublector.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 nonobvious 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 > (ie 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)
Comment 4•6 years ago


(In reply to Dan Gohman [:sunfish] from comment #3) > Created attachment 815015 [details] [diff] [review] > rangedoublector.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 > > (ie 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 overapproximation. > 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 followup 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 5•6 years ago


Comment on attachment 815015 [details] [diff] [review] rangedoublector.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•6 years ago


(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 followup 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] > rangedoublector.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 7•6 years ago


Comment on attachment 815346 [details] [diff] [review] rangedoublector.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 floatingpoint 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•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #7) > Comment on attachment 815346 [details] [diff] [review] > rangedoublector.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 floatingpoint 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/mozillainbound/rev/42a20a0d4269
Comment 9•6 years ago


https://hg.mozilla.org/mozillacentral/rev/42a20a0d4269
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution:  → FIXED
Target Milestone:  → mozilla27
You need to log in
before you can comment on or make changes to this bug.
Description
•