Closed
Bug 841666
Opened 12 years ago
Closed 12 years ago
IonMonkey: Support double exponent range analysis for multiplication truncation.
Categories
(Core :: JavaScript Engine, defect)
Core
JavaScript Engine
Tracking
()
RESOLVED
FIXED
mozilla22
People
(Reporter: nbp, Assigned: nbp)
References
(Blocks 1 open bug)
Details
Attachments
(1 file, 3 obsolete files)
71.42 KB,
patch

h4writer
:
review+

Details  Diff  Splinter Review 
PdfJS octane benchmark suffers from a local double conversion of int32>double, double multiplciation, double addition, and a truncation. This is located in pdfjs.js:16635 decrypt function. This double conversion are executed 119k times per run of PdfJS, which runs 21 times on my computer with octane harness. Using a range analysis on the exponent will give hints for moving the truncation up to the multiplication operation, which can then safely ignore the overflow case reported by the monitoring of the bytecode.
Assignee  
Comment 1•12 years ago


This Bug is some kind of followup of Bug 809472, where we need to push the truncation back to the multiplication. The surprising thing is that adding manually explicit truncate on the multiplication result keeps doing some double multiplication. This bug need to add an exponent range, such as (part 1) we keep track of the estimated range of value that are manipulated, and such as we can flag the addition as being truncatefriendly. And then (part 2) we populate the truncate flag back through the add & mul operations, as done just after the type analysis.
Assignee  
Comment 2•12 years ago


This patch add exponent range analysis to double & int expression. Alone this patch is likely to regress performances as it tries to sanitized the range analysis by making a distinction between the range of an operation and its truncated value.
Attachment #714496 
Flags: review?(hv1989)
Comment 4•12 years ago


Comment on attachment 714496 [details] [diff] [review] [part 1] Provide Double exponent range analysis. Review of attachment 714496 [details] [diff] [review]:  That was also the solution I had in my mind... I now have a basic idea how it works. I'll look more indepth tomorrow. Will mostly be nits to improve readability ;). E.g. It took me a while before I understand "KeepInf" and it's KeepMode. Also the names are really confusing and not intuitive ...
Comment 5•12 years ago


Comment on attachment 714496 [details] [diff] [review] [part 1] Provide Double exponent range analysis. Review of attachment 714496 [details] [diff] [review]:  ::: js/src/ion/RangeAnalysis.cpp @@ +386,4 @@ > } > > +static inline bool > +AnyInf(const Range *lhs, const Range *rhs) s/AnyInf/HasInfinite/ @@ +408,5 @@ > + return new Range( > + KeepInf(LLhs  URhs  LRes, lhs, rhs, (int64_t)lhs>lower_  (int64_t)rhs>upper_), > + KeepInf(ULhs  LRhs  URes, lhs, rhs, (int64_t)lhs>upper_  (int64_t)rhs>lower_), > + lhs>fractional_part_  rhs>fractional_part_, > + Max(lhs>upper_exponent_, rhs>upper_exponent_) + 1); I would rather not use KeefInf. I think the code is easier to read and understand without it. Also I would recommend to use variable names. It is really important that this code is quickly readable and understandable, because it is easy to make a mistake. I think using this shorthands LLhs won't help. Also I was confused and thinking to much about Unsigned Right shift etc... Range * Range::sub(const Range *lhs, const Range *rhs) { int64_t lower = (int64_t)lhs>lower_  (int64_t)rhs>upper_; if (lhs>isLowerInfinite()  rhs>isUpperInfinite()) lower = RANGE_INF_MIN; int64_t upper = (int64_t)lhs>upper_  (int64_t)rhs>lower_; if (lhs>isUpperInfinite()  rhs>isLowerInfinite()) upper = RANGE_INF_MAX; bool decimal = lhs>decimal_  rhs>decimal_; uint16_t exponent = Max(lhs>upper_exponent_, rhs>upper_exponent_) + 1; return new Range(lower, upper, decimal, exponent); } NOTE: I think the exponent range for sub is also wrong in this calculations !! ::: js/src/ion/RangeAnalysis.h @@ +92,5 @@ > > class Range : public TempObject { > + public: > + // 52 bits of mantissa, so 2^52+1 cannot be represented without loss. > + static const uint16_t MaxIntExponent = 52; The three Max*Exponent is getting confusing. Could your rename this one to: s/MaxIntExponent/MaxExponentWithoutPrecisionLoss/ @@ +99,5 @@ > + // which needs 32 bits. > + static const uint16_t MaxInt32Exponent = 31; > + > + // 11 bits of signed exponent, so the max is encoded on 10 bits. > + static const uint16_t MaxExponent = (1 << 11)  1; This is the maximum Double/Number we can encode, right? Renaming this to the following should make that clear: s/MaxExponent/MaxDoubleExponent/ (MaxNumberExponent would also be good) @@ +133,4 @@ > int32_t upper_; > bool upper_infinite_; > > + bool fractional_part_; fractional_ or decimal_ but use the same name accross the whole file. isFloat, fractional and fractional_part_ is used => isDecimal, decimal and decimal_ ;) @@ +133,5 @@ > int32_t upper_; > bool upper_infinite_; > > + bool fractional_part_; > + uint16_t upper_exponent_; The "upper" part is confusing. Suddenly when reading through the file, I thought the upper stood for the exponent we saw in the positive range. This exponent combines the maximum upper and lower exponent we saw... Is there a reason not to create upper_exponent and lower_exponent? I don't think this is a lot of extra work/overhead and would give us more accurate ranges for "sub"
Attachment #714496 
Flags: review?(hv1989)
Comment 6•12 years ago


Ah and another question. This bug aims to remove the 20 addition limit and increase the potential of truncating constant doubles right?
Assignee  
Comment 7•12 years ago


(In reply to Hannes Verschore [:h4writer] from comment #6) > Ah and another question. This bug aims to remove the 20 addition limit and > increase the potential of truncating constant doubles right? This is a side effect of it. It aim at handling (a * b + c) & 0xffff, such as we do Int32 multiplication and additions.
Assignee  
Comment 8•12 years ago


 Remove analyszeTruncateBackward. (replaced by RangeAnalysis::truncateBackward)  Remove isBigInt computation. (replaced by hasRoundingErrors)  Replace intvalues implicitTruncate flags.  Add decimal & max_exponent_ to Range analysis.  Support Double as part of range analysis spectrum (especially for MConstant)  Truncate operations based on the result of range analysis.
Attachment #714496 
Attachment is obsolete: true
Attachment #716674 
Flags: review?(hv1989)
Assignee  
Comment 9•12 years ago


This improve PdfJS by ~1% on my computer. Regress kraken sha256 by ~1.6% because AddD(BitXor(…, …), BitXor(…, …)) was optimized as an Int addition without being truncated. Nothing interesting on sunspider. Octane is too noisy to spot any improvement / regressions with a few runs.
Assignee  
Comment 10•12 years ago


Delta:  Apply nits.  Add a test case.  Assert assumptions at the creation of the Range structure.
Attachment #716674 
Attachment is obsolete: true
Attachment #716674 
Flags: review?(hv1989)
Attachment #716916 
Flags: review?(hv1989)
Assignee  
Comment 11•12 years ago


(In reply to Nicolas B. Pierron [:pierron] [:nbp] from comment #9) > This improve PdfJS by ~1% on my computer. > Regress kraken sha256 by ~1.6% because AddD(BitXor(…, …), BitXor(…, …)) was > optimized as an Int addition without being truncated. The same regression affect pbkdf2, with the same regression :( Unfortunately this is a wrong behaviour as highlighted by the test case added to the current patch. I've open Bug 843902 to investigate the JM issue which is unrelated to Ion, but I still want to add the JM test case as it look similar and might prevent adding a similar bug to the baseline compiler or to this patch.
Comment 12•12 years ago


Comment on attachment 716916 [details] [diff] [review] Use exponent overestimation to truncate operations. Review of attachment 716916 [details] [diff] [review]:  Did a quick pass. Will review more indepth later today. ::: js/src/ion/RangeAnalysis.cpp @@ +380,3 @@ > { > + return lhs>isLowerInfinite()  lhs>isUpperInfinite()  > + rhs>isLowerInfinite()  rhs>isUpperInfinite(); Align both lines @@ +444,5 @@ > > Range * > Range::mul(const Range *lhs, const Range *rhs) > { > + bool fractional = lhs>isDecimal()  rhs>isDecimal(); s/fractional/decimal/ @@ +561,5 @@ > MConstant::computeRange() > { > if (type() == MIRType_Int32) > setRange(new Range(value().toInt32(), value().toInt32())); > + else if (type() == MIRType_Double) { If else has brackets, the if needs to have them too @@ +1335,5 @@ > +bool > +MMod::truncateOperand(size_t index) const > +{ > + return false; > +} The default for truncateOperand is "return false";. I.e. we don't have to override it for MDiv/MMod @@ +1404,5 @@ > + > +// This is similar to TypeAnalyzer::specializeTruncatedInstructions, except that > +// this version is based on the range analysis and not on an approximation of > +// the exponent (aka. isBigInt) which is limited to the number and kind of > +// consecutive instructions. This comment refers to code that is removed. We shouldn't do that. Only refer to existing code. I would suggest explaining what specializeTruncatedInstructions did. ::: js/src/ion/RangeAnalysis.h @@ +344,5 @@ > + // > + // Note: > + // exponent of JSVAL_INT_MIN == 32 > + // exponent of JSVAL_INT_MAX == 31 > + inline void rectifyExponent() { why not "computeExponent" instead of "rectifyExponent" ::: js/src/jittest/tests/ion/rangeanalysis.js @@ +1,2 @@ > +// jittest nojm > +// Disable JM until it got investigated in Bug ######. Bugnummer must definitely get added!
Assignee  
Comment 13•12 years ago


(In reply to Hannes Verschore [:h4writer] from comment #12) > Comment on attachment 716916 [details] [diff] [review] > Use exponent overestimation to truncate operations. > > Review of attachment 716916 [details] [diff] [review]: >  > @@ +1335,5 @@ > > +bool > > +MMod::truncateOperand(size_t index) const > > +{ > > + return false; > > +} > > The default for truncateOperand is "return false";. I.e. we don't have to > override it for MDiv/MMod Because I am already overriding MBinaryArithInstruction, but as there is only 5 Arith Instructions, I will move it into each which would be less errorprone. > ::: js/src/ion/RangeAnalysis.h > @@ +344,5 @@ > > + // > > + // Note: > > + // exponent of JSVAL_INT_MIN == 32 > > + // exponent of JSVAL_INT_MAX == 31 > > + inline void rectifyExponent() { > > why not "computeExponent" instead of "rectifyExponent" Because computeExponent implies that you might be able to compute the exponent for any value, including nonInt32 values. Where rectify is used to refine the exponent in the Int32 range of value.
Assignee  
Comment 14•12 years ago


Delta:  Apply nits.  Reduce indentation level of MConstant::computeRange.
Attachment #716916 
Attachment is obsolete: true
Attachment #716916 
Flags: review?(hv1989)
Attachment #717228 
Flags: review?(hv1989)
Comment 15•12 years ago


Comment on attachment 717228 [details] [diff] [review] Use exponent overestimation to truncate operations. Review of attachment 717228 [details] [diff] [review]:  Nice work! ::: js/src/ion/MIR.h @@ +338,5 @@ > virtual MDefinition *foldsTo(bool useValueNumbers); > virtual void analyzeEdgeCasesForward(); > virtual void analyzeEdgeCasesBackward(); > + > + virtual bool truncateOperation(); s/truncateOperation()/truncate()/ @@ +340,5 @@ > virtual void analyzeEdgeCasesBackward(); > + > + virtual bool truncateOperation(); > + virtual bool truncateOperand(size_t index) const; > + This name of this method implies the operand will get truncated when calling. But this is only checking if the operand truncates. s/truncateOperand/operandTruncated()/ ::: js/src/ion/RangeAnalysis.cpp @@ +1345,5 @@ > +} > + > +// Look for all observables (nonresume point) uses, and check that each > +// operation using the result of the candidate are working truncating the > +// corresponding input. Please rephrase? Content is correct, but it's hard to read. @@ +1370,5 @@ > +static void > +RemoveTruncatesOnOutput(MInstruction *truncated) > +{ > + JS_ASSERT(truncated>type() == MIRType_Int32); > + JS_ASSERT(!truncated>range()  truncated>range()>isInt32()); JS_ASSERT_IF(truncated>range(), truncated>range()>isInt32()); If I read this correctly @@ +1414,5 @@ > +// > +// We iterate backward because it is likely that a truncated operation truncates > +// some of its operands. > +bool > +RangeAnalysis::truncateBackward() I see no reason to include "backward" in the method name. I know this has historically grown into the name, because edge case analysis had a forward and backward pass. But now this distinction isn't important to know. s/truncateBackward()/truncateAnalysis()/ @@ +1430,5 @@ > + continue; > + > + if (!AllUsesTruncate(*iter)) > + continue; > + SetImplicitTruncate(*iter); Don't see the need for this "SetImplicitTruncate" function. I would recommend adding it as part of truncateOperation() on Add/Sub/Mod/Mul/Div
Attachment #717228 
Flags: review?(hv1989) → review+
Assignee  
Comment 17•12 years ago


https://hg.mozilla.org/integration/mozillainbound/rev/6a930768eb82
Comment 18•12 years ago


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