Bug 894813 - IonMonkey: Implement dynamic range analysis checking. r=nbp
authorDan Gohman <sunfish@google.com>
Fri, 16 Aug 2013 14:09:49 -0700
changeset 155840 f08e4a699011c5d2e6402c7e6caea33c54e44f40
parent 155839 0c3f3de7638b1fe487c31599a45d5e6f84818e6f
child 155841 70848736309bbeebea31eac92428ed5724923e2d
push id2961
push userlsblakk@mozilla.com
push dateMon, 28 Oct 2013 21:59:28 +0000
treeherdermozilla-beta@73ef4f13486f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnbp
bugs894813
milestone26.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 894813 - IonMonkey: Implement dynamic range analysis checking. r=nbp
js/src/jit/CodeGenerator.cpp
js/src/jit/CodeGenerator.h
js/src/jit/Ion.h
js/src/jit/LIR-Common.h
js/src/jit/LOpcodes.h
js/src/jit/Lowering.cpp
js/src/jit/RangeAnalysis.cpp
js/src/jit/RangeAnalysis.h
js/src/shell/js.cpp
--- a/js/src/jit/CodeGenerator.cpp
+++ b/js/src/jit/CodeGenerator.cpp
@@ -7299,10 +7299,90 @@ CodeGenerator::visitAsmJSCheckOverRecurs
     uintptr_t *limitAddr = &GetIonContext()->runtime->mainThread.nativeStackLimit;
     masm.branchPtr(Assembler::AboveOrEqual,
                    AbsoluteAddress(limitAddr),
                    StackPointer,
                    lir->mir()->onError());
     return true;
 }
 
+bool
+CodeGenerator::visitRangeAssert(LRangeAssert *ins)
+{
+     Register input = ToRegister(ins->input());
+     Range *r = ins->range();
+
+    // Check the lower bound.
+    if (r->lower() != INT32_MIN) {
+        Label success;
+        masm.branch32(Assembler::GreaterThanOrEqual, input, Imm32(r->lower()), &success);
+        masm.breakpoint();
+        masm.bind(&success);
+    }
+
+    // Check the upper bound.
+    if (r->upper() != INT32_MAX) {
+        Label success;
+        masm.branch32(Assembler::LessThanOrEqual, input, Imm32(r->upper()), &success);
+        masm.breakpoint();
+        masm.bind(&success);
+    }
+
+    // For r->isDecimal() and r->exponent(), there's nothing to check, because
+    // if we ended up in the integer range checking code, the value is already
+    // in an integer register in the integer range.
+
+    return true;
+}
+
+bool
+CodeGenerator::visitDoubleRangeAssert(LDoubleRangeAssert *ins)
+{
+     FloatRegister input = ToFloatRegister(ins->input());
+     FloatRegister temp = ToFloatRegister(ins->temp());
+     Range *r = ins->range();
+
+    // Check the lower bound.
+    if (!r->isLowerInfinite()) {
+        Label success;
+        masm.loadConstantDouble(r->lower(), temp);
+        if (r->isUpperInfinite())
+            masm.branchDouble(Assembler::DoubleUnordered, input, input, &success);
+        masm.branchDouble(Assembler::DoubleGreaterThanOrEqual, input, temp, &success);
+        masm.breakpoint();
+        masm.bind(&success);
+    }
+    // Check the upper bound.
+    if (!r->isUpperInfinite()) {
+        Label success;
+        masm.loadConstantDouble(r->upper(), temp);
+        if (r->isLowerInfinite())
+            masm.branchDouble(Assembler::DoubleUnordered, input, input, &success);
+        masm.branchDouble(Assembler::DoubleLessThanOrEqual, input, temp, &success);
+        masm.breakpoint();
+        masm.bind(&success);
+    }
+
+    // This code does not yet check r->isDecimal(). This would require new
+    // assembler interfaces to make rounding instructions available.
+
+    if (!r->isInfinite()) {
+        // Check the bounds implied by the maximum exponent.
+        Label exponentLoOk;
+        masm.loadConstantDouble(pow(2, r->exponent() + 1), temp);
+        masm.branchDouble(Assembler::DoubleUnordered, input, input, &exponentLoOk);
+        masm.branchDouble(Assembler::DoubleLessThanOrEqual, input, temp, &exponentLoOk);
+        masm.breakpoint();
+        masm.bind(&exponentLoOk);
+
+        Label exponentHiOk;
+        masm.loadConstantDouble(-pow(2, r->exponent() + 1), temp);
+        masm.branchDouble(Assembler::DoubleUnordered, input, input, &exponentHiOk);
+        masm.branchDouble(Assembler::DoubleGreaterThanOrEqual, input, temp, &exponentHiOk);
+        masm.breakpoint();
+        masm.bind(&exponentHiOk);
+    }
+
+    return true;
+}
+
 } // namespace ion
 } // namespace js
--- a/js/src/jit/CodeGenerator.h
+++ b/js/src/jit/CodeGenerator.h
@@ -297,16 +297,19 @@ class CodeGenerator : public CodeGenerat
     bool visitSetPropertyIC(OutOfLineUpdateCache *ool, SetPropertyIC *ic);
     bool visitGetElementIC(OutOfLineUpdateCache *ool, GetElementIC *ic);
     bool visitGetElementParIC(OutOfLineUpdateCache *ool, GetElementParIC *ic);
     bool visitSetElementIC(OutOfLineUpdateCache *ool, SetElementIC *ic);
     bool visitBindNameIC(OutOfLineUpdateCache *ool, BindNameIC *ic);
     bool visitNameIC(OutOfLineUpdateCache *ool, NameIC *ic);
     bool visitCallsiteCloneIC(OutOfLineUpdateCache *ool, CallsiteCloneIC *ic);
 
+    bool visitRangeAssert(LRangeAssert *ins);
+    bool visitDoubleRangeAssert(LDoubleRangeAssert *ins);
+
     IonScriptCounts *extractUnassociatedScriptCounts() {
         IonScriptCounts *counts = unassociatedScriptCounts_;
         unassociatedScriptCounts_ = NULL;  // prevent delete in dtor
         return counts;
     }
 
   private:
     bool addGetPropertyCache(LInstruction *ins, RegisterSet liveRegs, Register objReg,
--- a/js/src/jit/Ion.h
+++ b/js/src/jit/Ion.h
@@ -72,16 +72,22 @@ struct IonOptions
     // Default: true
     bool edgeCaseAnalysis;
 
     // Toggles whether Range Analysis is used.
     //
     // Default: true
     bool rangeAnalysis;
 
+    // Whether to enable extra code to perform dynamic validation of
+    // RangeAnalysis results.
+    //
+    // Default: false
+    bool checkRangeAnalysis;
+
     // Toggles whether Unreachable Code Elimination is performed.
     //
     // Default: true
     bool uce;
 
     // Toggles whether Effective Address Analysis is performed.
     //
     // Default: true
@@ -207,16 +213,17 @@ struct IonOptions
         gvnIsOptimistic(true),
         licm(true),
         osr(true),
         limitScriptSize(true),
         registerAllocator(RegisterAllocator_LSRA),
         inlining(true),
         edgeCaseAnalysis(true),
         rangeAnalysis(true),
+        checkRangeAnalysis(false),
         uce(true),
         eaa(true),
         parallelCompilation(false),
 #ifdef CHECK_OSIPOINT_REGISTERS
         checkOsiPointRegisters(false),
 #endif
         baselineUsesBeforeCompile(10),
         usesBeforeCompile(1000),
--- a/js/src/jit/LIR-Common.h
+++ b/js/src/jit/LIR-Common.h
@@ -2,16 +2,17 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef jit_LIR_Common_h
 #define jit_LIR_Common_h
 
+#include "RangeAnalysis.h"
 #include "jit/shared/Assembler-shared.h"
 
 // This file declares LIR instructions that are common to every platform.
 
 namespace js {
 namespace ion {
 
 template <size_t Temps, size_t ExtraUses = 0>
@@ -4937,12 +4938,61 @@ class LAsmJSCheckOverRecursed : public L
   public:
     LIR_HEADER(AsmJSCheckOverRecursed)
 
     MAsmJSCheckOverRecursed *mir() const {
         return mir_->toAsmJSCheckOverRecursed();
     }
 };
 
+class LRangeAssert : public LInstructionHelper<0, 1, 0>
+{
+    Range range_;
+
+  public:
+    LIR_HEADER(RangeAssert)
+
+    LRangeAssert(const LAllocation &input, Range r)
+      : range_(r)
+    {
+        setOperand(0, input);
+    }
+
+    const LAllocation *input() {
+        return getOperand(0);
+    }
+
+    Range *range() {
+        return &range_;
+    }
+};
+
+class LDoubleRangeAssert : public LInstructionHelper<0, 1, 1>
+{
+    Range range_;
+
+  public:
+    LIR_HEADER(DoubleRangeAssert)
+
+    LDoubleRangeAssert(const LAllocation &input, const LDefinition &temp, Range r)
+      : range_(r)
+    {
+        setOperand(0, input);
+        setTemp(0, temp);
+    }
+
+    const LAllocation *input() {
+        return getOperand(0);
+    }
+
+    const LDefinition *temp() {
+        return getTemp(0);
+    }
+
+    Range *range() {
+        return &range_;
+    }
+};
+
 } // namespace ion
 } // namespace js
 
 #endif /* jit_LIR_Common_h */
--- a/js/src/jit/LOpcodes.h
+++ b/js/src/jit/LOpcodes.h
@@ -240,17 +240,19 @@
     _(AsmJSStoreGlobalVar)          \
     _(AsmJSLoadFFIFunc)             \
     _(AsmJSParameter)               \
     _(AsmJSReturn)                  \
     _(AsmJSVoidReturn)              \
     _(AsmJSPassStackArg)            \
     _(AsmJSCall)                    \
     _(AsmJSCheckOverRecursed)       \
-    _(CheckInterruptPar)
+    _(CheckInterruptPar)            \
+    _(RangeAssert)                  \
+    _(DoubleRangeAssert)
 
 #if defined(JS_CPU_X86)
 # include "jit/x86/LOpcodes-x86.h"
 #elif defined(JS_CPU_X64)
 # include "jit/x64/LOpcodes-x64.h"
 #elif defined(JS_CPU_ARM)
 # include "jit/arm/LOpcodes-arm.h"
 #endif
--- a/js/src/jit/Lowering.cpp
+++ b/js/src/jit/Lowering.cpp
@@ -2938,16 +2938,35 @@ LIRGenerator::visitInstruction(MInstruct
 #endif
 
     // If no safepoint was created, there's no need for an OSI point.
     if (LOsiPoint *osiPoint = popOsiPoint()) {
         if (!add(osiPoint))
             return false;
     }
 
+    // Check the computed range for this instruction, if the option is set. Note
+    // that this code is quite invasive; it adds numerous additional
+    // instructions for each MInstruction with a computed range, and it uses
+    // registers, so it also affects register allocation.
+    if (js_IonOptions.checkRangeAnalysis) {
+        if (Range *r = ins->range()) {
+           switch (ins->type()) {
+           case MIRType_Int32:
+               add(new LRangeAssert(useRegisterAtStart(ins), *r));
+               break;
+           case MIRType_Double:
+               add(new LDoubleRangeAssert(useRegister(ins), tempFloat(), *r));
+               break;
+           default:
+               break;
+           }
+        }
+    }
+
     return true;
 }
 
 bool
 LIRGenerator::definePhis()
 {
     size_t lirIndex = 0;
     MBasicBlock *block = current->mir();
--- a/js/src/jit/RangeAnalysis.cpp
+++ b/js/src/jit/RangeAnalysis.cpp
@@ -156,44 +156,44 @@ RangeAnalysis::addBetaNobes()
 
         if (left->isConstant() && left->toConstant()->value().isInt32()) {
             bound = left->toConstant()->value().toInt32();
             val = right;
             jsop = analyze::ReverseCompareOp(jsop);
         } else if (right->isConstant() && right->toConstant()->value().isInt32()) {
             bound = right->toConstant()->value().toInt32();
             val = left;
-        } else {
+        } else if (left->type() == MIRType_Int32 && right->type() == MIRType_Int32) {
             MDefinition *smaller = NULL;
             MDefinition *greater = NULL;
             if (jsop == JSOP_LT) {
                 smaller = left;
                 greater = right;
             } else if (jsop == JSOP_GT) {
                 smaller = right;
                 greater = left;
             }
             if (smaller && greater) {
                 MBeta *beta;
-                beta = MBeta::New(smaller, new Range(JSVAL_INT_MIN, JSVAL_INT_MAX-1,
-                                                     smaller->type() != MIRType_Int32,
-                                                     Range::MaxDoubleExponent));
+                beta = MBeta::New(smaller, new Range(JSVAL_INT_MIN, JSVAL_INT_MAX-1));
                 block->insertBefore(*block->begin(), beta);
                 replaceDominatedUsesWith(smaller, beta, block);
                 IonSpew(IonSpew_Range, "Adding beta node for smaller %d", smaller->id());
-                beta = MBeta::New(greater, new Range(JSVAL_INT_MIN+1, JSVAL_INT_MAX,
-                                                     greater->type() != MIRType_Int32,
-                                                     Range::MaxDoubleExponent));
+                beta = MBeta::New(greater, new Range(JSVAL_INT_MIN+1, JSVAL_INT_MAX));
                 block->insertBefore(*block->begin(), beta);
                 replaceDominatedUsesWith(greater, beta, block);
                 IonSpew(IonSpew_Range, "Adding beta node for greater %d", greater->id());
             }
             continue;
+        } else {
+            continue;
         }
 
+        // At this point, one of the operands if the compare is a constant, and
+        // val is the other operand.
         JS_ASSERT(val);
 
 
         Range comp;
         if (val->type() == MIRType_Int32)
             comp.setInt32();
         switch (jsop) {
           case JSOP_LE:
@@ -848,16 +848,22 @@ MConstant::computeRange()
         // Extract the integral part.
         int64_t integral = ToInt64(d);
         // Extract the decimal part.
         double rest = d - (double) integral;
         // Estimate the smallest integral boundaries.
         //   Safe double comparisons, because there is no precision loss.
         int64_t l = integral - ((rest < 0) ? 1 : 0);
         int64_t h = integral + ((rest > 0) ? 1 : 0);
+        // If we adjusted into a new exponent range, adjust exp accordingly.
+        if ((rest < 0 && (l == INT64_MIN || IsPowerOfTwo(Abs(l)))) ||
+            (rest > 0 && (h == INT64_MIN || IsPowerOfTwo(Abs(h)))))
+        {
+            ++exp;
+        }
         setRange(new Range(l, h, (rest != 0), exp));
     } else {
         // This double has a precision loss. This also mean that it cannot
         // encode any decimals.
         if (IsNegative(d))
             setRange(new Range(RANGE_INF_MIN, RANGE_INF_MIN, false, exp));
         else
             setRange(new Range(RANGE_INF_MAX, RANGE_INF_MAX, false, exp));
@@ -979,18 +985,18 @@ void
 MAbs::computeRange()
 {
     if (specialization_ != MIRType_Int32 && specialization_ != MIRType_Double)
         return;
 
     Range other(getOperand(0));
     setRange(Range::abs(&other));
 
-    if (implicitTruncate_ && !range()->isInt32())
-        setRange(new Range(INT32_MIN, INT32_MAX));
+    if (implicitTruncate_)
+        range()->wrapAroundToInt32();
 }
 
 void
 MMinMax::computeRange()
 {
     if (specialization_ != MIRType_Int32 && specialization_ != MIRType_Double)
         return;
 
@@ -1004,63 +1010,67 @@ MAdd::computeRange()
 {
     if (specialization() != MIRType_Int32 && specialization() != MIRType_Double)
         return;
     Range left(getOperand(0));
     Range right(getOperand(1));
     Range *next = Range::add(&left, &right);
     setRange(next);
 
-    if (isTruncated() && !range()->isInt32())
-        setRange(new Range(INT32_MIN, INT32_MAX));
+    if (isTruncated())
+        range()->wrapAroundToInt32();
 }
 
 void
 MSub::computeRange()
 {
     if (specialization() != MIRType_Int32 && specialization() != MIRType_Double)
         return;
     Range left(getOperand(0));
     Range right(getOperand(1));
     Range *next = Range::sub(&left, &right);
     setRange(next);
 
-    if (isTruncated() && !range()->isInt32())
-        setRange(new Range(INT32_MIN, INT32_MAX));
+    if (isTruncated())
+        range()->wrapAroundToInt32();
 }
 
 void
 MMul::computeRange()
 {
     if (specialization() != MIRType_Int32 && specialization() != MIRType_Double)
         return;
     Range left(getOperand(0));
     Range right(getOperand(1));
     if (canBeNegativeZero())
         canBeNegativeZero_ = Range::negativeZeroMul(&left, &right);
     setRange(Range::mul(&left, &right));
 
     // Truncated multiplications could overflow in both directions
-    if (isTruncated() && !range()->isInt32())
-        setRange(new Range(INT32_MIN, INT32_MAX));
+    if (isTruncated())
+        range()->wrapAroundToInt32();
 }
 
 void
 MMod::computeRange()
 {
     if (specialization() != MIRType_Int32 && specialization() != MIRType_Double)
         return;
     Range lhs(getOperand(0));
     Range rhs(getOperand(1));
 
     // If either operand is a NaN, the result is NaN. This also conservatively
     // handles Infinity cases.
     if (lhs.isInfinite() || rhs.isInfinite())
         return;
 
+    // If RHS can be zero, the result can be NaN.
+    if (rhs.lower() <= 0 && rhs.upper() >= 0)
+        return;
+
     // Math.abs(lhs % rhs) == Math.abs(lhs) % Math.abs(rhs).
     // First, the absolute value of the result will always be less than the
     // absolute value of rhs. (And if rhs is zero, the result is NaN).
     int64_t a = Abs<int64_t>(rhs.lower());
     int64_t b = Abs<int64_t>(rhs.upper());
     if (a == 0 && b == 0)
         return;
     int64_t rhsAbsBound = Max(a-1, b-1);
@@ -1658,66 +1668,60 @@ MConstant::truncate()
 }
 
 bool
 MAdd::truncate()
 {
     // Remember analysis, needed for fallible checks.
     setTruncated(true);
 
-    // Modify the instruction if needed.
-    if (type() != MIRType_Double)
-        return false;
+    if (type() == MIRType_Double || type() == MIRType_Int32) {
+        specialization_ = MIRType_Int32;
+        setResultType(MIRType_Int32);
+        if (range())
+            range()->wrapAroundToInt32();
+        return true;
+    }
 
-    specialization_ = MIRType_Int32;
-    setResultType(MIRType_Int32);
-    if (range())
-        range()->wrapAroundToInt32();
-    return true;
+    return false;
 }
 
 bool
 MSub::truncate()
 {
     // Remember analysis, needed for fallible checks.
     setTruncated(true);
 
-    // Modify the instruction if needed.
-    if (type() != MIRType_Double)
-        return false;
+    if (type() == MIRType_Double || type() == MIRType_Int32) {
+        specialization_ = MIRType_Int32;
+        setResultType(MIRType_Int32);
+        if (range())
+            range()->wrapAroundToInt32();
+        return true;
+    }
 
-    specialization_ = MIRType_Int32;
-    setResultType(MIRType_Int32);
-    if (range())
-        range()->wrapAroundToInt32();
-    return true;
+    return false;
 }
 
 bool
 MMul::truncate()
 {
     // Remember analysis, needed to remove negative zero checks.
     setTruncated(true);
 
-    // Modify the instruction.
-    bool truncated = type() == MIRType_Int32;
-    if (type() == MIRType_Double) {
+    if (type() == MIRType_Double || type() == MIRType_Int32) {
         specialization_ = MIRType_Int32;
         setResultType(MIRType_Int32);
-        truncated = true;
-        JS_ASSERT(range());
+        setCanBeNegativeZero(false);
+        if (range())
+            range()->wrapAroundToInt32();
+        return true;
     }
 
-    if (truncated && range()) {
-        range()->wrapAroundToInt32();
-        setTruncated(true);
-        setCanBeNegativeZero(false);
-    }
-
-    return truncated;
+    return false;
 }
 
 bool
 MDiv::truncate()
 {
     // Remember analysis, needed to remove negative zero checks.
     setTruncated(true);
 
--- a/js/src/jit/RangeAnalysis.h
+++ b/js/src/jit/RangeAnalysis.h
@@ -169,16 +169,19 @@ class Range : public TempObject {
     Range(int64_t l, int64_t h, bool d = false, uint16_t e = MaxInt32Exponent)
         : lower_infinite_(true),
           upper_infinite_(true),
           decimal_(d),
           max_exponent_(e),
           symbolicLower_(NULL),
           symbolicUpper_(NULL)
     {
+        JS_ASSERT(e >= (h == INT64_MIN ? MaxDoubleExponent : mozilla::FloorLog2(mozilla::Abs(h))));
+        JS_ASSERT(e >= (l == INT64_MIN ? MaxDoubleExponent : mozilla::FloorLog2(mozilla::Abs(l))));
+
         setLowerInit(l);
         setUpperInit(h);
         rectifyExponent();
         JS_ASSERT_IF(lower_infinite_, lower_ == JSVAL_INT_MIN);
         JS_ASSERT_IF(upper_infinite_, upper_ == JSVAL_INT_MAX);
     }
 
     Range(const Range &other)
--- a/js/src/shell/js.cpp
+++ b/js/src/shell/js.cpp
@@ -5087,16 +5087,19 @@ ProcessArgs(JSContext *cx, JSObject *obj
          if (strcmp(str, "on") == 0)
              ion::js_IonOptions.rangeAnalysis = true;
          else if (strcmp(str, "off") == 0)
              ion::js_IonOptions.rangeAnalysis = false;
          else
              return OptionFailure("ion-range-analysis", str);
      }
 
+    if (op->getBoolOption("ion-check-range-analysis"))
+        ion::js_IonOptions.checkRangeAnalysis = true;
+
     if (const char *str = op->getStringOption("ion-inlining")) {
         if (strcmp(str, "on") == 0)
             ion::js_IonOptions.inlining = true;
         else if (strcmp(str, "off") == 0)
             ion::js_IonOptions.inlining = false;
         else
             return OptionFailure("ion-inlining", str);
     }
@@ -5372,16 +5375,18 @@ main(int argc, char **argv, char **envp)
                                "  pessimistic: use pessimistic GVN\n"
                                "  optimistic: (default) use optimistic GVN")
         || !op.addStringOption('\0', "ion-licm", "on/off",
                                "Loop invariant code motion (default: on, off to disable)")
         || !op.addStringOption('\0', "ion-edgecase-analysis", "on/off",
                                "Find edge cases where Ion can avoid bailouts (default: on, off to disable)")
         || !op.addStringOption('\0', "ion-range-analysis", "on/off",
                                "Range analysis (default: off, on to enable)")
+        || !op.addBoolOption('\0', "ion-check-range-analysis",
+                               "Range analysis checking")
         || !op.addStringOption('\0', "ion-inlining", "on/off",
                                "Inline methods where possible (default: on, off to disable)")
         || !op.addStringOption('\0', "ion-osr", "on/off",
                                "On-Stack Replacement (default: on, off to disable)")
         || !op.addStringOption('\0', "ion-limit-script-size", "on/off",
                                "Don't compile very large scripts (default: on, off to disable)")
         || !op.addIntOption('\0', "ion-uses-before-compile", "COUNT",
                             "Wait for COUNT calls or iterations before compiling "