Teach RangeAnalysis how to deal with unreachable blocks (bug 765119, r=dvander)
authorMarty Rosenberg <mrosenberg@mozilla.com>
Tue, 02 Oct 2012 04:34:28 -0400
changeset 109621 c0b3051972272612b087decafb5f73afe63ba441
parent 109620 94734724e155c9f80c1f837b9e15dae582f24431
child 109622 17c3cdc2f5d9c9fa7bce0e9db60eb79054362ef2
push id23636
push usergsharp@mozilla.com
push dateMon, 08 Oct 2012 08:08:19 +0000
treeherdermozilla-central@24cf40690042 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdvander
bugs765119
milestone18.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
Teach RangeAnalysis how to deal with unreachable blocks (bug 765119, r=dvander)
js/src/ion/Ion.h
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/ion/MIRGraph.cpp
js/src/ion/MIRGraph.h
js/src/ion/RangeAnalysis.cpp
js/src/ion/RangeAnalysis.h
--- a/js/src/ion/Ion.h
+++ b/js/src/ion/Ion.h
@@ -160,17 +160,17 @@ struct IonOptions
       : gvn(true),
         gvnIsOptimistic(true),
         licm(true),
         osr(true),
         limitScriptSize(true),
         lsra(true),
         inlining(true),
         edgeCaseAnalysis(true),
-        rangeAnalysis(false),
+        rangeAnalysis(true),
         parallelCompilation(false),
         usesBeforeCompile(10240),
         usesBeforeCompileNoJaeger(40),
         usesBeforeInlining(usesBeforeCompile),
         maxStackArgs(4096),
         maxInlineDepth(3),
         smallFunctionMaxBytecodeLength(100),
         smallFunctionUsesBeforeInlining(usesBeforeInlining / 4),
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -29,16 +29,33 @@ MDefinition::PrintOpcodeName(FILE *fp, M
 #undef NAME
     };
     const char *name = names[op];
     size_t len = strlen(name);
     for (size_t i = 0; i < len; i++)
         fprintf(fp, "%c", tolower(name[i]));
 }
 
+// If one of the inputs to any non-phi are in a block that will abort, then there is
+// no point in processing this instruction, since control flow cannot reach here.
+bool
+MDefinition::earlyAbortCheck()
+{
+    if (isPhi())
+        return false;
+    for (int i = 0; i < numOperands(); i++) {
+        if (getOperand(i)->block()->earlyAbort()) {
+            block()->setEarlyAbort();
+            IonSpew(IonSpew_Range, "Ignoring value from block %d because instruction %d is in a block that aborts", block()->id(), getOperand(i)->id());
+            return true;
+        }
+    }
+    return false;
+}
+
 static inline bool
 EqualValues(bool useGVN, MDefinition *left, MDefinition *right)
 {
     if (useGVN)
         return left->valueNumber() == right->valueNumber();
 
     return left->id() == right->id();
 }
@@ -464,36 +481,52 @@ MPhi::recomputeRange()
 {
     if (type() != MIRType_Int32)
         return false;
 
     Range r;
     JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue);
     bool updated = false;
     for (size_t i = 0; i < numOperands(); i++) {
-#if 0
         if (getOperand(i)->block()->earlyAbort()) {
             IonSpew(IonSpew_Range, "Ignoring unreachable input %d", getOperand(i)->id());
             continue;
         }
-#endif
+
         if (!isOSRLikeValue(getOperand(i))) {
             if (block()->isLoopHeader())
                 changeCounts_[i].updateRange(getOperand(i)->range());
             if (updated) {
                 if (block()->isLoopHeader())
                     r.unionWith(&changeCounts_[i]);
                 else
                     r.unionWith(getOperand(i)->range());
             } else {
                 r.update(getOperand(0)->range());
                 updated = true;
             }
+#ifdef DEBUG
+            if (IonSpewEnabled(IonSpew_Range)) {
+                fprintf(IonSpewFile, "    %d:", getOperand(i)->id());
+                getOperand(i)->range()->printRange(IonSpewFile);
+                fprintf(IonSpewFile, " => ");
+                r.printRange(IonSpewFile);
+                fprintf(IonSpewFile, "\n");
+            }
+#endif
+
+
         }
-    }
+     }
+     if (!updated) {
+         IonSpew(IonSpew_Range, "My block is unreachable %d", id());
+         block()->setEarlyAbort();
+         return false;
+     }
+
      return range()->update(&r);
 }
 
 uint32
 MPrepareCall::argc() const
 {
     JS_ASSERT(useCount() == 1);
     MCall *call = usesBegin()->node()->toDefinition()->toCall();
@@ -1492,8 +1525,20 @@ void
 MBeta::printOpcode(FILE *fp)
 {
     PrintOpcodeName(fp, op());
     fprintf(fp, " ");
     getOperand(0)->printName(fp);
     fprintf(fp, " ");
     comparison_.printRange(fp);
 }
+
+bool
+MBeta::recomputeRange()
+{
+    bool nullRange = false;
+    bool ret = range()->update(Range::intersect(val_->range(), &comparison_, &nullRange));
+    if (nullRange) {
+            IonSpew(IonSpew_Range, "Marking block for inst %d unexitable", id());
+            block()->setEarlyAbort();
+    }
+    return ret;
+}
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -300,17 +300,17 @@ class MDefinition : public MNode
     virtual bool congruentTo(MDefinition* const &ins) const {
         return false;
     }
     bool congruentIfOperandsEqual(MDefinition * const &ins) const;
     virtual MDefinition *foldsTo(bool useValueNumbers);
     virtual void analyzeEdgeCasesForward();
     virtual void analyzeEdgeCasesBackward();
     virtual void analyzeTruncateBackward();
-
+    bool earlyAbortCheck();
     // Propagate a range. Return true if the range changed.
     virtual bool recomputeRange() {
         return false;
     }
 
     MNode::Kind kind() const {
         return MNode::Definition;
     }
@@ -2789,20 +2789,17 @@ class MBeta : public MUnaryInstruction
     {
         return new MBeta(val, comp);
     }
 
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
 
-    bool recomputeRange() {
-        return range()->update(
-            Range::intersect(val_->range(), &comparison_));
-    }
+    bool recomputeRange();
 };
 
 // MIR representation of a Value on the OSR StackFrame.
 // The Value is indexed off of OsrFrameReg.
 class MOsrValue : public MUnaryInstruction
 {
   private:
     ptrdiff_t frameOffset_;
--- a/js/src/ion/MIRGraph.cpp
+++ b/js/src/ion/MIRGraph.cpp
@@ -112,17 +112,18 @@ MBasicBlock::NewPendingLoopHeader(MIRGra
 
 MBasicBlock *
 MBasicBlock::NewSplitEdge(MIRGraph &graph, CompileInfo &info, MBasicBlock *pred)
 {
     return MBasicBlock::New(graph, info, pred, pred->pc(), SPLIT_EDGE);
 }
 
 MBasicBlock::MBasicBlock(MIRGraph &graph, CompileInfo &info, jsbytecode *pc, Kind kind)
-  : graph_(graph),
+    : earlyAbort_(false),
+    graph_(graph),
     info_(info),
     stackPosition_(info_.firstStackSlot()),
     lastIns_(NULL),
     pc_(pc),
     lir_(NULL),
     start_(NULL),
     entryResumePoint_(NULL),
     successorWithPhis_(NULL),
--- a/js/src/ion/MIRGraph.h
+++ b/js/src/ion/MIRGraph.h
@@ -48,16 +48,20 @@ class MBasicBlock : public TempObject, p
   private:
     MBasicBlock(MIRGraph &graph, CompileInfo &info, jsbytecode *pc, Kind kind);
     bool init();
     void copySlots(MBasicBlock *from);
     bool inherit(MBasicBlock *pred);
     bool inheritResumePoint(MBasicBlock *pred);
     void assertUsesAreNotWithin(MUseIterator use, MUseIterator end);
 
+    // Does this block do something that forces it to terminate early?
+    bool earlyAbort_;
+
+
     // Sets a slot, taking care to rewrite copies.
     void setSlot(uint32 slot, MDefinition *ins);
 
     // Pushes a copy of a local variable or argument.
     void pushVariable(uint32 slot);
 
     // Sets a variable slot to the top of the stack, correctly creating copies
     // as needed.
@@ -79,17 +83,25 @@ class MBasicBlock : public TempObject, p
                                              MBasicBlock *pred, jsbytecode *entryPc);
     static MBasicBlock *NewSplitEdge(MIRGraph &graph, CompileInfo &info, MBasicBlock *pred);
 
     bool dominates(MBasicBlock *other);
 
     void setId(uint32 id) {
         id_ = id;
     }
-
+    void setEarlyAbort() {
+        earlyAbort_ = true;
+    }
+    void clearEarlyAbort() {
+        earlyAbort_ = false;
+    }
+    bool earlyAbort() {
+        return earlyAbort_;
+    }
     // Move the definition to the top of the stack.
     void pick(int32 depth);
 
     // Exchange 2 stack slots at the defined depth
     void swapAt(int32 depth);
 
     // Gets the instruction associated with various slot types.
     MDefinition *peek(int32 depth);
--- a/js/src/ion/RangeAnalysis.cpp
+++ b/js/src/ion/RangeAnalysis.cpp
@@ -244,17 +244,17 @@ Range::printRange(FILE *fp)
     fprintf(fp, "[");
     if (lower_infinite_) { fprintf(fp, "-inf"); } else { fprintf(fp, "%d", lower_); }
     fprintf(fp, ", ");
     if (upper_infinite_) { fprintf(fp, "inf"); } else { fprintf(fp, "%d", upper_); }
     fprintf(fp, "]");
 }
 
 Range
-Range::intersect(const Range *lhs, const Range *rhs)
+Range::intersect(const Range *lhs, const Range *rhs, bool *nullRange)
 {
     Range r(
         Max(lhs->lower_, rhs->lower_),
         Min(lhs->upper_, rhs->upper_));
 
     r.lower_infinite_ = lhs->lower_infinite_ && rhs->lower_infinite_;
     r.upper_infinite_ = lhs->upper_infinite_ && rhs->upper_infinite_;
 
@@ -429,17 +429,17 @@ RangeAnalysis::analyze()
         }
     }
     size_t iters = 0;
 
     while (!worklist.empty()) {
         MDefinition *def = PopFromWorklist(worklist);
         IonSpew(IonSpew_Range, "recomputing range on %d", def->id());
         SpewRange(def);
-        if (def->recomputeRange()) {
+        if (!def->earlyAbortCheck() && def->recomputeRange()) {
             JS_ASSERT(def->range()->lower() <= def->range()->upper());
             IonSpew(IonSpew_Range, "Range changed; adding consumers");
             for (MUseDefIterator use(def); use; use++) {
                 if(!AddToWorklist(worklist, use.def()))
                     return false;
             }
         }
         iters++;
--- a/js/src/ion/RangeAnalysis.h
+++ b/js/src/ion/RangeAnalysis.h
@@ -16,169 +16,168 @@ namespace js {
 namespace ion {
 
 class MBasicBlock;
 class MIRGraph;
 
 class RangeAnalysis
 {
   protected:
-	bool blockDominates(MBasicBlock *b, MBasicBlock *b2);
-	void replaceDominatedUsesWith(MDefinition *orig, MDefinition *dom,
-	                              MBasicBlock *block);
+    bool blockDominates(MBasicBlock *b, MBasicBlock *b2);
+    void replaceDominatedUsesWith(MDefinition *orig, MDefinition *dom,
+                                  MBasicBlock *block);
 
   protected:
     MIRGraph &graph_;
 
   public:
     RangeAnalysis(MIRGraph &graph);
     bool addBetaNobes();
     bool analyze();
     bool removeBetaNobes();
 };
 
 struct RangeChangeCount;
 class Range {
-    private:
-        // :TODO: we should do symbolic range evaluation, where we have
-        // information of the form v1 < v2 for arbitrary defs v1 and v2, not
-        // just constants of type int32.
-        // (Bug 766592)
+  private:
+    // :TODO: we should do symbolic range evaluation, where we have
+    // information of the form v1 < v2 for arbitrary defs v1 and v2, not
+    // just constants of type int32.
+    // (Bug 766592)
 
-        // We represent ranges where the endpoints can be in the set:
-        // {-infty} U [INT_MIN, INT_MAX] U {infty}.  A bound of +/-
-        // infty means that the value may have overflowed in that
-        // direction. When computing the range of an integer
-        // instruction, the ranges of the operands can be clamped to
-        // [INT_MIN, INT_MAX], since if they had overflowed they would
-        // no longer be integers. This is important for optimizations
-        // and somewhat subtle.
-        //
-        // N.B.: All of the operations that compute new ranges based
-        // on existing ranges will ignore the _infinite_ flags of the
-        // input ranges; that is, they implicitly clamp the ranges of
-        // the inputs to [INT_MIN, INT_MAX]. Therefore, while our range might
-        // be infinite (and could overflow), when using this information to
-        // propagate through other ranges, we disregard this fact; if that code
-        // executes, then the overflow did not occur, so we may safely assume
-        // that the range is [INT_MIN, INT_MAX] instead.
-        //
-        // To facilitate this trick, we maintain the invariants that:
-        // 1) lower_infinite == true implies lower_ == JSVAL_INT_MIN
-        // 2) upper_infinite == true implies upper_ == JSVAL_INT_MAX
-        int32 lower_;
-        bool lower_infinite_;
-        int32 upper_;
-        bool upper_infinite_;
+    // We represent ranges where the endpoints can be in the set:
+    // {-infty} U [INT_MIN, INT_MAX] U {infty}.  A bound of +/-
+    // infty means that the value may have overflowed in that
+    // direction. When computing the range of an integer
+    // instruction, the ranges of the operands can be clamped to
+    // [INT_MIN, INT_MAX], since if they had overflowed they would
+    // no longer be integers. This is important for optimizations
+    // and somewhat subtle.
+    //
+    // N.B.: All of the operations that compute new ranges based
+    // on existing ranges will ignore the _infinite_ flags of the
+    // input ranges; that is, they implicitly clamp the ranges of
+    // the inputs to [INT_MIN, INT_MAX]. Therefore, while our range might
+    // be infinite (and could overflow), when using this information to
+    // propagate through other ranges, we disregard this fact; if that code
+    // executes, then the overflow did not occur, so we may safely assume
+    // that the range is [INT_MIN, INT_MAX] instead.
+    //
+    // To facilitate this trick, we maintain the invariants that:
+    // 1) lower_infinite == true implies lower_ == JSVAL_INT_MIN
+    // 2) upper_infinite == true implies upper_ == JSVAL_INT_MAX
+    int32 lower_;
+    bool lower_infinite_;
+    int32 upper_;
+    bool upper_infinite_;
 
-    public:
-        Range()
-          : lower_(JSVAL_INT_MIN),
-            lower_infinite_(true),
-            upper_(JSVAL_INT_MAX),
-            upper_infinite_(true)
-        {}
+  public:
+    Range()
+        : lower_(JSVAL_INT_MIN),
+          lower_infinite_(true),
+          upper_(JSVAL_INT_MAX),
+          upper_infinite_(true)
+    {}
 
-        Range(int64_t l, int64_t h) {
-            setLower(l);
-            setUpper(h);
-        }
+    Range(int64_t l, int64_t h) {
+        setLower(l);
+        setUpper(h);
+    }
 
-        Range(const Range &other)
-          : lower_(other.lower_),
-            lower_infinite_(other.lower_infinite_),
-            upper_(other.upper_),
-            upper_infinite_(other.upper_infinite_)
-        {}
+    Range(const Range &other)
+    : lower_(other.lower_),
+      lower_infinite_(other.lower_infinite_),
+      upper_(other.upper_),
+      upper_infinite_(other.upper_infinite_)
+    {}
 
-        static int64_t abs64(int64_t x) {
+    static int64_t abs64(int64_t x) {
 #ifdef WTF_OS_WINDOWS
-            return _abs64(x);
+        return _abs64(x);
 #else
-            return llabs(x);
+        return llabs(x);
 #endif
-        }
+    }
 
-        void printRange(FILE *fp);
-        bool update(const Range *other);
-        bool update(const Range &other) {
-            return update(&other);
-        }
+    void printRange(FILE *fp);
+    bool update(const Range *other);
+    bool update(const Range &other) {
+        return update(&other);
+    }
 
-        // Unlike the other operations, unionWith is an in-place
-        // modification. This is to avoid a bunch of useless extra
-        // copying when chaining together unions when handling Phi
-        // nodes.
+    // Unlike the other operations, unionWith is an in-place
+    // modification. This is to avoid a bunch of useless extra
+    // copying when chaining together unions when handling Phi
+    // nodes.
     void unionWith(const Range *other);
     void unionWith(RangeChangeCount *other);
-
-        static Range intersect(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 Range intersect(const Range *lhs, const Range *rhs, bool *nullRange);
+    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);
 
-        inline void makeLowerInfinite() {
-            lower_infinite_ = true;
-            lower_ = JSVAL_INT_MIN;
-        }
-        inline void makeUpperInfinite() {
-            upper_infinite_ = true;
-            upper_ = JSVAL_INT_MAX;
-        }
-        inline void makeRangeInfinite() {
-            makeLowerInfinite();
-            makeUpperInfinite();
-        }
+    inline void makeLowerInfinite() {
+        lower_infinite_ = true;
+        lower_ = JSVAL_INT_MIN;
+    }
+    inline void makeUpperInfinite() {
+        upper_infinite_ = true;
+        upper_ = JSVAL_INT_MAX;
+    }
+    inline void makeRangeInfinite() {
+        makeLowerInfinite();
+        makeUpperInfinite();
+    }
 
-        inline bool isLowerInfinite() const {
-            return lower_infinite_;
-        }
-        inline bool isUpperInfinite() const {
-            return upper_infinite_;
-        }
+    inline bool isLowerInfinite() const {
+        return lower_infinite_;
+    }
+    inline bool isUpperInfinite() const {
+        return upper_infinite_;
+    }
 
-        inline bool isFinite() const {
-            return !isLowerInfinite() && !isUpperInfinite();
-        }
+    inline bool isFinite() const {
+        return !isLowerInfinite() && !isUpperInfinite();
+    }
 
-        inline int32 lower() const {
-            return lower_;
-        }
+    inline int32 lower() const {
+        return lower_;
+    }
 
-        inline int32 upper() const {
-            return upper_;
-        }
+    inline int32 upper() const {
+        return upper_;
+    }
 
-        inline void setLower(int64_t x) {
-            if (x > JSVAL_INT_MAX) { // c.c
-                lower_ = JSVAL_INT_MAX;
-            } else if (x < JSVAL_INT_MIN) {
-                makeLowerInfinite();
-            } else {
-                lower_ = (int32)x;
-                lower_infinite_ = false;
-            }
+    inline void setLower(int64_t x) {
+        if (x > JSVAL_INT_MAX) { // c.c
+            lower_ = JSVAL_INT_MAX;
+        } else if (x < JSVAL_INT_MIN) {
+            makeLowerInfinite();
+        } else {
+            lower_ = (int32)x;
+            lower_infinite_ = false;
         }
-        inline void setUpper(int64_t x) {
-            if (x > JSVAL_INT_MAX) {
-                makeUpperInfinite();
-            } else if (x < JSVAL_INT_MIN) { // c.c
-                upper_ = JSVAL_INT_MIN;
-            } else {
-                upper_ = (int32)x;
-                upper_infinite_ = false;
-            }
+    }
+    inline void setUpper(int64_t x) {
+        if (x > JSVAL_INT_MAX) {
+            makeUpperInfinite();
+        } else if (x < JSVAL_INT_MIN) { // c.c
+            upper_ = JSVAL_INT_MIN;
+        } else {
+            upper_ = (int32)x;
+            upper_infinite_ = false;
         }
-        void set(int64_t l, int64_t h) {
-            setLower(l);
-            setUpper(h);
-        }
+    }
+    void set(int64_t l, int64_t h) {
+        setLower(l);
+        setUpper(h);
+    }
 };
 
 struct RangeChangeCount {
     Range oldRange;
     unsigned char lowerCount_ : 4;
     unsigned char upperCount_ : 4;
 
     void updateRange(Range *newRange) {