Bug 824257 - Remove type barriers that are redundant with null/undefined checks, r=jandem.
authorBrian Hackett <bhackett1024@gmail.com>
Tue, 25 Dec 2012 07:27:48 -0700
changeset 126121 78a77949db8e371521f663b919ee2aaacd8c4a0a
parent 126120 b86cca9cd8d261d5e4108fa9f7cc542c73d22f10
child 126122 88a218a4b5bfaaf9cc02dd2d29ea06d66f0610a9
push id2151
push userlsblakk@mozilla.com
push dateTue, 19 Feb 2013 18:06:57 +0000
treeherdermozilla-beta@4952e88741ec [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjandem
bugs824257
milestone20.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 824257 - Remove type barriers that are redundant with null/undefined checks, r=jandem.
js/src/ion/Ion.cpp
js/src/ion/IonAnalysis.cpp
js/src/ion/IonAnalysis.h
js/src/ion/IonBuilder.cpp
js/src/ion/IonBuilder.h
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/jit-test/tests/ion/eliminate-type-barrier.js
js/src/jsinfer.cpp
js/src/jsinfer.h
--- a/js/src/ion/Ion.cpp
+++ b/js/src/ion/Ion.cpp
@@ -951,21 +951,21 @@ CompileBackEnd(MIRGenerator *mir)
             return NULL;
         IonSpewPass("Edge Case Analysis (Late)");
         AssertGraphCoherency(graph);
 
         if (mir->shouldCancel("Edge Case Analysis (Late)"))
             return NULL;
     }
 
-    // Note: bounds check elimination has to run after all other passes that
-    // move instructions. Since bounds check uses are replaced with the actual
-    // index, code motion after this pass could incorrectly move a load or
-    // store before its bounds check.
-    if (!EliminateRedundantBoundsChecks(graph))
+    // Note: check elimination has to run after all other passes that move
+    // instructions. Since check uses are replaced with the actual index, code
+    // motion after this pass could incorrectly move a load or store before its
+    // bounds check.
+    if (!EliminateRedundantChecks(graph))
         return NULL;
     IonSpewPass("Bounds Check Elimination");
     AssertGraphCoherency(graph);
 
     if (mir->shouldCancel("Bounds Check Elimination"))
         return NULL;
 
     LIRGraph *lir = mir->temp().lifoAlloc()->new_<LIRGraph>(&graph);
--- a/js/src/ion/IonAnalysis.cpp
+++ b/js/src/ion/IonAnalysis.cpp
@@ -1129,20 +1129,39 @@ ion::ExtractLinearInequality(MTest *test
 
     *plhs = lsum;
     *prhs = rsum.term;
 
     return true;
 }
 
 static bool
-TryEliminateBoundsCheck(MBoundsCheck *dominating, MBoundsCheck *dominated, bool *eliminated)
+TryEliminateBoundsCheck(BoundsCheckMap &checks, size_t blockIndex, MBoundsCheck *dominated, bool *eliminated)
 {
     JS_ASSERT(!*eliminated);
 
+    // Replace all uses of the bounds check with the actual index.
+    // This is (a) necessary, because we can coalesce two different
+    // bounds checks and would otherwise use the wrong index and
+    // (b) helps register allocation. Note that this is safe since
+    // no other pass after bounds check elimination moves instructions.
+    dominated->replaceAllUsesWith(dominated->index());
+
+    if (!dominated->isMovable())
+        return true;
+
+    MBoundsCheck *dominating = FindDominatingBoundsCheck(checks, dominated, blockIndex);
+    if (!dominating)
+        return false;
+
+    if (dominating == dominated) {
+        // We didn't find a dominating bounds check.
+        return true;
+    }
+
     // We found two bounds checks with the same hash number, but we still have
     // to make sure the lengths and index terms are equal.
     if (dominating->length() != dominated->length())
         return true;
 
     SimpleLinearSum sumA = ExtractLinearSum(dominating->index());
     SimpleLinearSum sumB = ExtractLinearSum(dominated->index());
 
@@ -1172,26 +1191,119 @@ TryEliminateBoundsCheck(MBoundsCheck *do
         return false;
     }
 
     dominating->setMinimum(newMinimum);
     dominating->setMaximum(newMaximum);
     return true;
 }
 
+static void
+TryEliminateTypeBarrierFromTest(MTypeBarrier *barrier, bool filtersNull, bool filtersUndefined,
+                                MTest *test, BranchDirection direction, bool *eliminated)
+{
+    JS_ASSERT(filtersNull || filtersUndefined);
+
+    // Watch for code patterns similar to 'if (x.f) { ... = x.f }'.  If x.f
+    // is either an object or null/undefined, there will be a type barrier on
+    // the latter read as the null/undefined value is never realized there.
+    // The type barrier can be eliminated, however, by looking at tests
+    // performed on the result of the first operation that filter out all
+    // types that have been seen in the first access but not the second.
+
+    // A test 'if (x.f)' filters both null and undefined.
+    if (test->getOperand(0) == barrier->input() && direction == TRUE_BRANCH) {
+        *eliminated = true;
+        barrier->replaceAllUsesWith(barrier->input());
+        return;
+    }
+
+    if (!test->getOperand(0)->isCompare())
+        return;
+
+    MCompare *compare = test->getOperand(0)->toCompare();
+    MCompare::CompareType compareType = compare->compareType();
+
+    if (compareType != MCompare::Compare_Undefined && compareType != MCompare::Compare_Null)
+        return;
+    if (compare->getOperand(0) != barrier->input())
+        return;
+
+    JSOp op = compare->jsop();
+    JS_ASSERT(op == JSOP_EQ || op == JSOP_STRICTEQ ||
+              op == JSOP_NE || op == JSOP_STRICTNE);
+
+    if ((direction == TRUE_BRANCH) != (op == JSOP_NE || op == JSOP_STRICTNE))
+        return;
+
+    // A test 'if (x.f != null)' or 'if (x.f != undefined)' filters both null
+    // and undefined. If strict equality is used, only the specified rhs is
+    // tested for.
+    if (op == JSOP_STRICTEQ || op == JSOP_STRICTNE) {
+        if (compareType == MCompare::Compare_Undefined && !filtersUndefined)
+            return;
+        if (compareType == MCompare::Compare_Null && !filtersNull)
+            return;
+    }
+
+    *eliminated = true;
+    barrier->replaceAllUsesWith(barrier->input());
+}
+
+static bool
+TryEliminateTypeBarrier(MTypeBarrier *barrier, bool *eliminated)
+{
+    JS_ASSERT(!*eliminated);
+
+    const types::StackTypeSet *barrierTypes = barrier->typeSet();
+    const types::StackTypeSet *inputTypes = barrier->input()->typeSet();
+
+    if (!barrierTypes || !inputTypes)
+        return true;
+
+    bool filtersNull = barrierTypes->filtersType(inputTypes, types::Type::NullType());
+    bool filtersUndefined = barrierTypes->filtersType(inputTypes, types::Type::UndefinedType());
+
+    if (!filtersNull && !filtersUndefined)
+        return true;
+
+    MBasicBlock *block = barrier->block();
+    while (true) {
+        BranchDirection direction;
+        MTest *test = block->immediateDominatorBranch(&direction);
+
+        if (test) {
+            TryEliminateTypeBarrierFromTest(barrier, filtersNull, filtersUndefined,
+                                            test, direction, eliminated);
+        }
+
+        MBasicBlock *previous = block->immediateDominator();
+        if (previous == block)
+            break;
+        block = previous;
+    }
+
+    return true;
+}
+
+// Eliminate checks which are redundant given each other or other instructions.
+//
+// A type barrier is considered redundant if all missing types have been tested
+// for by earlier control instructions.
+//
 // A bounds check is considered redundant if it's dominated by another bounds
 // check with the same length and the indexes differ by only a constant amount.
 // In this case we eliminate the redundant bounds check and update the other one
 // to cover the ranges of both checks.
 //
 // Bounds checks are added to a hash map and since the hash function ignores
 // differences in constant offset, this offers a fast way to find redundant
 // checks.
 bool
-ion::EliminateRedundantBoundsChecks(MIRGraph &graph)
+ion::EliminateRedundantChecks(MIRGraph &graph)
 {
     BoundsCheckMap checks;
 
     if (!checks.init())
         return false;
 
     // Stack for pre-order CFG traversal.
     Vector<MBasicBlock *, 1, IonAllocPolicy> worklist;
@@ -1215,51 +1327,28 @@ ion::EliminateRedundantBoundsChecks(MIRG
 
         // Add all immediate dominators to the front of the worklist.
         for (size_t i = 0; i < block->numImmediatelyDominatedBlocks(); i++) {
             if (!worklist.append(block->getImmediatelyDominatedBlock(i)))
                 return false;
         }
 
         for (MDefinitionIterator iter(block); iter; ) {
-            if (!iter->isBoundsCheck()) {
-                iter++;
-                continue;
+            bool eliminated = false;
+
+            if (iter->isBoundsCheck()) {
+                if (!TryEliminateBoundsCheck(checks, index, iter->toBoundsCheck(), &eliminated))
+                    return false;
+            } else if (iter->isTypeBarrier()) {
+                if (!TryEliminateTypeBarrier(iter->toTypeBarrier(), &eliminated))
+                    return false;
             }
 
-            MBoundsCheck *check = iter->toBoundsCheck();
-
-            // Replace all uses of the bounds check with the actual index.
-            // This is (a) necessary, because we can coalesce two different
-            // bounds checks and would otherwise use the wrong index and
-            // (b) helps register allocation. Note that this is safe since
-            // no other pass after bounds check elimination moves instructions.
-            check->replaceAllUsesWith(check->index());
-
-            if (!check->isMovable()) {
-                iter++;
-                continue;
-            }
-
-            MBoundsCheck *dominating = FindDominatingBoundsCheck(checks, check, index);
-            if (!dominating)
-                return false;
-
-            if (dominating == check) {
-                // We didn't find a dominating bounds check.
-                iter++;
-                continue;
-            }
-
-            bool eliminated = false;
-            if (!TryEliminateBoundsCheck(dominating, check, &eliminated))
-                return false;
-
             if (eliminated)
-                iter = check->block()->discardDefAt(iter);
+                iter = block->discardDefAt(iter);
             else
                 iter++;
         }
         index++;
     }
 
     JS_ASSERT(index == graph.numBlocks());
     return true;
--- a/js/src/ion/IonAnalysis.h
+++ b/js/src/ion/IonAnalysis.h
@@ -50,17 +50,17 @@ BuildPhiReverseMapping(MIRGraph &graph);
 
 void
 AssertGraphCoherency(MIRGraph &graph);
 
 void
 AssertExtendedGraphCoherency(MIRGraph &graph);
 
 bool
-EliminateRedundantBoundsChecks(MIRGraph &graph);
+EliminateRedundantChecks(MIRGraph &graph);
 
 class MDefinition;
 
 // Simple linear sum of the form 'n' or 'x + n'.
 struct SimpleLinearSum
 {
     MDefinition *term;
     int32_t constant;
--- a/js/src/ion/IonBuilder.cpp
+++ b/js/src/ion/IonBuilder.cpp
@@ -5098,16 +5098,21 @@ IonBuilder::pushTypeBarrier(MInstruction
                 JS_ASSERT(ins->type() == replaceType);
             break;
           }
         }
         if (replace) {
             current->pop();
             current->add(replace);
             current->push(replace);
+            if (replace->acceptsTypeSet())
+                replace->setTypeSet(cloneTypeSet(actual));
+        } else {
+            if (ins->acceptsTypeSet())
+                ins->setTypeSet(cloneTypeSet(actual));
         }
         return true;
     }
 
     if (observed->unknown())
         return true;
 
     current->pop();
@@ -5146,17 +5151,17 @@ IonBuilder::pushTypeBarrier(MInstruction
     }
     current->push(barrier);
     return true;
 }
 
 // Test the type of values returned by a VM call. This is an optimized version
 // of calling TypeScript::Monitor inside such stubs.
 void
-IonBuilder::monitorResult(MInstruction *ins, types::TypeSet *barrier, types::TypeSet *types)
+IonBuilder::monitorResult(MInstruction *ins, types::TypeSet *barrier, types::StackTypeSet *types)
 {
     // MonitorTypes is redundant if we will also add a type barrier.
     if (barrier)
         return;
 
     if (!types || types->unknown())
         return;
 
@@ -7076,18 +7081,18 @@ IonBuilder::addShapeGuard(MDefinition *o
 
     // If a shape guard failed in the past, don't optimize shape guard.
     if (failedShapeGuard_)
         guard->setNotMovable();
 
     return guard;
 }
 
-const types::TypeSet *
-IonBuilder::cloneTypeSet(const types::TypeSet *types)
+const types::StackTypeSet *
+IonBuilder::cloneTypeSet(const types::StackTypeSet *types)
 {
     if (!js_IonOptions.parallelCompilation)
         return types;
 
     // Clone a type set so that it can be stored into the MIR and accessed
     // during off thread compilation. This is necessary because main thread
     // updates to type sets can race with reads in the compiler backend, and
     // after bug 804676 this code can be removed.
--- a/js/src/ion/IonBuilder.h
+++ b/js/src/ion/IonBuilder.h
@@ -283,17 +283,17 @@ class IonBuilder : public MIRGenerator
 
     void insertRecompileCheck();
 
     bool initParameters();
     void rewriteParameters();
     bool initScopeChain();
     bool pushConstant(const Value &v);
     bool pushTypeBarrier(MInstruction *ins, types::StackTypeSet *actual, types::StackTypeSet *observed);
-    void monitorResult(MInstruction *ins, types::TypeSet *barrier, types::TypeSet *types);
+    void monitorResult(MInstruction *ins, types::TypeSet *barrier, types::StackTypeSet *types);
 
     JSObject *getSingletonPrototype(JSFunction *target);
 
     MDefinition *createThisNative();
     MDefinition *createThisScripted(MDefinition *callee);
     MDefinition *createThisScriptedSingleton(HandleFunction target, HandleObject proto, MDefinition *callee);
     MDefinition *createThis(HandleFunction target, MDefinition *callee);
     MInstruction *createDeclEnvObject(MDefinition *callee, MDefinition *scopeObj);
@@ -465,17 +465,17 @@ class IonBuilder : public MIRGenerator
 
     MPolyInlineDispatch *
     makePolyInlineDispatch(JSContext *cx, AutoObjectVector &targets, int argc,
                            MGetPropertyCache *getPropCache,
                            types::StackTypeSet *types, types::StackTypeSet *barrier,
                            MBasicBlock *bottom,
                            Vector<MDefinition *, 8, IonAllocPolicy> &retvalDefns);
 
-    const types::TypeSet *cloneTypeSet(const types::TypeSet *types);
+    const types::StackTypeSet *cloneTypeSet(const types::StackTypeSet *types);
 
     // A builder is inextricably tied to a particular script.
     HeapPtrScript script_;
 
     // If off thread compilation is successful, the final code generator is
     // attached here. Code has been generated, but not linked (there is not yet
     // an IonScript). This is heap allocated, and must be explicitly destroyed.
     CodeGenerator *backgroundCodegen_;
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -362,17 +362,17 @@ MConstant::printOpcode(FILE *fp)
 void
 MConstantElements::printOpcode(FILE *fp)
 {
     PrintOpcodeName(fp, op());
     fprintf(fp, " %p", value());
 }
 
 MParameter *
-MParameter::New(int32_t index, const types::TypeSet *types)
+MParameter::New(int32_t index, const types::StackTypeSet *types)
 {
     return new MParameter(index, types);
 }
 
 void
 MParameter::printOpcode(FILE *fp)
 {
     PrintOpcodeName(fp, op());
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -438,16 +438,25 @@ class MDefinition : public MNode
     bool isInstruction() const {
         return !isPhi();
     }
 
     void setResultType(MIRType type) {
         resultType_ = type;
     }
 
+    virtual bool acceptsTypeSet() const {
+        return false;
+    }
+    virtual void setTypeSet(const types::StackTypeSet *types) {
+    }
+    virtual const types::StackTypeSet *typeSet() const {
+        return NULL;
+    }
+
     MDefinition *dependency() const {
         return dependency_;
     }
     void setDependency(MDefinition *dependency) {
         dependency_ = dependency;
     }
     virtual AliasSet getAliasSet() const {
         // Instructions are effectful by default.
@@ -658,36 +667,36 @@ class MConstant : public MNullaryInstruc
     }
 
     void computeRange();
 };
 
 class MParameter : public MNullaryInstruction
 {
     int32_t index_;
-    const types::TypeSet *typeSet_;
+    const types::StackTypeSet *typeSet_;
 
   public:
     static const int32_t THIS_SLOT = -1;
 
-    MParameter(int32_t index, const types::TypeSet *types)
+    MParameter(int32_t index, const types::StackTypeSet *types)
       : index_(index),
         typeSet_(types)
     {
         setResultType(MIRType_Value);
     }
 
   public:
     INSTRUCTION_HEADER(Parameter)
-    static MParameter *New(int32_t index, const types::TypeSet *types);
+    static MParameter *New(int32_t index, const types::StackTypeSet *types);
 
     int32_t index() const {
         return index_;
     }
-    const types::TypeSet *typeSet() const {
+    const types::StackTypeSet *typeSet() const {
         return typeSet_;
     }
     void printOpcode(FILE *fp);
 
     HashNumber valueHash() const;
     bool congruentTo(MDefinition * const &ins) const;
 };
 
@@ -4112,36 +4121,47 @@ class MClampToUint8
     void computeRange();
 };
 
 class MLoadFixedSlot
   : public MUnaryInstruction,
     public SingleObjectPolicy
 {
     size_t slot_;
+    const types::StackTypeSet *types_;
 
   protected:
     MLoadFixedSlot(MDefinition *obj, size_t slot)
-      : MUnaryInstruction(obj), slot_(slot)
+      : MUnaryInstruction(obj), slot_(slot), types_(NULL)
     {
         setResultType(MIRType_Value);
         setMovable();
     }
 
   public:
     INSTRUCTION_HEADER(LoadFixedSlot)
 
     static MLoadFixedSlot *New(MDefinition *obj, size_t slot) {
         return new MLoadFixedSlot(obj, slot);
     }
 
     TypePolicy *typePolicy() {
         return this;
     }
 
+    virtual bool acceptsTypeSet() const {
+        return true;
+    }
+    virtual void setTypeSet(const types::StackTypeSet *types) {
+        types_ = types;
+    }
+    virtual const types::StackTypeSet *typeSet() const {
+        return types_;
+    }
+
     MDefinition *object() const {
         return getOperand(0);
     }
     size_t slot() const {
         return slot_;
     }
     bool congruentTo(MDefinition * const &ins) const {
         if (!ins->isLoadFixedSlot())
@@ -4692,20 +4712,22 @@ class MGuardClass
 };
 
 // Load from vp[slot] (slots that are not inline in an object).
 class MLoadSlot
   : public MUnaryInstruction,
     public SingleObjectPolicy
 {
     uint32_t slot_;
+    const types::StackTypeSet *types_;
 
     MLoadSlot(MDefinition *slots, uint32_t slot)
       : MUnaryInstruction(slots),
-        slot_(slot)
+        slot_(slot),
+        types_(NULL)
     {
         setResultType(MIRType_Value);
         setMovable();
         JS_ASSERT(slots->type() == MIRType_Slots);
     }
 
   public:
     INSTRUCTION_HEADER(LoadSlot)
@@ -4718,16 +4740,27 @@ class MLoadSlot
         return this;
     }
     MDefinition *slots() const {
         return getOperand(0);
     }
     uint32_t slot() const {
         return slot_;
     }
+
+    virtual bool acceptsTypeSet() const {
+        return true;
+    }
+    virtual void setTypeSet(const types::StackTypeSet *types) {
+        types_ = types;
+    }
+    virtual const types::StackTypeSet *typeSet() const {
+        return types_;
+    }
+
     bool congruentTo(MDefinition * const &ins) const {
         if (!ins->isLoadSlot())
             return false;
         if (slot() != ins->toLoadSlot()->slot())
             return false;
         return congruentIfOperandsEqual(ins);
     }
     AliasSet getAliasSet() const {
@@ -5559,83 +5592,83 @@ class MGetArgument
    }
 };
 
 // Given a value, guard that the value is in a particular TypeSet, then returns
 // that value.
 class MTypeBarrier : public MUnaryInstruction
 {
     BailoutKind bailoutKind_;
-    const types::TypeSet *typeSet_;
-
-    MTypeBarrier(MDefinition *def, const types::TypeSet *types)
+    const types::StackTypeSet *typeSet_;
+
+    MTypeBarrier(MDefinition *def, const types::StackTypeSet *types)
       : MUnaryInstruction(def),
         typeSet_(types)
     {
         setResultType(MIRType_Value);
         setGuard();
         setMovable();
         bailoutKind_ = def->isEffectful()
                        ? Bailout_TypeBarrier
                        : Bailout_Normal;
     }
 
   public:
     INSTRUCTION_HEADER(TypeBarrier)
 
-    static MTypeBarrier *New(MDefinition *def, const types::TypeSet *types) {
+    static MTypeBarrier *New(MDefinition *def, const types::StackTypeSet *types) {
         return new MTypeBarrier(def, types);
     }
     bool congruentTo(MDefinition * const &def) const {
         return false;
     }
     MDefinition *input() const {
         return getOperand(0);
     }
     BailoutKind bailoutKind() const {
         return bailoutKind_;
     }
-    const types::TypeSet *typeSet() const {
+    const types::StackTypeSet *typeSet() const {
         return typeSet_;
     }
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
     virtual bool neverHoist() const {
         return typeSet()->empty();
     }
 
 };
 
 // Like MTypeBarrier, guard that the value is in the given type set. This is
 // used after some VM calls (like GetElement) to avoid the slower calls to
 // TypeScript::Monitor inside these stubs.
 class MMonitorTypes : public MUnaryInstruction
 {
-    const types::TypeSet *typeSet_;
-
-    MMonitorTypes(MDefinition *def, const types::TypeSet *types)
+    const types::StackTypeSet *typeSet_;
+
+    MMonitorTypes(MDefinition *def, const types::StackTypeSet *types)
       : MUnaryInstruction(def),
         typeSet_(types)
     {
         setResultType(MIRType_Value);
         setGuard();
         JS_ASSERT(!types->unknown());
     }
 
   public:
     INSTRUCTION_HEADER(MonitorTypes)
 
-    static MMonitorTypes *New(MDefinition *def, const types::TypeSet *types) {
+    static MMonitorTypes *New(MDefinition *def, const types::StackTypeSet *types) {
         return new MMonitorTypes(def, types);
     }
     MDefinition *input() const {
         return getOperand(0);
     }
-    const types::TypeSet *typeSet() const {
+    const types::StackTypeSet *typeSet() const {
         return typeSet_;
     }
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
 };
 
 class MNewSlots : public MNullaryInstruction
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/eliminate-type-barrier.js
@@ -0,0 +1,41 @@
+function foo(a) {
+  var y = 0;
+  for (var i = 0; i < 10; i++) {
+    var x = a[i];
+    z = x.f;
+    if (x.h != null)
+      y = x.f.g;
+  }
+  return y;
+}
+
+function foo2(a) {
+  var y = 0;
+  for (var i = 0; i < 10; i++) {
+    var x = a[i];
+    if (x.f !== undefined) {
+      if (x.h != null)
+        y = x.f.g;
+    }
+  }
+  return y;
+}
+
+a = [];
+for (var i = 0; i < 10; i++)
+  a[i] = {f:null, h:null};
+for (var i = 0; i < 10; i++) {
+  a[i].f = {g:0};
+  a[i].h = {};
+}
+var q = a[0].h;
+a[0].f = null;
+a[0].h = null;
+
+foo(a);
+foo2(a);
+
+a[0].h = q;
+
+try { foo(a); } catch (e) {}
+try { foo2(a); } catch (e) {}
--- a/js/src/jsinfer.cpp
+++ b/js/src/jsinfer.cpp
@@ -453,23 +453,23 @@ StackTypeSet::make(JSContext *cx, const 
     InferSpew(ISpewOps, "typeSet: %sT%p%s intermediate %s",
               InferSpewColor(res), res, InferSpewColorReset(),
               name);
     res->setPurged();
 
     return res;
 }
 
-const TypeSet *
+const StackTypeSet *
 TypeSet::clone(LifoAlloc *alloc) const
 {
     unsigned objectCount = baseObjectCount();
     unsigned capacity = (objectCount >= 2) ? HashSetCapacity(objectCount) : 0;
 
-    TypeSet *res = alloc->new_<TypeSet>();
+    StackTypeSet *res = alloc->new_<StackTypeSet>();
     if (!res)
         return NULL;
 
     TypeObjectKey **newSet;
     if (capacity) {
         newSet = alloc->newArray<TypeObjectKey*>(capacity);
         if (!newSet)
             return NULL;
@@ -1861,16 +1861,43 @@ StackTypeSet::knownNonStringPrimitive()
         return false;
 
     if (baseFlags() == 0)
         return false;
     return true;
 }
 
 bool
+StackTypeSet::filtersType(const StackTypeSet *other, Type filteredType) const
+{
+    if (other->unknown())
+        return unknown();
+
+    for (TypeFlags flag = 1; flag < TYPE_FLAG_ANYOBJECT; flag <<= 1) {
+        Type type = Type::PrimitiveType(TypeFlagPrimitive(flag));
+        if (type != filteredType && other->hasType(type) && !hasType(type))
+            return false;
+    }
+
+    if (other->unknownObject())
+        return unknownObject();
+
+    for (size_t i = 0; i < other->getObjectCount(); i++) {
+        TypeObjectKey *key = other->getObject(i);
+        if (key) {
+            Type type = Type::ObjectType(key);
+            if (type != filteredType && !hasType(type))
+                return false;
+        }
+    }
+
+    return true;
+}
+
+bool
 HeapTypeSet::knownSubset(JSContext *cx, TypeSet *other)
 {
     JS_ASSERT(!other->constraintsPurged());
 
     if ((baseFlags() & other->baseFlags()) != baseFlags())
         return false;
 
     if (unknownObject()) {
--- a/js/src/jsinfer.h
+++ b/js/src/jsinfer.h
@@ -465,17 +465,17 @@ class TypeSet
         JS_ASSERT(definiteProperty());
         return flags >> TYPE_FLAG_DEFINITE_SHIFT;
     }
 
     /*
      * Clone a type set into an arbitrary allocator. The result should not be
      * modified further.
      */
-    const TypeSet *clone(LifoAlloc *alloc) const;
+    const StackTypeSet *clone(LifoAlloc *alloc) const;
 
     /*
      * Add a type to this set, calling any constraint handlers if this is a new
      * possible type.
      */
     inline void addType(JSContext *cx, Type type);
 
     /* Mark this type set as representing an own property or configured property. */
@@ -600,16 +600,22 @@ class StackTypeSet : public TypeSet
 
     /* Get the single value which can appear in this type set, otherwise NULL. */
     RawObject getSingleton();
 
     /* Whether any objects in the type set needs a barrier on id. */
     bool propertyNeedsBarrier(JSContext *cx, jsid id);
 
     /*
+     * Whether this set contains all types in other, except (possibly) the
+     * specified type.
+     */
+    bool filtersType(const StackTypeSet *other, Type type) const;
+
+    /*
      * Get whether this type only contains non-string primitives:
      * null/undefined/int/double, or some combination of those.
      */
     bool knownNonStringPrimitive();
 
     bool knownPrimitiveOrObject() {
         TypeFlags flags = TYPE_FLAG_UNDEFINED | TYPE_FLAG_NULL | TYPE_FLAG_DOUBLE |
                           TYPE_FLAG_INT32 | TYPE_FLAG_BOOLEAN | TYPE_FLAG_STRING |