Bug 894794 - Collect Range info ahead instead of manipulating operand ranges. r=jandem
authorNicolas B. Pierron <nicolas.b.pierron@mozilla.com>
Wed, 24 Jul 2013 10:46:38 -0700
changeset 139871 6aa9971523fc21ad1267a9e3bfc7c911c3de8f97
parent 139870 4e17c7ca2432053b9ed8cd913a016d9d3e4f5d97
child 139872 68e224769eb123528f2a2ca7bc086143bc09d54d
push idunknown
push userunknown
push dateunknown
reviewersjandem
bugs894794
milestone25.0a1
Bug 894794 - Collect Range info ahead instead of manipulating operand ranges. r=jandem
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/ion/RangeAnalysis.cpp
js/src/jit-test/tests/ion/bug894794.js
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -1177,23 +1177,16 @@ MDiv::fallible()
 bool
 MMod::canBeDivideByZero() const
 {
     JS_ASSERT(specialization_ == MIRType_Int32);
     return !rhs()->isConstant() || rhs()->toConstant()->value().toInt32() == 0;
 }
 
 bool
-MMod::canBeNegativeDividend() const
-{
-    JS_ASSERT(specialization_ == MIRType_Int32);
-    return !lhs()->range() || lhs()->range()->lower() < 0;
-}
-
-bool
 MMod::canBePowerOfTwoDivisor() const
 {
     JS_ASSERT(specialization_ == MIRType_Int32);
 
     if (!rhs()->isConstant())
         return true;
 
     int32_t i = rhs()->toConstant()->value().toInt32();
@@ -2215,30 +2208,16 @@ MBeta::printOpcode(FILE *fp) const
     fprintf(fp, " ");
 
     Sprinter sp(GetIonContext()->cx);
     sp.init();
     comparison_->print(sp);
     fprintf(fp, "%s", sp.string());
 }
 
-void
-MBeta::computeRange()
-{
-    bool emptyRange = false;
-
-    Range *range = Range::intersect(val_->range(), comparison_, &emptyRange);
-    if (emptyRange) {
-        IonSpew(IonSpew_Range, "Marking block for inst %d unexitable", id());
-        block()->setEarlyAbort();
-    } else {
-        setRange(range);
-    }
-}
-
 bool
 MNewObject::shouldUseVM() const
 {
     return templateObject()->hasSingletonType() ||
            templateObject()->hasDynamicSlots();
 }
 
 bool
@@ -2340,22 +2319,16 @@ InlinePropertyTable::buildTypeSetForFunc
         if (entries_[i]->func == func) {
             if (!types->addObject(types::Type::ObjectType(entries_[i]->typeObj).objectKey(), alloc))
                 return NULL;
         }
     }
     return types;
 }
 
-bool
-MInArray::needsNegativeIntCheck() const
-{
-    return !index()->range() || index()->range()->lower() < 0;
-}
-
 void *
 MLoadTypedArrayElementStatic::base() const
 {
     return typedArray_->viewData();
 }
 
 size_t
 MLoadTypedArrayElementStatic::length() const
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -344,16 +344,21 @@ class MDefinition : public MNode
     void setTrackedPc(jsbytecode *pc) {
         trackedPc_ = pc;
     }
 
     jsbytecode *trackedPc() {
         return trackedPc_;
     }
 
+    // Warning: Range analysis is removing the bit-operations such as '| 0' at
+    // the end of the transformations. Using this function to analyse any
+    // operands after the truncate phase of the range analysis will lead to
+    // errors. Instead, one should define the collectRangeInfo() to set the
+    // right set of flags which are dependent on the range of the inputs.
     Range *range() const {
         return range_;
     }
     void setRange(Range *range) {
         range_ = range;
     }
 
     virtual HashNumber valueHash() const;
@@ -366,20 +371,23 @@ class MDefinition : public MNode
     virtual void analyzeEdgeCasesBackward();
 
     virtual bool truncate();
     virtual bool isOperandTruncated(size_t index) const;
 
     bool earlyAbortCheck();
 
     // Compute an absolute or symbolic range for the value of this node.
-    // Ranges are only computed for definitions whose type is int32.
     virtual void computeRange() {
     }
 
+    // Collect information from the truncated ranges.
+    virtual void collectRangeInfo() {
+    }
+
     MNode::Kind kind() const {
         return MNode::Definition;
     }
 
     uint32_t id() const {
         JS_ASSERT(block_);
         return id_;
     }
@@ -3468,20 +3476,22 @@ class MDiv : public MBinaryArithInstruct
 
     bool fallible();
     bool truncate();
 };
 
 class MMod : public MBinaryArithInstruction
 {
     bool unsigned_;
+    bool canBeNegativeDividend_;
 
     MMod(MDefinition *left, MDefinition *right, MIRType type)
       : MBinaryArithInstruction(left, right),
-        unsigned_(false)
+        unsigned_(false),
+        canBeNegativeDividend_(true)
     {
         if (type != MIRType_Value)
             specialization_ = type;
         setResultType(type);
     }
 
   public:
     INSTRUCTION_HEADER(Mod)
@@ -3496,28 +3506,32 @@ class MMod : public MBinaryArithInstruct
     }
 
     MDefinition *foldsTo(bool useValueNumbers);
 
     double getIdentity() {
         MOZ_ASSUME_UNREACHABLE("not used");
     }
 
-    bool canBeNegativeDividend() const;
+    bool canBeNegativeDividend() const {
+        JS_ASSERT(specialization_ == MIRType_Int32);
+        return canBeNegativeDividend_;
+    }
     bool canBeDivideByZero() const;
     bool canBePowerOfTwoDivisor() const;
 
     bool isUnsigned() {
         return unsigned_;
     }
 
     bool fallible();
 
     void computeRange();
     bool truncate();
+    void collectRangeInfo();
 };
 
 class MConcat
   : public MBinaryInstruction,
     public BinaryStringPolicy
 {
     MConcat(MDefinition *left, MDefinition *right)
       : MBinaryInstruction(left, right)
@@ -7097,22 +7111,24 @@ class MIn
 
 
 // Test whether the index is in the array bounds or a hole.
 class MInArray
   : public MQuaternaryInstruction,
     public ObjectPolicy<3>
 {
     bool needsHoleCheck_;
+    bool needsNegativeIntCheck_;
 
     MInArray(MDefinition *elements, MDefinition *index,
              MDefinition *initLength, MDefinition *object,
              bool needsHoleCheck)
       : MQuaternaryInstruction(elements, index, initLength, object),
-        needsHoleCheck_(needsHoleCheck)
+        needsHoleCheck_(needsHoleCheck),
+        needsNegativeIntCheck_(true)
     {
         setResultType(MIRType_Boolean);
         setMovable();
         JS_ASSERT(elements->type() == MIRType_Elements);
         JS_ASSERT(index->type() == MIRType_Int32);
         JS_ASSERT(initLength->type() == MIRType_Int32);
     }
 
@@ -7136,23 +7152,27 @@ class MInArray
         return getOperand(2);
     }
     MDefinition *object() const {
         return getOperand(3);
     }
     bool needsHoleCheck() const {
         return needsHoleCheck_;
     }
-    bool needsNegativeIntCheck() const;
+    bool needsNegativeIntCheck() const {
+        return needsNegativeIntCheck_;
+    }
+    void collectRangeInfo();
     AliasSet getAliasSet() const {
         return AliasSet::Load(AliasSet::Element);
     }
     TypePolicy *typePolicy() {
         return this;
     }
+
 };
 
 // Implementation for instanceof operator with specific rhs.
 class MInstanceOf
   : public MUnaryInstruction,
     public InstanceOfPolicy
 {
     CompilerRootObject protoObj_;
--- a/js/src/ion/RangeAnalysis.cpp
+++ b/js/src/ion/RangeAnalysis.cpp
@@ -800,16 +800,30 @@ MPhi::computeRange()
         else
             range = new Range(*input);
     }
 
     setRange(range);
 }
 
 void
+MBeta::computeRange()
+{
+    bool emptyRange = false;
+
+    Range *range = Range::intersect(val_->range(), comparison_, &emptyRange);
+    if (emptyRange) {
+        IonSpew(IonSpew_Range, "Marking block for inst %d unexitable", id());
+        block()->setEarlyAbort();
+    } else {
+        setRange(range);
+    }
+}
+
+void
 MConstant::computeRange()
 {
     if (type() == MIRType_Int32) {
         setRange(new Range(value().toInt32(), value().toInt32()));
         return;
     }
 
     if (type() != MIRType_Double)
@@ -1910,20 +1924,52 @@ RangeAnalysis::truncate()
     IonSpew(IonSpew_Range, "Do graph type fixup (dequeue)");
     while (!worklist.empty()) {
         MInstruction *ins = worklist.popCopy();
         ins->setNotInWorklist();
         RemoveTruncatesOnOutput(ins);
         AdjustTruncatedInputs(ins);
     }
 
+    // Collect range information as soon as the truncate phased is finished to
+    // ensure that we do not collect information from any operand out-side the
+    // scope of the Range Analysis.
+    //
+    // As the range is attached to the MIR nodes and we remove the bit-ops, we
+    // cannot safely access any information of the range of any operands.
+    //
+    // Example of ranges:
+    //   (x >>> 0)               range() == [0 .. +inf[
+    //   ((x >>> 0) | 0)         range() == [INT32_MIN .. INT32_MAX]
+    //   ((x >>> 0) | 0) % -1    Check   lhs->range()->lower() > 0
+    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
+        for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++)
+            iter->collectRangeInfo();
+    }
+
     // Fold any unnecessary bitops in the graph, such as (x | 0) on an integer
     // input. This is done after range analysis rather than during GVN as the
     // presence of the bitop can change which instructions are truncated.
     for (size_t i = 0; i < bitops.length(); i++) {
         MBinaryBitwiseInstruction *ins = bitops[i];
         MDefinition *folded = ins->foldUnnecessaryBitop();
         if (folded != ins)
             ins->replaceAllUsesWith(folded);
     }
 
     return true;
 }
+
+///////////////////////////////////////////////////////////////////////////////
+// Collect Range information of operands
+///////////////////////////////////////////////////////////////////////////////
+
+void
+MInArray::collectRangeInfo()
+{
+    needsNegativeIntCheck_ = !index()->range() || index()->range()->lower() < 0;
+}
+
+void
+MMod::collectRangeInfo()
+{
+    canBeNegativeDividend_ = !lhs()->range() || lhs()->range()->lower() < 0;
+}
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/bug894794.js
@@ -0,0 +1,7 @@
+(function() {
+    for (var j = 0; j < 1; ++j) {
+        var r = ((0x7fffffff - (0x80000000 | 0)) | 0) % 10000;
+        assertEq(r, -1);
+    }
+})();
+