1051674 - Optimize Math.Ceil using Range Analysis

Status: NEW

(Core :: JavaScript Engine: JIT, enhancement, P5)

Description

[Julien Levesy]

Using Range Analysis we're now able to : 
- Authorize truncation to flow through Math.Ceil if we ensure that given operand is in ]-Inf, 0[
- Redefine as no-op if output is truncated to Int32 
- Use range data to remove if checks if given operand is in ]-Inf, -1[ U ]O, +Inf[

Comment 1

[Julien Levesy]

Attachment: bug1051674part1.patch

Comment 2

[Julien Levesy]

Comment on attachment 8470646 [details] [diff] [review]
bug1051674part1.patch

># HG changeset patch
># User Julien Levesy <[e-mail]>
>
>Bug1051674: Authorize truncation forwarding in Math.ceil; r=nbp
>
>diff --git a/js/src/jit/Lowering.cpp b/js/src/jit/Lowering.cpp
>index 1b9af34..5165d58 100644
>--- a/js/src/jit/Lowering.cpp
>+++ b/js/src/jit/Lowering.cpp
>@@ -1211,17 +1211,17 @@ LIRGenerator::visitFloor(MFloor *ins)
>         return false;
>     return define(lir, ins);
> }
> 
> bool
> LIRGenerator::visitCeil(MCeil *ins)
> {
>     MIRType type = ins->input()->type();
>-    JS_ASSERT(IsFloatingPointType(type));
>+    JS_ASSERT(IsNumberType(type));
> 
>     if (type == MIRType_Double) {
>         LCeil *lir = new(alloc()) LCeil(useRegister(ins->input()));
>         if (!assignSnapshot(lir, Bailout_Round))
>             return false;
>         return define(lir, ins);
>     }
> 
>diff --git a/js/src/jit/MIR.h b/js/src/jit/MIR.h
>index 40d2fa1..4b41311 100644
>--- a/js/src/jit/MIR.h
>+++ b/js/src/jit/MIR.h
>@@ -9207,23 +9207,28 @@ class MFloor
> };
> 
> // Inlined version of Math.ceil().
> class MCeil
>   : public MUnaryInstruction,
>     public FloatingPointPolicy<0>
> {
>     explicit MCeil(MDefinition *num)
>-      : MUnaryInstruction(num)
>+      : MUnaryInstruction(num),
>+      authorizeTruncation_(false),
>+      outputTruncation_(NoTruncate)
>     {
>         setResultType(MIRType_Int32);
>         setPolicyType(MIRType_Double);
>         setMovable();
>     }
> 
>+    bool authorizeTruncation_;
>+    TruncateKind outputTruncation_;
>+
>   public:
>     INSTRUCTION_HEADER(Ceil)
> 
>     static MCeil *New(TempAllocator &alloc, MDefinition *num) {
>         return new(alloc) MCeil(num);
>     }
> 
>     AliasSet getAliasSet() const {
>@@ -9240,16 +9245,22 @@ class MCeil
>     bool isConsistentFloat32Use(MUse *use) const {
>         return true;
>     }
> #endif
>     bool congruentTo(const MDefinition *ins) const {
>         return congruentIfOperandsEqual(ins);
>     }
>     void computeRange(TempAllocator &alloc);
>+    void setTruncateKind(TruncateKind kind) {
>+        outputTruncation_ = kind;
>+    }
>+    void collectRangeInfoPreTrunc();
>+    TruncateKind operandTruncateKind(size_t index) const;
>+    bool truncate(TruncateKind kind);
> };
> 
> // Inlined version of Math.round().
> class MRound
>   : public MUnaryInstruction,
>     public FloatingPointPolicy<0>
> {
>     explicit MRound(MDefinition *num)
>diff --git a/js/src/jit/RangeAnalysis.cpp b/js/src/jit/RangeAnalysis.cpp
>index 1473f80..ce96a41 100644
>--- a/js/src/jit/RangeAnalysis.cpp
>+++ b/js/src/jit/RangeAnalysis.cpp
>@@ -2271,16 +2271,29 @@ MDiv::truncate(TruncateKind kind)
>         return true;
>     }
> 
>     // No modifications.
>     return false;
> }
> 
> bool
>+MCeil::truncate(TruncateKind kind)
>+{
>+    setTruncateKind(kind);
>+
>+    if (authorizeTruncation_) {
>+        setResultType(MIRType_Int32);
>+        return true;
>+    }
>+
>+    return false;
>+}
>+
>+bool
> MMod::truncate(TruncateKind kind)
> {
>     // Remember analysis, needed to remove negative zero checks.
>     setTruncateKind(kind);
> 
>     // As for division, handle unsigned modulus with a truncated result.
>     if (type() == MIRType_Double || type() == MIRType_Int32) {
>         specialization_ = MIRType_Int32;
>@@ -2376,16 +2389,22 @@ MSub::operandTruncateKind(size_t index) const
> MDefinition::TruncateKind
> MMul::operandTruncateKind(size_t index) const
> {
>     // See the comment in MAdd::operandTruncateKind.
>     return Min(truncateKind(), IndirectTruncate);
> }
> 
> MDefinition::TruncateKind
>+MCeil::operandTruncateKind(size_t index) const
>+{
>+    return authorizeTruncation_ && outputTruncation_ >= IndirectTruncate ? outputTruncation_ : NoTruncate;
>+}
>+
>+MDefinition::TruncateKind
> MToDouble::operandTruncateKind(size_t index) const
> {
>     // MToDouble propagates its truncate kind to its operand.
>     return truncateKind();
> }
> 
> MDefinition::TruncateKind
> MStoreTypedArrayElement::operandTruncateKind(size_t index) const
>@@ -2774,16 +2793,24 @@ MMod::collectRangeInfoPreTrunc()
>     if (lhsRange.isFiniteNonNegative())
>         canBeNegativeDividend_ = false;
>     if (!rhsRange.canBeZero())
>         canBeDivideByZero_ = false;
> 
> }
> 
> void
>+MCeil::collectRangeInfoPreTrunc()
>+{
>+    Range inputRange(input());
>+    if (inputRange.isFiniteNegative())
>+        authorizeTruncation_ = true;
>+}
>+
>+void
> MToInt32::collectRangeInfoPreTrunc()
> {
>     Range inputRange(input());
>     if (!inputRange.canBeZero())
>         canBeNegativeZero_ = false;
> }
> 
> void

Comment 3

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8470646 [details] [diff] [review]
bug1051674part1.patch

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

::: js/src/jit/MIR.h
@@ +9213,5 @@
>  {
>      explicit MCeil(MDefinition *num)
> +      : MUnaryInstruction(num),
> +      authorizeTruncation_(false),
> +      outputTruncation_(NoTruncate)

style-nit: align fields names.

@@ +9220,5 @@
>          setPolicyType(MIRType_Double);
>          setMovable();
>      }
>  
> +    bool authorizeTruncation_;

There is no need for the authorizeTruncation_ flag, see below.

::: js/src/jit/RangeAnalysis.cpp
@@ +2801,5 @@
> +MCeil::collectRangeInfoPreTrunc()
> +{
> +    Range inputRange(input());
> +    if (inputRange.isFiniteNegative())
> +        authorizeTruncation_ = true;

Range accesses are fine in the ::truncate function, and the authorization part can be kept as part of the outputTruncation_ flag.

Comment 4

[franck.farmer456]

Hello,
Has this bug been fixed or is it still open? If it is open, can I work on it for my first bug?

Comment 5

[Nicolas B. Pierron [:nbp]]

This issue is still open, feel free to work on it.