Bug 809472: Add truncate analysis for MMul, r=mjrosenb
authorHannes Verschore <hv1989@gmail.com>
Thu, 08 Nov 2012 14:35:26 +0100
changeset 112683 9f3a01124d8cbf78db44ddf7ffa9f354b67f73c9
parent 112682 b4bc5389b4fffaa72f8340067a7f5e7e885f4490
child 112684 2f116ae5e387eedb70e0cc2ffc86536da29294ab
push id17717
push userhv1989@gmail.com
push dateThu, 08 Nov 2012 13:38:20 +0000
treeherdermozilla-inbound@9f3a01124d8c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmjrosenb
bugs809472
milestone19.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 809472: Add truncate analysis for MMul, r=mjrosenb
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/ion/RangeAnalysis.cpp
js/src/ion/RangeAnalysis.h
js/src/jit-test/tests/ion/bug809472.js
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -953,19 +953,30 @@ MMul::analyzeEdgeCasesForward()
 
 void
 MMul::analyzeEdgeCasesBackward()
 {
     if (canBeNegativeZero_)
         canBeNegativeZero_ = NeedNegativeZeroCheck(this);
 }
 
+void
+MMul::analyzeTruncateBackward()
+{
+    if (!isPossibleTruncated())
+        setPossibleTruncated(js::ion::EdgeCaseAnalysis::AllUsesTruncate(this));
+}
+
 bool
-MMul::updateForReplacement(MDefinition *ins)
+MMul::updateForReplacement(MDefinition *ins_)
 {
+    JS_ASSERT(ins_->isMul());
+    MMul *ins = ins_->toMul();
+    if (isPossibleTruncated())
+        setPossibleTruncated(ins->isPossibleTruncated());
     return true;
 }
 
 void
 MBinaryArithInstruction::infer(JSContext *cx, const TypeOracle::BinaryTypes &b)
 {
     // Retrieve type information of lhs and rhs
     // Rhs is defaulted to int32 first, 
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -2493,21 +2493,34 @@ class MSub : public MBinaryArithInstruct
         Range *right = getOperand(1)->range();
         Range next = isTruncated() ? Range::subTruncate(left,right) : Range::sub(left, right);
         return range()->update(next);
     }
 };
 
 class MMul : public MBinaryArithInstruction
 {
+    // Annotation the result could be a negative zero
+    // and we need to guard this during execution.
     bool canBeNegativeZero_;
 
+    // Annotation the result of this Mul is only used in int32 domain
+    // and we could possible truncate the result.
+    bool possibleTruncate_;
+
+    // Annotation the Mul can truncate. This is only set after range analysis,
+    // because the result could be in the imprecise double range.
+    // In that case the truncated result isn't correct.
+    bool implicitTruncate_;
+
     MMul(MDefinition *left, MDefinition *right, MIRType type)
       : MBinaryArithInstruction(left, right),
-        canBeNegativeZero_(true)
+        canBeNegativeZero_(true),
+        possibleTruncate_(false),
+        implicitTruncate_(false)
     {
         if (type != MIRType_Value)
             specialization_ = type;
         setResultType(type);
     }
 
   public:
     INSTRUCTION_HEADER(Mul);
@@ -2516,23 +2529,24 @@ class MMul : public MBinaryArithInstruct
     }
     static MMul *New(MDefinition *left, MDefinition *right, MIRType type) {
         return new MMul(left, right, type);
     }
 
     MDefinition *foldsTo(bool useValueNumbers);
     void analyzeEdgeCasesForward();
     void analyzeEdgeCasesBackward();
+    void analyzeTruncateBackward();
 
     double getIdentity() {
         return 1;
     }
 
     bool canOverflow() {
-        return !range()->isFinite();
+        return !implicitTruncate_ && !range()->isFinite();
     }
 
     bool canBeNegativeZero() {
         if (range()->lower() > 0 || range()->upper() < 0)
             return false;
         return canBeNegativeZero_;
     }
     bool updateForReplacement(MDefinition *ins);
@@ -2541,18 +2555,28 @@ class MMul : public MBinaryArithInstruct
         return canBeNegativeZero_ || canOverflow();
     }
 
     bool recomputeRange() {
         if (specialization() != MIRType_Int32)
             return false;
         Range *left = getOperand(0)->range();
         Range *right = getOperand(1)->range();
+        if (isPossibleTruncated())
+            implicitTruncate_ = !Range::precisionLossMul(left, right);
         return range()->update(Range::mul(left, right));
     }
+
+    bool isPossibleTruncated() const {
+        return possibleTruncate_;
+    }
+
+    void setPossibleTruncated(bool truncate) {
+        possibleTruncate_ = truncate;
+    }
 };
 
 class MDiv : public MBinaryArithInstruction
 {
     bool canBeNegativeZero_;
     bool canBeNegativeOverflow_;
     bool canBeDivideByZero_;
     bool implicitTruncate_;
--- a/js/src/ion/RangeAnalysis.cpp
+++ b/js/src/ion/RangeAnalysis.cpp
@@ -413,16 +413,34 @@ Range::shr(const Range *lhs, int32 c)
     int32 shift = c & 0x1f;
     Range ret(
         (int64_t)lhs->lower_ >> shift,
         (int64_t)lhs->upper_ >> shift);
     return ret;
 }
 
 bool
+Range::precisionLossMul(const Range *lhs, const Range *rhs)
+{
+    int64_t loss  = 1LL<<53; // result must be lower than 2^53
+    int64_t a = (int64_t)lhs->lower_ * (int64_t)rhs->lower_;
+    int64_t b = (int64_t)lhs->lower_ * (int64_t)rhs->upper_;
+    int64_t c = (int64_t)lhs->upper_ * (int64_t)rhs->lower_;
+    int64_t d = (int64_t)lhs->upper_ * (int64_t)rhs->upper_;
+    int64_t lower = Min( Min(a, b), Min(c, d) );
+    int64_t upper = Max( Max(a, b), Max(c, d) );
+    if (lower < 0)
+        lower = -lower;
+    if (upper < 0)
+        upper = -upper;
+
+    return lower > loss || upper > loss;
+}
+
+bool
 Range::update(const Range *other)
 {
     bool changed =
         lower_ != other->lower_ ||
         lower_infinite_ != other->lower_infinite_ ||
         upper_ != other->upper_ ||
         upper_infinite_ != other->upper_infinite_;
     if (changed) {
--- a/js/src/ion/RangeAnalysis.h
+++ b/js/src/ion/RangeAnalysis.h
@@ -121,16 +121,18 @@ class Range {
     static Range subTruncate(const Range *lhs, const Range *rhs);
     static Range add(const Range *lhs, const Range *rhs);
     static Range sub(const Range *lhs, const Range *rhs);
     static Range mul(const Range *lhs, const Range *rhs);
     static Range and_(const Range *lhs, const Range *rhs);
     static Range shl(const Range *lhs, int32 c);
     static Range shr(const Range *lhs, int32 c);
 
+    static bool precisionLossMul(const Range *lhs, const Range *rhs);
+
     inline void makeLowerInfinite() {
         lower_infinite_ = true;
         lower_ = JSVAL_INT_MIN;
     }
     inline void makeUpperInfinite() {
         upper_infinite_ = true;
         upper_ = JSVAL_INT_MAX;
     }
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/bug809472.js
@@ -0,0 +1,19 @@
+function test1(x) {
+  return (x*((2<<23)-1))|0
+}
+function test2(x) {
+  return (x*((2<<22)-1))|0
+}
+function test3(x) {
+  return (x*((2<<21)-1))|0
+}
+function test4(x) {
+  var b = x + x + 3
+  return (b*b) | 0
+}
+//MAX_INT
+var x = 0x7ffffffe;
+assertEq(test1(x), 2113929216);
+assertEq(test2(x), 2130706434);
+assertEq(test3(x), 2139095042);
+assertEq(test4(x), 0);