Bug 824275 - Improve precision of alias analysis, r=jandem.
authorBrian Hackett <bhackett1024@gmail.com>
Mon, 24 Dec 2012 10:29:14 -0700
changeset 126104 0e0200b9ef780a04dbbabd9cc89aa171a3393e35
parent 126103 978ca52298f03d045caf4599364f844db0ae41f4
child 126105 671e04519d02a0f588a5456c5d372fbf8416f839
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
bugs824275
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 824275 - Improve precision of alias analysis, r=jandem.
js/src/ion/AliasAnalysis.cpp
js/src/ion/AliasAnalysis.h
js/src/ion/MIR.cpp
js/src/ion/MIR.h
--- a/js/src/ion/AliasAnalysis.cpp
+++ b/js/src/ion/AliasAnalysis.cpp
@@ -39,27 +39,49 @@ class AliasSetIterator
             pos++;
         } while (flags && (flags & 1) == 0);
         return *this;
     }
     operator bool() const {
         return !!flags;
     }
     unsigned operator *() const {
+        JS_ASSERT(pos < AliasSet::NumCategories);
         return pos;
     }
 };
 
 AliasAnalysis::AliasAnalysis(MIRGenerator *mir, MIRGraph &graph)
   : mir(mir),
     graph_(graph),
     loop_(NULL)
 {
 }
 
+// Whether there might be a path from src to dest, excluding loop backedges. This is
+// approximate and really ought to depend on precomputed reachability information.
+static inline bool
+BlockMightReach(MBasicBlock *src, MBasicBlock *dest)
+{
+    while (src->id() <= dest->id()) {
+        if (src == dest)
+            return true;
+        switch (src->numSuccessors()) {
+          case 0:
+            return false;
+          case 1:
+            src = src->getSuccessor(0);
+            break;
+          default:
+            return true;
+        }
+    }
+    return false;
+}
+
 // This pass annotates every load instruction with the last store instruction
 // on which it depends. The algorithm is optimistic in that it ignores explicit
 // dependencies and only considers loads and stores.
 //
 // Loads inside loops only have an implicit dependency on a store before the
 // loop header if no instruction inside the loop body aliases it. To calculate
 // this efficiently, we maintain a list of maybe-invariant loads and the combined
 // alias set for all stores inside the loop. When we see the loop's backedge, this
@@ -67,22 +89,22 @@ AliasAnalysis::AliasAnalysis(MIRGenerato
 // having an implicit dependency on the last instruction of the loop header, so that
 // it's never moved before the loop header.
 //
 // The algorithm depends on the invariant that both control instructions and effectful
 // instructions (stores) are never hoisted.
 bool
 AliasAnalysis::analyze()
 {
-    Vector<MDefinition *, 16, SystemAllocPolicy> stores;
+    FixedArityList<MDefinitionVector, AliasSet::NumCategories> stores;
 
     // Initialize to the first instruction.
     MDefinition *firstIns = *graph_.begin()->begin();
-    for (unsigned i=0; i < NUM_ALIAS_SETS; i++) {
-        if (!stores.append(firstIns))
+    for (unsigned i=0; i < AliasSet::NumCategories; i++) {
+        if (!stores[i].append(firstIns))
             return false;
     }
 
     // Type analysis may have inserted new instructions. Since this pass depends
     // on the instruction number ordering, all instructions are renumbered.
     // We start with 1 because some passes use 0 to denote failure.
     uint32_t newId = 1;
 
@@ -98,31 +120,36 @@ AliasAnalysis::analyze()
         for (MDefinitionIterator def(*block); def; def++) {
             def->setId(newId++);
 
             AliasSet set = def->getAliasSet();
             if (set.isNone())
                 continue;
 
             if (set.isStore()) {
-                for (AliasSetIterator iter(set); iter; iter++)
-                    stores[*iter] = *def;
+                for (AliasSetIterator iter(set); iter; iter++) {
+                    if (!stores[*iter].append(*def))
+                        return false;
+                }
 
                 IonSpew(IonSpew_Alias, "Processing store %d (flags %x)", def->id(), set.flags());
-
-                if (loop_)
-                    loop_->addStore(set);
             } else {
                 // Find the most recent store on which this instruction depends.
-                MDefinition *lastStore = NULL;
+                MDefinition *lastStore = firstIns;
 
                 for (AliasSetIterator iter(set); iter; iter++) {
-                    MDefinition *store = stores[*iter];
-                    if (!lastStore || lastStore->id() < store->id())
-                        lastStore = store;
+                    MDefinitionVector &aliasedStores = stores[*iter];
+                    for (int i = aliasedStores.length() - 1; i >= 0; i--) {
+                        MDefinition *store = aliasedStores[i];
+                        if (def->mightAlias(store) && BlockMightReach(store->block(), *block)) {
+                            if (lastStore->id() < store->id())
+                                lastStore = store;
+                            break;
+                        }
+                    }
                 }
 
                 def->setDependency(lastStore);
                 IonSpew(IonSpew_Alias, "Load %d depends on store %d", def->id(), lastStore->id());
 
                 // If the last store was before the current loop, we assume this load
                 // is loop invariant. If a later instruction writes to the same location,
                 // we will fix this at the end of the loop.
@@ -133,45 +160,58 @@ AliasAnalysis::analyze()
             }
         }
 
         if (block->isLoopBackedge()) {
             JS_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge());
             IonSpew(IonSpew_Alias, "Processing loop backedge %d (header %d)", block->id(),
                     loop_->loopHeader()->id());
             LoopAliasInfo *outerLoop = loop_->outer();
-
-            // Propagate stores in this loop to the outer loop.
-            if (outerLoop)
-                outerLoop->addStore(loop_->loopStores());
+            MInstruction *firstLoopIns = *loop_->loopHeader()->begin();
 
             const InstructionVector &invariant = loop_->invariantLoads();
 
             for (unsigned i = 0; i < invariant.length(); i++) {
                 MDefinition *ins = invariant[i];
                 AliasSet set = ins->getAliasSet();
                 JS_ASSERT(set.isLoad());
 
-                if ((loop_->loopStores() & set).isNone()) {
+                bool hasAlias = false;
+                for (AliasSetIterator iter(set); iter; iter++) {
+                    MDefinitionVector &aliasedStores = stores[*iter];
+                    for (int i = aliasedStores.length() - 1;; i--) {
+                        MDefinition *store = aliasedStores[i];
+                        if (store->id() < firstLoopIns->id())
+                            break;
+                        if (ins->mightAlias(store)) {
+                            hasAlias = true;
+                            break;
+                        }
+                    }
+                    if (hasAlias)
+                        break;
+                }
+
+                if (hasAlias) {
+                    // This instruction depends on stores inside the loop body. Mark it as having a
+                    // dependency on the last instruction of the loop header. The last instruction is a
+                    // control instruction and these are never hoisted.
+                    MControlInstruction *controlIns = loop_->loopHeader()->lastIns();
+                    IonSpew(IonSpew_Alias, "Load %d depends on %d (due to stores in loop body)",
+                            ins->id(), controlIns->id());
+                    ins->setDependency(controlIns);
+                } else {
                     IonSpew(IonSpew_Alias, "Load %d does not depend on any stores in this loop",
                             ins->id());
 
                     if (outerLoop && ins->dependency()->id() < outerLoop->firstInstruction()->id()) {
                         IonSpew(IonSpew_Alias, "Load %d may be invariant in outer loop", ins->id());
                         if (!outerLoop->addInvariantLoad(ins))
                             return false;
                     }
-                } else {
-                    // This instruction depends on stores inside the loop body. Mark it as having a
-                    // dependency on the last instruction of the loop header. The last instruction is a
-                    // control instruction and these are never hoisted.
-                    MControlInstruction *controlIns = loop_->loopHeader()->lastIns();
-                    IonSpew(IonSpew_Alias, "Load %d depends on %d (due to stores in loop body)",
-                            ins->id(), controlIns->id());
-                    ins->setDependency(controlIns);
                 }
             }
             loop_ = loop_->outer();
         }
     }
 
     JS_ASSERT(loop_ == NULL);
     return true;
--- a/js/src/ion/AliasAnalysis.h
+++ b/js/src/ion/AliasAnalysis.h
@@ -16,43 +16,36 @@ namespace ion {
 
 class MIRGraph;
 
 typedef Vector<MDefinition *, 4, IonAllocPolicy> InstructionVector;
 
 class LoopAliasInfo : public TempObject {
   private:
     LoopAliasInfo *outer_;
-    AliasSet loopStores_;
     MBasicBlock *loopHeader_;
     InstructionVector invariantLoads_;
 
   public:
     LoopAliasInfo(LoopAliasInfo *outer, MBasicBlock *loopHeader)
-      : outer_(outer), loopStores_(AliasSet::None()), loopHeader_(loopHeader)
+      : outer_(outer), loopHeader_(loopHeader)
     { }
 
-    void addStore(AliasSet store) {
-        loopStores_ = loopStores_ | store;
-    }
     MBasicBlock *loopHeader() const {
         return loopHeader_;
     }
     LoopAliasInfo *outer() const {
         return outer_;
     }
     bool addInvariantLoad(MDefinition *ins) {
         return invariantLoads_.append(ins);
     }
     const InstructionVector& invariantLoads() const {
         return invariantLoads_;
     }
-    AliasSet loopStores() const {
-        return loopStores_;
-    }
     MDefinition *firstInstruction() const {
         return *loopHeader_->begin();
     }
 };
 
 class AliasAnalysis
 {
     MIRGenerator *mir;
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -1716,8 +1716,24 @@ MBeta::computeRange()
     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
+MLoadFixedSlot::mightAlias(MDefinition *store)
+{
+    if (store->isStoreFixedSlot() && store->toStoreFixedSlot()->slot() != slot())
+        return false;
+    return true;
+}
+
+bool
+MLoadSlot::mightAlias(MDefinition *store)
+{
+    if (store->isStoreSlot() && store->toStoreSlot()->slot() != slot())
+        return false;
+    return true;
+}
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -161,27 +161,32 @@ class AliasSet {
   private:
     uint32_t flags_;
 
   public:
     enum Flag {
         None_             = 0,
         ObjectFields      = 1 << 0, // shape, class, slots, length etc.
         Element           = 1 << 1, // A member of obj->elements.
-        Slot              = 1 << 2, // A member of obj->slots.
-        TypedArrayElement = 1 << 3, // A typed array element.
+        DynamicSlot       = 1 << 2, // A member of obj->slots.
+        FixedSlot         = 1 << 3, // A member of obj->fixedSlots().
+        TypedArrayElement = 1 << 4, // A typed array element.
         Last              = TypedArrayElement,
         Any               = Last | (Last - 1),
 
+        NumCategories     = 5,
+
         // Indicates load or store.
         Store_            = 1 << 31
     };
     AliasSet(uint32_t flags)
       : flags_(flags)
-    { }
+    {
+        JS_STATIC_ASSERT((1 << NumCategories) - 1 == Any);
+    }
 
   public:
     inline bool isNone() const {
         return flags_ == None_;
     }
     uint32_t flags() const {
         return flags_ & Any;
     }
@@ -205,18 +210,16 @@ class AliasSet {
         return AliasSet(flags);
     }
     static AliasSet Store(uint32_t flags) {
         JS_ASSERT(flags && !(flags & Store_));
         return AliasSet(flags | Store_);
     }
 };
 
-static const unsigned NUM_ALIAS_SETS = sizeof(AliasSet) * 8;
-
 // An MDefinition is an SSA name.
 class MDefinition : public MNode
 {
     friend class MBasicBlock;
     friend class Loop;
 
   public:
     enum Opcode {
@@ -448,16 +451,24 @@ class MDefinition : public MNode
     }
     virtual AliasSet getAliasSet() const {
         // Instructions are effectful by default.
         return AliasSet::Store(AliasSet::Any);
     }
     bool isEffectful() const {
         return getAliasSet().isStore();
     }
+    virtual bool mightAlias(MDefinition *store) {
+        // Return whether this load may depend on the specified store, given
+        // that the alias sets intersect. This may be refined to exclude
+        // possible aliasing in cases where alias set flags are too imprecise.
+        JS_ASSERT(!isEffectful() && store->isEffectful());
+        JS_ASSERT(getAliasSet().flags() & store->getAliasSet().flags());
+        return true;
+    }
 };
 
 // An MUseDefIterator walks over uses in a definition, skipping any use that is
 // not a definition. Items from the use list must not be deleted during
 // iteration.
 class MUseDefIterator
 {
     MDefinition *def_;
@@ -4136,18 +4147,20 @@ class MLoadFixedSlot
         if (!ins->isLoadFixedSlot())
             return false;
         if (slot() != ins->toLoadFixedSlot()->slot())
             return false;
         return congruentIfOperandsEqual(ins);
     }
 
     AliasSet getAliasSet() const {
-        return AliasSet::Load(AliasSet::Slot);
-    }
+        return AliasSet::Load(AliasSet::FixedSlot);
+    }
+
+    bool mightAlias(MDefinition *store);
 };
 
 class MStoreFixedSlot
   : public MBinaryInstruction,
     public SingleObjectPolicy
 {
     bool needsBarrier_;
     size_t slot_;
@@ -4178,17 +4191,17 @@ class MStoreFixedSlot
     MDefinition *value() const {
         return getOperand(1);
     }
     size_t slot() const {
         return slot_;
     }
 
     AliasSet getAliasSet() const {
-        return AliasSet::Store(AliasSet::Slot);
+        return AliasSet::Store(AliasSet::FixedSlot);
     }
     bool needsBarrier() const {
         return needsBarrier_;
     }
     void setNeedsBarrier() {
         needsBarrier_ = true;
     }
 };
@@ -4339,18 +4352,21 @@ class MGetPropertyCache
         if (!ins->isGetPropertyCache())
             return false;
         if (name() != ins->toGetPropertyCache()->name())
             return false;
         return congruentIfOperandsEqual(ins);
     }
 
     AliasSet getAliasSet() const {
-        if (idempotent_)
-            return AliasSet::Load(AliasSet::ObjectFields | AliasSet::Slot);
+        if (idempotent_) {
+            return AliasSet::Load(AliasSet::ObjectFields |
+                                  AliasSet::FixedSlot |
+                                  AliasSet::DynamicSlot);
+        }
         return AliasSet::Store(AliasSet::Any);
     }
 
 };
 
 // Represents a polymorphic dispatch to one or more functions.
 class MPolyInlineDispatch : public MControlInstruction, public SingleObjectPolicy
 {
@@ -4711,18 +4727,19 @@ class MLoadSlot
         if (!ins->isLoadSlot())
             return false;
         if (slot() != ins->toLoadSlot()->slot())
             return false;
         return congruentIfOperandsEqual(ins);
     }
     AliasSet getAliasSet() const {
         JS_ASSERT(slots()->type() == MIRType_Slots);
-        return AliasSet::Load(AliasSet::Slot);
-    }
+        return AliasSet::Load(AliasSet::DynamicSlot);
+    }
+    bool mightAlias(MDefinition *store);
 };
 
 // Inline call to access a function's environment (scope chain).
 class MFunctionEnvironment
   : public MUnaryInstruction,
     public SingleObjectPolicy
 {
   public:
@@ -4792,17 +4809,17 @@ class MStoreSlot
     }
     bool needsBarrier() const {
         return needsBarrier_;
     }
     void setNeedsBarrier() {
         needsBarrier_ = true;
     }
     AliasSet getAliasSet() const {
-        return AliasSet::Store(AliasSet::Slot);
+        return AliasSet::Store(AliasSet::DynamicSlot);
     }
 };
 
 class MGetNameCache
   : public MUnaryInstruction,
     public SingleObjectPolicy
 {
   public: