841666 - IonMonkey: Support double exponent range analysis for multiplication truncation.

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicolas B. Pierron [:nbp]]

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 byte-code.

Comment 1

[Nicolas B. Pierron [:nbp]]

This Bug is some kind of follow-up 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 truncate-friendly. And then (part 2) we populate the truncate flag back through the add & mul operations, as done just after the type analysis.

Comment 2

[Nicolas B. Pierron [:nbp]]

Attachment: [part 1] Provide Double exponent range analysis.

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.

Comment 4

[Hannes Verschore [:h4writer]]

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 in-depth 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

[Hannes Verschore [:h4writer]]

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"

Comment 6

[Hannes Verschore [:h4writer]]

Ah and another question. This bug aims to remove the 20 addition limit and increase the potential of truncating constant doubles right?

Comment 7

[Nicolas B. Pierron [:nbp]]

(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.

Comment 8

[Nicolas B. Pierron [:nbp]]

Attachment: Use exponent over-estimation to truncate operations.

- Remove analyszeTruncateBackward. (replaced by RangeAnalysis::truncateBackward)
- Remove isBigInt computation. (replaced by hasRoundingErrors)
- Replace int-values 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.

Comment 9

[Nicolas B. Pierron [:nbp]]

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.

Comment 10

[Nicolas B. Pierron [:nbp]]

Attachment: Use exponent over-estimation to truncate operations.

Delta:
- Apply nits.
- Add a test case.
- Assert assumptions at the creation of the Range structure.

Comment 11

[Nicolas B. Pierron [:nbp]]

(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

[Hannes Verschore [:h4writer]]

Comment on attachment 716916 [details] [diff] [review]
Use exponent over-estimation to truncate operations.

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

Did a quick pass. Will review more in-depth 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/jit-test/tests/ion/range-analysis.js
@@ +1,2 @@
> +// |jit-test| no-jm
> +// Disable JM until it got investigated in Bug ######.

Bugnummer must definitely get added!

Comment 13

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #12)
> Comment on attachment 716916 [details] [diff] [review]
> Use exponent over-estimation 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 error-prone.

> ::: 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 non-Int32 values.  Where rectify is used to refine the exponent in the Int32 range of value.

Comment 14

[Nicolas B. Pierron [:nbp]]

Attachment: Use exponent over-estimation to truncate operations.

Delta:
 - Apply nits.
 - Reduce indentation level of MConstant::computeRange.

Comment 15

[Hannes Verschore [:h4writer]]

Comment on attachment 717228 [details] [diff] [review]
Use exponent over-estimation 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 (non-resume 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

Comment 17

[Nicolas B. Pierron [:nbp]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/6a930768eb82

Comment 18

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/6a930768eb82