Closed
Bug 915846
Opened 6 years ago
Closed 6 years ago
Range Analysis API changes
Categories
(Core :: JavaScript Engine, enhancement)
Core
JavaScript Engine
Not set
Tracking
()
RESOLVED
FIXED
mozilla27
People
(Reporter: sunfish, Assigned: sunfish)
References
Details
Attachments
(20 files, 6 obsolete files)
Inspired by bug 910807, bug 909528, and others, I developed a series of rangeanalysis 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 rangeanalysis API more precise and more explicit.
Assignee  
Comment 1•6 years ago


Attachment #803935 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 2•6 years ago


Attachment #803936 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 3•6 years ago


Attachment #803938 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 4•6 years ago


Attachment #803939 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 5•6 years ago


Attachment #803940 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 6•6 years ago


Attachment #803942 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 7•6 years ago


Attachment #803944 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 8•6 years ago


Attachment #803946 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 9•6 years ago


Attachment #803948 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 10•6 years ago


Attachment #803949 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 11•6 years ago


Attachment #803950 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 12•6 years ago


Attachment #803951 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 13•6 years ago


Attachment #803952 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 14•6 years ago


Attachment #803953 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 15•6 years ago


Attachment #803954 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 16•6 years ago


Attachment #803956 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 17•6 years ago


Attachment #803958 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 18•6 years ago


Attachment #803959 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 19•6 years ago


Attachment #803960 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 20•6 years ago


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

Assignee: general → sunfish
Updated•6 years ago

Attachment #803935 
Flags: review?(nicolas.b.pierron) → review+
Comment 21•6 years ago


Comment on attachment 803936 [details] [diff] [review] rangetidy.patch Review of attachment 803936 [details] [diff] [review]:  Is there any linktime 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 linktime overhead, right? Could we do as we usually do, ie moving these functions into RangaAnalysisinl.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•6 years ago


Comment on attachment 803938 [details] [diff] [review] rangeeliminateboundscheckupper.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.
Attachment #803938 
Flags: review?(nicolas.b.pierron)
Updated•6 years ago

Attachment #803939 
Flags: review?(nicolas.b.pierron) → review+
Assignee  
Comment 24•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #21) > Comment on attachment 803936 [details] [diff] [review] > rangetidy.patch > > Review of attachment 803936 [details] [diff] [review]: >  > > Is there any linktime 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 linktime 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, ie moving these functions into > RangaAnalysisinl.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 linktime overhead being introduced.
Assignee  
Comment 25•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #22) > Comment on attachment 803938 [details] [diff] [review] > rangeeliminateboundscheckupper.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.
Attachment #803938 
Attachment is obsolete: true
Attachment #805802 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 26•6 years ago


rangeconsts.patch: https://hg.mozilla.org/integration/mozillainbound/rev/709992264f64 rangefractional.patch: https://hg.mozilla.org/integration/mozillainbound/rev/54adcc76078b
Whiteboard: [leave open]
Comment 27•6 years ago


Comment on attachment 803940 [details] [diff] [review] rangeunbounded.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
Attachment #803940 
Flags: review?(nicolas.b.pierron) → review+
Updated•6 years ago

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

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

Attachment #803942 
Flags: review?(nicolas.b.pierron) → review+
Comment 28•6 years ago


Comment on attachment 803944 [details] [diff] [review] rangemorerenames.patch Review of attachment 803944 [details] [diff] [review]:  nit: Fix your patch subject: Raname > Rename.
Attachment #803944 
Flags: review?(nicolas.b.pierron) → review+
Comment 29•6 years ago


Comment on attachment 803946 [details] [diff] [review] rangefactories.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 followup 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.
Attachment #803946 
Flags: review?(nicolas.b.pierron) → review+
Comment 30•6 years ago


Comment on attachment 803948 [details] [diff] [review] rangeinfinityandnan.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 doubleprecision > + // 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.
Attachment #803948 
Flags: review?(nicolas.b.pierron)
Comment 31•6 years ago


Comment on attachment 803949 [details] [diff] [review] rangeprivatemembers.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.
Attachment #803949 
Flags: review?(nicolas.b.pierron) → review+
Comment 32•6 years ago


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


Comment on attachment 803951 [details] [diff] [review] rangeuseaccessors.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/mozillacentral/source/js/src/jit/RangeAnalysis.cpp#l677
Attachment #803951 
Flags: review?(nicolas.b.pierron)
Comment 34•6 years ago


Comment on attachment 803952 [details] [diff] [review] rangeint32arithmetic.patch Review of attachment 803952 [details] [diff] [review]:  ::: js/src/jit/RangeAnalysis.cpp @@ +504,5 @@ > // Both operands are nonnegative, 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 nonnegative int32 will at least be 1 to account for the bit of sign.
Attachment #803952 
Flags: review?(nicolas.b.pierron) → review+
Comment 35•6 years ago


Comment on attachment 803953 [details] [diff] [review] rangeset.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();
Attachment #803953 
Flags: review?(nicolas.b.pierron)
Comment 36•6 years ago


https://hg.mozilla.org/mozillacentral/rev/709992264f64 https://hg.mozilla.org/mozillacentral/rev/54adcc76078b
Assignee  
Comment 37•6 years ago


(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.
Assignee  
Comment 38•6 years ago


rangetidy.patch: https://hg.mozilla.org/integration/mozillainbound/rev/e8f4ce1c8390 rangeeliminateboundscheckupper.patch: https://hg.mozilla.org/integration/mozillainbound/rev/d00e40c657a1
Comment 39•6 years ago


(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)?
Assignee  
Comment 40•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #39) > Maybe hasInt32Bounds instead of hasInt32LowerAndUpperBounds (isUnbounded)? That works for me. rangeunbounded.patch: https://hg.mozilla.org/integration/mozillainbound/rev/a3255cb88e5e rangeisfullybounded.patch: https://hg.mozilla.org/integration/mozillainbound/rev/6afebbb8e595 rangefactories.patch: https://hg.mozilla.org/integration/mozillainbound/rev/99240d780042 rangeprivatemembers.patch: https://hg.mozilla.org/integration/mozillainbound/rev/644fe03f2bd4 rangemorerenames.patch: https://hg.mozilla.org/integration/mozillainbound/rev/bbb3d10d2c1c
Assignee  
Comment 41•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #29) > We should open a followup 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•6 years ago


https://hg.mozilla.org/mozillacentral/rev/e8f4ce1c8390 https://hg.mozilla.org/mozillacentral/rev/d00e40c657a1 https://hg.mozilla.org/mozillacentral/rev/a3255cb88e5e https://hg.mozilla.org/mozillacentral/rev/6afebbb8e595 https://hg.mozilla.org/mozillacentral/rev/99240d780042 https://hg.mozilla.org/mozillacentral/rev/644fe03f2bd4 https://hg.mozilla.org/mozillacentral/rev/bbb3d10d2c1c
Assignee  
Comment 43•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #30) > Comment on attachment 803948 [details] [diff] [review] > rangeinfinityandnan.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 rangeassertinvariants.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 C99style 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 doubleprecision > > + // 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.
Attachment #803948 
Attachment is obsolete: true
Attachment #808986 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 44•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #33) > Comment on attachment 803951 [details] [diff] [review] > rangeuseaccessors.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.
Attachment #803951 
Attachment is obsolete: true
Attachment #809126 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 45•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #35) > Comment on attachment 803953 [details] [diff] [review] > rangeset.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 readded 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.
Attachment #803953 
Attachment is obsolete: true
Attachment #809166 
Flags: review?(nicolas.b.pierron)
Comment 46•6 years ago


Comment on attachment 808986 [details] [diff] [review] rangeinfinityandnan.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.
Attachment #808986 
Flags: review?(nicolas.b.pierron) → review+
Comment 47•6 years ago


(In reply to Dan Gohman [:sunfish] from comment #44) > Created attachment 809126 [details] [diff] [review] > rangeuseaccessors.patch > > (In reply to Nicolas B. Pierron [:nbp] from comment #33) > > Comment on attachment 803951 [details] [diff] [review] > > rangeuseaccessors.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•6 years ago


Comment on attachment 809166 [details] [diff] [review] rangeset.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 falseside 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; > + } stylenit: 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; > + } stylenit: 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) stylenit:  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), stylenit: 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.
Attachment #809166 
Flags: review?(nicolas.b.pierron) → review+
Comment 49•6 years ago


Comment on attachment 809126 [details] [diff] [review] rangeuseaccessors.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.
Attachment #809126 
Flags: review?(nicolas.b.pierron) → review+
Comment 50•6 years ago


Comment on attachment 803954 [details] [diff] [review] rangedoubles.patch Review of attachment 803954 [details] [diff] [review]:  r=me, with the renaming of rangeset patch.
Attachment #803954 
Flags: review?(nicolas.b.pierron) → review+
Updated•6 years ago

Attachment #803956 
Flags: review?(nicolas.b.pierron) → review+
Comment 51•6 years ago


Comment on attachment 803958 [details] [diff] [review] rangeasserttype.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?
Attachment #803958 
Flags: review?(nicolas.b.pierron)
Comment 52•6 years ago


Comment on attachment 803959 [details] [diff] [review] rangeassertinvariants.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.
Attachment #803959 
Flags: review?(nicolas.b.pierron) → review+
Updated•6 years ago

Attachment #803960 
Flags: review?(nicolas.b.pierron) → review+
Comment 53•6 years ago


Comment on attachment 803961 [details] [diff] [review] rangediv.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.
Attachment #803961 
Flags: review?(nicolas.b.pierron)
Comment 54•6 years ago


Comment on attachment 803950 [details] [diff] [review] rangehelperpredicates.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.
Attachment #803950 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 55•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #46) > Comment on attachment 808986 [details] [diff] [review] > rangeinfinityandnan.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 offbyone 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.
Assignee  
Comment 56•6 years ago


(In reply to Nicolas B. Pierron [:nbp] from comment #53) > Comment on attachment 803961 [details] [diff] [review] > rangediv.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.
Attachment #803961 
Attachment is obsolete: true
Attachment #813247 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 57•6 years ago


(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.
Attachment #803950 
Attachment is obsolete: true
Attachment #813264 
Flags: review?(nicolas.b.pierron)
Assignee  
Comment 58•6 years ago


(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.
Flags: needinfo?(nicolas.b.pierron)
Comment 59•6 years ago


(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 offbyone 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.
Flags: needinfo?(nicolas.b.pierron)
Updated•6 years ago

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

Attachment #813264 
Flags: review?(nicolas.b.pierron) → review+
Assignee  
Comment 60•6 years ago


Comment on attachment 803958 [details] [diff] [review] rangeasserttype.patch In comment 59 you agreed with this change, so I'm rerequesting review :).
Attachment #803958 
Flags: review?(nicolas.b.pierron)
Comment 61•6 years ago


Comment on attachment 803958 [details] [diff] [review] rangeasserttype.patch Review of attachment 803958 [details] [diff] [review]:  Thanks for asking again :)
Attachment #803958 
Flags: review?(nicolas.b.pierron) → review+
Comment 62•6 years ago


(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)
Assignee  
Comment 63•6 years ago


> 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/mozillainbound/pushloghtml?changeset=a70ad9d7e0f4 Of course, if you have any further concerns or comments on these changes, please let me know.
Whiteboard: [leave open]
Comment 64•6 years ago


https://hg.mozilla.org/mozillacentral/rev/38ed27acd3b3 https://hg.mozilla.org/mozillacentral/rev/7d523ba71bfc https://hg.mozilla.org/mozillacentral/rev/70147fbd31fb https://hg.mozilla.org/mozillacentral/rev/af3b8a2268a3 https://hg.mozilla.org/mozillacentral/rev/26df5342ca05 https://hg.mozilla.org/mozillacentral/rev/27abc86d9ada https://hg.mozilla.org/mozillacentral/rev/9392f41259bc https://hg.mozilla.org/mozillacentral/rev/ce4fdd6c612f https://hg.mozilla.org/mozillacentral/rev/2de50965c299 https://hg.mozilla.org/mozillacentral/rev/13a8512e04f8 https://hg.mozilla.org/mozillacentral/rev/a70ad9d7e0f4
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
•