diff -r 000000000000 -r 6474c204b198 js/src/jit/AliasAnalysis.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/js/src/jit/AliasAnalysis.cpp	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,296 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "jit/AliasAnalysis.h"
+
+#include <stdio.h>
+
+#include "jit/Ion.h"
+#include "jit/IonBuilder.h"
+#include "jit/IonSpewer.h"
+#include "jit/MIR.h"
+#include "jit/MIRGraph.h"
+
+using namespace js;
+using namespace js::jit;
+
+using mozilla::Array;
+
+namespace js {
+namespace jit {
+
+class LoopAliasInfo : public TempObject
+{
+  private:
+    LoopAliasInfo *outer_;
+    MBasicBlock *loopHeader_;
+    MDefinitionVector invariantLoads_;
+
+  public:
+    LoopAliasInfo(TempAllocator &alloc, LoopAliasInfo *outer, MBasicBlock *loopHeader)
+      : outer_(outer), loopHeader_(loopHeader), invariantLoads_(alloc)
+    { }
+
+    MBasicBlock *loopHeader() const {
+        return loopHeader_;
+    }
+    LoopAliasInfo *outer() const {
+        return outer_;
+    }
+    bool addInvariantLoad(MDefinition *ins) {
+        return invariantLoads_.append(ins);
+    }
+    const MDefinitionVector& invariantLoads() const {
+        return invariantLoads_;
+    }
+    MDefinition *firstInstruction() const {
+        return *loopHeader_->begin();
+    }
+};
+
+} // namespace jit
+} // namespace js
+
+namespace {
+
+// Iterates over the flags in an AliasSet.
+class AliasSetIterator
+{
+  private:
+    uint32_t flags;
+    unsigned pos;
+
+  public:
+    AliasSetIterator(AliasSet set)
+      : flags(set.flags()), pos(0)
+    {
+        while (flags && (flags & 1) == 0) {
+            flags >>= 1;
+            pos++;
+        }
+    }
+    AliasSetIterator& operator ++(int) {
+        do {
+            flags >>= 1;
+            pos++;
+        } while (flags && (flags & 1) == 0);
+        return *this;
+    }
+    operator bool() const {
+        return !!flags;
+    }
+    unsigned operator *() const {
+        JS_ASSERT(pos < AliasSet::NumCategories);
+        return pos;
+    }
+};
+
+} /* anonymous namespace */
+
+AliasAnalysis::AliasAnalysis(MIRGenerator *mir, MIRGraph &graph)
+  : mir(mir),
+    graph_(graph),
+    loop_(nullptr)
+{
+}
+
+// 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: {
+            MBasicBlock *successor = src->getSuccessor(0);
+            if (successor->id() <= src->id())
+                return true; // Don't iloop.
+            src = successor;
+            break;
+          }
+          default:
+            return true;
+        }
+    }
+    return false;
+}
+
+static void
+IonSpewDependency(MDefinition *load, MDefinition *store, const char *verb, const char *reason)
+{
+    if (!IonSpewEnabled(IonSpew_Alias))
+        return;
+
+    fprintf(IonSpewFile, "Load ");
+    load->printName(IonSpewFile);
+    fprintf(IonSpewFile, " %s on store ", verb);
+    store->printName(IonSpewFile);
+    fprintf(IonSpewFile, " (%s)\n", reason);
+}
+
+static void
+IonSpewAliasInfo(const char *pre, MDefinition *ins, const char *post)
+{
+    if (!IonSpewEnabled(IonSpew_Alias))
+        return;
+
+    fprintf(IonSpewFile, "%s ", pre);
+    ins->printName(IonSpewFile);
+    fprintf(IonSpewFile, " %s\n", post);
+}
+
+// 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
+// information is used to mark every load we wrongly assumed to be loop invaraint as
+// 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<MDefinitionVector, AliasSet::NumCategories, IonAllocPolicy> stores(alloc());
+
+    // Initialize to the first instruction.
+    MDefinition *firstIns = *graph_.begin()->begin();
+    for (unsigned i = 0; i < AliasSet::NumCategories; i++) {
+        MDefinitionVector defs(alloc());
+        if (!defs.append(firstIns))
+            return false;
+        if (!stores.append(Move(defs)))
+            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;
+
+    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
+        if (mir->shouldCancel("Alias Analysis (main loop)"))
+            return false;
+
+        if (block->isLoopHeader()) {
+            IonSpew(IonSpew_Alias, "Processing loop header %d", block->id());
+            loop_ = new(alloc()) LoopAliasInfo(alloc(), loop_, *block);
+        }
+
+        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++) {
+                    if (!stores[*iter].append(*def))
+                        return false;
+                }
+
+                if (IonSpewEnabled(IonSpew_Alias)) {
+                    fprintf(IonSpewFile, "Processing store ");
+                    def->printName(IonSpewFile);
+                    fprintf(IonSpewFile, " (flags %x)\n", set.flags());
+                }
+            } else {
+                // Find the most recent store on which this instruction depends.
+                MDefinition *lastStore = firstIns;
+
+                for (AliasSetIterator iter(set); iter; iter++) {
+                    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);
+                IonSpewDependency(*def, lastStore, "depends", "");
+
+                // 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.
+                if (loop_ && lastStore->id() < loop_->firstInstruction()->id()) {
+                    if (!loop_->addInvariantLoad(*def))
+                        return false;
+                }
+            }
+        }
+
+        // Renumber the last instruction, as the analysis depends on this and the order.
+        block->lastIns()->setId(newId++);
+
+        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();
+            MInstruction *firstLoopIns = *loop_->loopHeader()->begin();
+
+            const MDefinitionVector &invariant = loop_->invariantLoads();
+
+            for (unsigned i = 0; i < invariant.length(); i++) {
+                MDefinition *ins = invariant[i];
+                AliasSet set = ins->getAliasSet();
+                JS_ASSERT(set.isLoad());
+
+                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;
+                            IonSpewDependency(ins, store, "aliases", "store in loop body");
+                            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();
+                    IonSpewDependency(ins, controlIns, "depends", "due to stores in loop body");
+                    ins->setDependency(controlIns);
+                } else {
+                    IonSpewAliasInfo("Load", ins, "does not depend on any stores in this loop");
+
+                    if (outerLoop && ins->dependency()->id() < outerLoop->firstInstruction()->id()) {
+                        IonSpewAliasInfo("Load", ins, "may be invariant in outer loop");
+                        if (!outerLoop->addInvariantLoad(ins))
+                            return false;
+                    }
+                }
+            }
+            loop_ = loop_->outer();
+        }
+    }
+
+    JS_ASSERT(loop_ == nullptr);
+    return true;
+}