Add m-esr52 at 52.6.0

1 files changed, 949 insertions, 0 deletions

diff --git a/js/src/jit/FlowAliasAnalysis.cpp b/js/src/jit/FlowAliasAnalysis.cpp
new file mode 100644
index 000000000..2b88e3678
--- /dev/null
+++ b/js/src/jit/FlowAliasAnalysis.cpp
@@ -0,0 +1,949 @@
+/* -*- 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/FlowAliasAnalysis.h"
+
+#include <stdio.h>
+
+#include "jit/AliasAnalysisShared.h"
+#include "jit/Ion.h"
+#include "jit/IonBuilder.h"
+#include "jit/JitSpewer.h"
+#include "jit/MIR.h"
+#include "jit/MIRGraph.h"
+
+#include "vm/Printer.h"
+
+using namespace js;
+using namespace js::jit;
+
+using mozilla::Array;
+
+namespace js {
+namespace jit {
+
+class LoopInfo : public TempObject
+{
+  private:
+    LoopInfo* outer_;
+    MBasicBlock* loopHeader_;
+    MDefinitionVector loopinvariant_;
+
+  public:
+    LoopInfo(TempAllocator& alloc, LoopInfo* outer, MBasicBlock* loopHeader)
+      : outer_(outer), loopHeader_(loopHeader), loopinvariant_(alloc)
+    { }
+
+    MBasicBlock* loopHeader() const {
+        return loopHeader_;
+    }
+    LoopInfo* outer() const {
+        return outer_;
+    }
+    MDefinitionVector& loopinvariant() {
+        return loopinvariant_;
+    }
+};
+
+static bool
+KeepBlock(MBasicBlock *block)
+{
+    // Any block that is predecessor to a loopheader need to be kept.
+    // We need it to process possible loop invariant loads.
+    if (block->numSuccessors() == 1 && block->getSuccessor(0)->isLoopHeader())
+        return true;
+
+#ifdef DEBUG
+    // We assume a predecessor to a loopheader has one successor.
+    for (size_t i = 0; i < block->numSuccessors(); i++)
+        MOZ_ASSERT(!block->getSuccessor(i)->isLoopHeader());
+#endif
+
+    return false;
+}
+
+class GraphStoreInfo : public TempObject
+{
+    // The current BlockStoreInfo while iterating the block untill,
+    // it contains the store info at the end of the block.
+    BlockStoreInfo* current_;
+
+    // Vector with pointer to BlockStoreInfo at the end of the block for every block.
+    // Only keeping the info during iteration if needed, else contains nullptr.
+    GraphStoreVector stores_;
+
+    // All BlockStoreInfo's that aren't needed anymore and can be reused.
+    GraphStoreVector empty_;
+
+  public:
+    explicit GraphStoreInfo(TempAllocator& alloc)
+      : current_(nullptr),
+        stores_(alloc),
+        empty_(alloc)
+    { }
+
+    bool reserve(size_t num) {
+        return stores_.appendN(nullptr, num);
+    }
+
+    BlockStoreInfo& current() {
+        return *current_;
+    }
+
+    void unsetCurrent() {
+        current_ = nullptr;
+    }
+
+    BlockStoreInfo* newCurrent(TempAllocator& alloc, MBasicBlock* block) {
+        BlockStoreInfo *info = nullptr;
+        if (empty_.length() != 0) {
+            info = empty_.popCopy();
+        } else {
+            info = (BlockStoreInfo*) alloc.allocate(sizeof(BlockStoreInfo));
+            if (!info)
+                return nullptr;
+            new(info) BlockStoreInfo(alloc);
+        }
+
+        stores_[block->id()] = info;
+        current_ = info;
+        return current_;
+    }
+
+    void swap(MBasicBlock* block1, MBasicBlock* block2) {
+        BlockStoreInfo* info = stores_[block1->id()];
+        stores_[block1->id()] = stores_[block2->id()];
+        stores_[block2->id()] = info;
+        if (stores_[block1->id()] == current_)
+            current_ = stores_[block2->id()];
+        else if (stores_[block2->id()] == current_)
+            current_ = stores_[block1->id()];
+    }
+
+    bool maybeFreePredecessorBlocks(MBasicBlock* block) {
+        for (size_t i=0; i < block->numPredecessors(); i++) {
+
+            // For some blocks we cannot free the store info.
+            if (KeepBlock(block->getPredecessor(i)))
+                continue;
+
+            // Check the given block is the last successor.
+            bool release = true;
+            for (size_t j = 0; j < block->getPredecessor(i)->numSuccessors(); j++) {
+                if (block->getPredecessor(i)->getSuccessor(j)->id() > block->id()) {
+                    release = false;
+                    break;
+                }
+            }
+            if (release) {
+                BlockStoreInfo *info = stores_[block->getPredecessor(i)->id()];
+                if (!empty_.append(info))
+                    return false;
+                info->clear();
+
+                stores_[block->getPredecessor(i)->id()] = nullptr;
+            }
+        }
+        return true;
+    }
+
+    BlockStoreInfo& get(MBasicBlock* block) {
+        MOZ_ASSERT(stores_[block->id()] != current_);
+        return *stores_[block->id()];
+    }
+};
+
+} // namespace jit
+} // namespace js
+
+
+FlowAliasAnalysis::FlowAliasAnalysis(MIRGenerator* mir, MIRGraph& graph)
+  : AliasAnalysisShared(mir, graph),
+    loop_(nullptr),
+    output_(graph_.alloc()),
+    worklist_(graph_.alloc())
+{
+    stores_ = new(graph_.alloc()) GraphStoreInfo(graph_.alloc());
+}
+
+template <typename T>
+static bool
+AppendToWorklist(MDefinitionVector& worklist, T& stores)
+{
+    if (!worklist.reserve(worklist.length() + stores.length()))
+        return false;
+
+    for (size_t j = 0; j < stores.length(); j++) {
+        MOZ_ASSERT(stores[j]);
+        if (stores[j]->isInWorklist())
+            continue;
+
+        worklist.infallibleAppend(stores[j]);
+        stores[j]->setInWorklist();
+    }
+    return true;
+}
+
+static void
+SetNotInWorkList(MDefinitionVector& worklist)
+{
+    for (size_t item = 0; item < worklist.length(); item++)
+        worklist[item]->setNotInWorklistUnchecked();
+}
+
+static bool
+LoadAliasesStore(MDefinition* load, MDefinition* store)
+{
+    // Always alias first instruction of graph.
+    if (store->id() == 0)
+        return true;
+
+    // Default to alias control instructions which indicates loops.
+    // Control instructions are special, since we need to determine
+    // if it aliases anything in the full loop. Which we do lateron.
+    if (store->isControlInstruction())
+        return true;
+
+    // Check if the alias categories alias eachother.
+    if ((load->getAliasSet() & store->getAliasSet()).isNone())
+        return false;
+
+    // On any operation that has a specific alias category we can use TI to know
+    // the objects operating on don't intersect.
+    MDefinition::AliasType mightAlias = AliasAnalysisShared::genericMightAlias(load, store);
+    if (mightAlias == MDefinition::AliasType::NoAlias)
+        return false;
+
+    // Check if the instruction might alias eachother.
+    mightAlias = load->mightAlias(store);
+    if (mightAlias == MDefinition::AliasType::NoAlias)
+        return false;
+
+    return true;
+}
+
+#ifdef JS_JITSPEW
+static void
+DumpAliasSet(AliasSet set)
+{
+    Fprinter &print = JitSpewPrinter();
+
+    if (set.flags() == AliasSet::Any) {
+        print.printf("Any");
+        return;
+    }
+
+    bool first = true;
+    for (AliasSetIterator iter(set); iter; iter++) {
+        if (!first)
+            print.printf(", ");
+        print.printf("%s", AliasSet::Name(*iter));
+        first = false;
+    }
+}
+#endif
+
+#ifdef JS_JITSPEW
+static void
+DumpStoreList(BlockStoreInfo& stores)
+{
+    Fprinter &print = JitSpewPrinter();
+    if (stores.length() == 0) {
+        print.printf("empty");
+        return;
+    }
+    bool first = true;
+    for (size_t i = 0; i < stores.length(); i++) {
+        if (!first)
+            print.printf(", ");
+        if (!stores[i]) {
+            print.printf("nullptr");
+            continue;
+        }
+        MOZ_ASSERT(stores[i]->isControlInstruction() ||
+                   stores[i]->getAliasSet().isStore() ||
+                   stores[i]->id() == 0);
+        MDefinition::PrintOpcodeName(print, stores[i]->op());
+        print.printf("%d", stores[i]->id());
+        first = false;
+    }
+}
+#endif
+
+static void
+DumpAnalyzeStart()
+{
+#ifdef JS_JITSPEW
+    if (JitSpewEnabled(JitSpew_Alias) || JitSpewEnabled(JitSpew_AliasSummaries)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpewEnabled(JitSpew_Alias) ? JitSpew_Alias : JitSpew_AliasSummaries);
+        print.printf("Running Alias Analysis on graph\n");
+    }
+#endif
+}
+
+static void
+DumpBlockStart(MBasicBlock* block)
+{
+#ifdef JS_JITSPEW
+    if (JitSpewEnabled(JitSpew_Alias) || JitSpewEnabled(JitSpew_AliasSummaries)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpewEnabled(JitSpew_Alias)?JitSpew_Alias:JitSpew_AliasSummaries);
+        if (block->isLoopHeader())
+            print.printf(" Visiting block %d (loopheader)\n", block->id());
+        else
+            print.printf(" Visiting block %d\n", block->id());
+    }
+#endif
+}
+
+static void
+DumpProcessingDeferredLoads(MBasicBlock* loopHeader)
+{
+#ifdef JS_JITSPEW
+    if (JitSpewEnabled(JitSpew_Alias)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpew_Alias);
+        print.printf(" Process deferred loads of loop %d\n", loopHeader->id());
+    }
+#endif
+}
+
+static void
+DumpBlockSummary(MBasicBlock* block, BlockStoreInfo& blockInfo)
+{
+#ifdef JS_JITSPEW
+    if (JitSpewEnabled(JitSpew_AliasSummaries)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpew_AliasSummaries);
+        print.printf("  Store at end of block: ");
+        DumpStoreList(blockInfo);
+        print.printf("\n");
+    }
+#endif
+}
+
+static void
+DumpStore(MDefinition* store)
+{
+#ifdef JS_JITSPEW
+    if (JitSpewEnabled(JitSpew_Alias)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpew_Alias);
+        print.printf("  Store ");
+        store->PrintOpcodeName(print, store->op());
+        print.printf("%d with flags (", store->id());
+        DumpAliasSet(store->getAliasSet());
+        print.printf(")\n");
+    }
+#endif
+}
+
+static void
+DumpLoad(MDefinition* load)
+{
+#ifdef JS_JITSPEW
+    if (JitSpewEnabled(JitSpew_Alias)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpew_Alias);
+        print.printf("  Load ");
+        load->PrintOpcodeName(print, load->op());
+        print.printf("%d", load->id());
+        print.printf(" with flag (");
+        DumpAliasSet(load->getAliasSet());
+        print.printf(")\n");
+    }
+#endif
+}
+
+static void
+DumpLoadOutcome(MDefinition* load, MDefinitionVector& stores, bool defer)
+{
+#ifdef JS_JITSPEW
+    // Spew what we did.
+    if (JitSpewEnabled(JitSpew_Alias)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpew_Alias);
+        print.printf("   Marked depending on ");
+        DumpStoreList(stores);
+        if (defer)
+            print.printf(" deferred");
+        print.printf("\n");
+    }
+#endif
+}
+
+static void
+DumpLoopInvariant(MDefinition* load, MBasicBlock* loopheader, bool loopinvariant,
+                  MDefinitionVector& loopInvariantDependency)
+{
+#ifdef JS_JITSPEW
+    if (JitSpewEnabled(JitSpew_Alias)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpew_Alias);
+        if (!loopinvariant) {
+            print.printf("   Determine not loop invariant to loop %d.\n", loopheader->id());
+        } else {
+            print.printf("   Determine loop invariant to loop %d. Dependendy is now: ", loopheader->id());
+            DumpStoreList(loopInvariantDependency);
+            print.printf("\n");
+        }
+    }
+#endif
+}
+
+static void
+DumpImprovement(MDefinition *load, MDefinitionVector& input, MDefinitionVector& output)
+{
+#ifdef JS_JITSPEW
+    if (JitSpewEnabled(JitSpew_Alias)) {
+        Fprinter &print = JitSpewPrinter();
+        JitSpewHeader(JitSpew_Alias);
+        print.printf("   Improve dependency from %d", load->id());
+        DumpStoreList(input);
+        print.printf(" to ");
+        DumpStoreList(output);
+        print.printf("\n");
+    }
+#endif
+}
+
+// Flow Sensitive Alias Analysis.
+//
+// This pass annotates every load instructions with the last store instruction
+// on which it depends in their dependency_ field. For loop variant instructions
+// this will depend on the control instruction in the specific loop it cannot
+// get hoisted out (if there is no store between start loopheader and
+// instruction).
+//
+// We visit the graph in RPO and keep track of the last stores in that block.
+// Upon entering a block we merge the stores information of the predecessors.
+// Only loopheaders are different, since we eagerly make it depend on the
+// control instruction of the loopheader.
+//
+// During the iteration of a block we keep a running store dependeny list.
+// At the end of the iteration, this will contain the last stores
+// (which we keep for successors).
+//
+// When encountering a store or load we do:
+// - Store: we update the current block store info and put a StoreDependency
+//          to create a store-chain.
+//
+// - Load: we take the current block store dependency info and improve that by
+//         following the store-chain when encountering not aliasing store. Upon
+//         encountering a control instruction (indicates loop) it solely depends on
+//         we defer until the loop has been examined.
+//
+// The algorithm depends on the invariant that both control instructions and effectful
+// instructions (stores) are never hoisted.
+
+bool
+FlowAliasAnalysis::analyze()
+{
+    DumpAnalyzeStart();
+
+    // Type analysis may have inserted new instructions. Since this pass depends
+    // on the instruction number ordering, all instructions are renumbered.
+    uint32_t newId = 0;
+
+    if (!stores_->reserve(graph_.numBlocks()))
+        return false;
+
+    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
+        if (mir->shouldCancel("Alias Analysis (main loop)"))
+            return false;
+
+        DumpBlockStart(*block);
+
+        if (!computeBlockStores(*block))
+            return false;
+        if (!stores_->maybeFreePredecessorBlocks(*block))
+            return false;
+
+        if (block->isLoopHeader())
+            loop_ = new(alloc()) LoopInfo(alloc(), loop_, *block);
+
+        for (MPhiIterator def(block->phisBegin()), end(block->phisEnd()); def != end; ++def)
+            def->setId(newId++);
+
+        BlockStoreInfo& blockInfo = stores_->current();
+        for (MInstructionIterator def(block->begin()), end(block->begin(block->lastIns()));
+                def != end;
+                ++def)
+        {
+            def->setId(newId++);
+
+            // For the purposes of alias analysis, all recoverable operations
+            // are treated as effect free as the memory represented by these
+            // operations cannot be aliased by others.
+            if (def->canRecoverOnBailout())
+                continue;
+
+            AliasSet set = def->getAliasSet();
+            if (set.isStore()) {
+                if (!processStore(blockInfo, *def))
+                    return false;
+            } else if (set.isLoad()) {
+                if (!processLoad(blockInfo, *def))
+                    return false;
+            }
+        }
+
+        block->lastIns()->setId(newId++);
+
+        if (block->isLoopBackedge()) {
+            stores_->unsetCurrent();
+
+            LoopInfo* info = loop_;
+            loop_ = loop_->outer();
+
+            if (!processDeferredLoads(info))
+                return false;
+        }
+
+        DumpBlockSummary(*block, blockInfo);
+    }
+
+    spewDependencyList();
+    return true;
+}
+
+bool
+FlowAliasAnalysis::processStore(BlockStoreInfo& blockInfo, MDefinition* store)
+{
+    // Compute and set dependency information.
+    if (!saveStoreDependency(store, blockInfo))
+        return false;
+
+    // Update the block store dependency vector.
+    blockInfo.clear();
+    if (!blockInfo.append(store))
+        return false;
+
+    // Spew what we did.
+    DumpStore(store);
+    return true;
+}
+
+bool
+FlowAliasAnalysis::processLoad(BlockStoreInfo& blockInfo, MDefinition* load)
+{
+    DumpLoad(load);
+
+    // Compute dependency information.
+    MDefinitionVector& dependencies = blockInfo;
+    if (!improveDependency(load, dependencies, output_))
+        return false;
+    saveLoadDependency(load, output_);
+
+    // If possible defer when better loop information is present.
+    if (deferImproveDependency(output_)) {
+        if (!loop_->loopinvariant().append(load))
+            return false;
+
+        DumpLoadOutcome(load, output_, /* defer = */ true);
+        return true;
+    }
+
+    DumpLoadOutcome(load, output_, /* defer = */ false);
+    return true;
+}
+
+bool
+FlowAliasAnalysis::processDeferredLoads(LoopInfo* info)
+{
+    DumpProcessingDeferredLoads(info->loopHeader());
+    MOZ_ASSERT(loopIsFinished(info->loopHeader()));
+
+    for (size_t i = 0; i < info->loopinvariant().length(); i++) {
+        MDefinition* load = info->loopinvariant()[i];
+
+        DumpLoad(load);
+
+        // Defer load again when this loop still isn't finished yet.
+        if (!loopIsFinished(load->dependency()->block())) {
+            MOZ_ASSERT(loop_);
+            if (!loop_->loopinvariant().append(load))
+                return false;
+
+            DumpLoadOutcome(load, output_, /* defer = */ true);
+            continue;
+        }
+
+        MOZ_ASSERT(load->dependency()->block() == info->loopHeader());
+        MDefinition* store = load->dependency();
+        load->setDependency(nullptr);
+
+        // Test if this load is loop invariant and if it is,
+        // take the dependencies of non-backedge predecessors of the loop header.
+        bool loopinvariant;
+        if (!isLoopInvariant(load, store, &loopinvariant))
+            return false;
+        MDefinitionVector &loopInvariantDependency =
+            stores_->get(store->block()->loopPredecessor());
+
+        DumpLoopInvariant(load, info->loopHeader(), /* loopinvariant = */ loopinvariant,
+                          loopInvariantDependency);
+
+        if (loopinvariant) {
+            if (!improveDependency(load, loopInvariantDependency, output_))
+                return false;
+            saveLoadDependency(load, output_);
+
+            // If possible defer when better loop information is present.
+            if (deferImproveDependency(output_)) {
+                if (!loop_->loopinvariant().append(load))
+                    return false;
+
+                DumpLoadOutcome(load, output_, /* defer = */ true);
+            } else {
+                DumpLoadOutcome(load, output_, /* defer = */ false);
+            }
+
+        } else {
+            load->setDependency(store);
+
+#ifdef JS_JITSPEW
+            output_.clear();
+            if (!output_.append(store))
+                return false;
+            DumpLoadOutcome(load, output_, /* defer = */ false);
+#endif
+        }
+
+    }
+    return true;
+}
+
+// Given a load instruction and an initial store dependency list,
+// find the most accurate store dependency list.
+bool
+FlowAliasAnalysis::improveDependency(MDefinition* load, MDefinitionVector& inputStores,
+                                     MDefinitionVector& outputStores)
+{
+    MOZ_ASSERT(inputStores.length() > 0);
+    outputStores.clear();
+    if (!outputStores.appendAll(inputStores))
+        return false;
+
+    bool improved = false;
+    bool adjusted = true;
+    while (adjusted) {
+        adjusted = false;
+        if (!improveNonAliasedStores(load, outputStores, outputStores, &improved))
+            return false;
+        MOZ_ASSERT(outputStores.length() != 0);
+        if (!improveStoresInFinishedLoops(load, outputStores, &adjusted))
+            return false;
+        if (adjusted)
+            improved = true;
+    }
+
+    if (improved)
+        DumpImprovement(load, inputStores, outputStores);
+
+    return true;
+}
+
+// For every real store dependencies, follow the chain of stores to find the
+// unique set of 'might alias' store dependencies.
+bool
+FlowAliasAnalysis::improveNonAliasedStores(MDefinition* load, MDefinitionVector& inputStores,
+                                           MDefinitionVector& outputStores, bool* improved,
+                                           bool onlyControlInstructions)
+{
+    MOZ_ASSERT(worklist_.length() == 0);
+    if (!AppendToWorklist(worklist_, inputStores))
+        return false;
+    outputStores.clear();
+
+    for (size_t i = 0; i < worklist_.length(); i++) {
+        MOZ_ASSERT(worklist_[i]);
+
+        if (!LoadAliasesStore(load, worklist_[i])) {
+            StoreDependency* dep = worklist_[i]->storeDependency();
+            MOZ_ASSERT(dep);
+            MOZ_ASSERT(dep->get().length() > 0);
+
+            if (!AppendToWorklist(worklist_, dep->get()))
+                return false;
+
+            *improved = true;
+            continue;
+        }
+
+        if (onlyControlInstructions && !worklist_[i]->isControlInstruction()) {
+            outputStores.clear();
+            break;
+        }
+        if (!outputStores.append(worklist_[i]))
+            return false;
+    }
+
+    SetNotInWorkList(worklist_);
+    worklist_.clear();
+    return true;
+}
+
+// Given a load instruction and an initial store dependency list,
+// find the most accurate store dependency list with only control instructions.
+// Returns an empty output list, when there was a non control instructions
+// that couldn't get improved to a control instruction.
+bool
+FlowAliasAnalysis::improveLoopDependency(MDefinition* load, MDefinitionVector& inputStores,
+                                         MDefinitionVector& outputStores)
+{
+    outputStores.clear();
+    if (!outputStores.appendAll(inputStores))
+        return false;
+
+    bool improved = false;
+    bool adjusted = true;
+    while (adjusted) {
+        adjusted = false;
+        if (!improveNonAliasedStores(load, outputStores, outputStores, &improved,
+                                      /* onlyControlInstructions = */ true))
+        {
+            return false;
+        }
+        if (outputStores.length() == 0)
+            return true;
+        if (!improveStoresInFinishedLoops(load, outputStores, &adjusted))
+            return false;
+        if (adjusted)
+            improved = true;
+    }
+
+    if (improved)
+        DumpImprovement(load, inputStores, outputStores);
+
+    return true;
+}
+
+// For every control instruction in the output we find out if the load is loop
+// invariant to that loop. When it is, improve the output dependency store,
+// by pointing to the stores before the loop.
+bool
+FlowAliasAnalysis::improveStoresInFinishedLoops(MDefinition* load, MDefinitionVector& stores,
+                                                bool* improved)
+{
+    for (size_t i = 0; i < stores.length(); i++) {
+        if (!stores[i]->isControlInstruction())
+            continue;
+        if (!stores[i]->block()->isLoopHeader())
+            continue;
+
+        MOZ_ASSERT(!stores[i]->storeDependency());
+
+        if (!loopIsFinished(stores[i]->block()))
+            continue;
+
+        if (load->dependency() == stores[i])
+            continue;
+
+        bool loopinvariant;
+        if (!isLoopInvariant(load, stores[i], &loopinvariant))
+            return false;
+        if (!loopinvariant)
+            continue;
+
+        MBasicBlock* pred = stores[i]->block()->loopPredecessor();
+        BlockStoreInfo& predInfo = stores_->get(pred);
+
+        MOZ_ASSERT(predInfo.length() > 0);
+        stores[i] = predInfo[0];
+        for (size_t j = 1; j < predInfo.length(); j++) {
+            if (!stores.append(predInfo[j]))
+                return false;
+        }
+
+        *improved = true;
+    }
+
+    return true;
+}
+
+bool
+FlowAliasAnalysis::deferImproveDependency(MDefinitionVector& stores)
+{
+    // Look if the store depends only on 1 non finished loop.
+    // In that case we will defer until that loop has finished.
+    return loop_ && stores.length() == 1 &&
+           stores[0]->isControlInstruction() &&
+           stores[0]->block()->isLoopHeader() &&
+           !loopIsFinished(stores[0]->block());
+}
+
+void
+FlowAliasAnalysis::saveLoadDependency(MDefinition* load, MDefinitionVector& dependencies)
+{
+    MOZ_ASSERT(dependencies.length() > 0);
+
+    // For now we only save the last store before the load for other passes.
+    // That means the store with the maximum id.
+    MDefinition* max = dependencies[0];
+    MDefinition* maxNonControl = nullptr;
+    for (size_t i = 0; i < dependencies.length(); i++) {
+        MDefinition* ins = dependencies[i];
+        if (max->id() < ins->id())
+            max = ins;
+        if (!ins->isControlInstruction()) {
+            if (!maxNonControl || maxNonControl->id() < ins->id())
+                maxNonControl = ins;
+        }
+    }
+
+    // For loop variant loads with no stores between loopheader and the load,
+    // the control instruction of the loop header is returned.
+    // That id is higher than any store inside the loopheader itself.
+    // Fix for dependency on item in loopheader, but before the "test".
+    // Which would assume it depends on the loop itself.
+    if (maxNonControl != max && maxNonControl) {
+        if (maxNonControl->block() == max->block())
+            max = maxNonControl;
+    }
+
+    load->setDependency(max);
+}
+
+bool
+FlowAliasAnalysis::saveStoreDependency(MDefinition* ins, BlockStoreInfo& prevStores)
+{
+    // To form a store dependency chain, we store the previous last dependencies
+    // in the current store.
+
+    StoreDependency* dependency = new(alloc()) StoreDependency(alloc());
+    if (!dependency)
+        return false;
+    if (!dependency->init(prevStores))
+        return false;
+
+    ins->setStoreDependency(dependency);
+    return true;
+}
+
+// Returns if loop has been processed
+// and has complete backedge stores information.
+bool
+FlowAliasAnalysis::loopIsFinished(MBasicBlock* loopheader)
+{
+    MOZ_ASSERT(loopheader->isLoopHeader());
+
+    if (!loop_)
+        return true;
+
+    return loopheader->backedge()->id() <
+           loop_->loopHeader()->backedge()->id();
+}
+
+
+// Determines if a load is loop invariant.
+//
+// Get the last store dependencies of the backedge of the loop and follow
+// the store chain until finding the aliased stores. Make sure the computed
+// aliased stores is only the loop control instruction or control instructions
+// of loops it is also loop invariant. Only in that case the load is
+// definitely loop invariant.
+bool
+FlowAliasAnalysis::isLoopInvariant(MDefinition* load, MDefinition* store, bool* loopinvariant)
+{
+    MOZ_ASSERT(store->isControlInstruction());
+    MOZ_ASSERT(!store->storeDependency());
+    MOZ_ASSERT(store->block()->isLoopHeader());
+    MOZ_ASSERT(loopIsFinished(store->block()));
+
+    *loopinvariant = false;
+    MBasicBlock* backedge = store->block()->backedge();
+    MDefinitionVector output(alloc());
+
+    // To make sure the improve dependency stops at this loop,
+    // set the loop control instruction as dependency.
+    MDefinition* olddep = load->dependency();
+    load->setDependency(store);
+    if (!improveLoopDependency(load, stores_->get(backedge), output))
+        return false;
+    load->setDependency(olddep);
+
+    if (output.length() == 0)
+        return true;
+
+    for (size_t i = 0; i < output.length(); i++) {
+        if (output[i]->storeDependency())
+            return true;
+
+        if (!output[i]->isControlInstruction())
+            return true;
+        if (!output[i]->block()->isLoopHeader())
+            return true;
+
+        if (output[i] == store)
+            continue;
+
+        return true;
+    }
+
+    *loopinvariant = true;
+    return true;
+}
+
+// Compute the store dependencies at the start of this MBasicBlock.
+bool
+FlowAliasAnalysis::computeBlockStores(MBasicBlock* block)
+{
+    BlockStoreInfo* blockInfo = stores_->newCurrent(alloc(), block);
+    if (!blockInfo)
+        return false;
+
+    // First block depends on the first instruction.
+    if (block->id() == 0) {
+        MDefinition* firstIns = *graph_.entryBlock()->begin();
+        if (!blockInfo->append(firstIns))
+            return false;
+        return true;
+    }
+
+    // For loopheaders we take the loopheaders control instruction.
+    // That is not moveable and easy is to detect.
+    if (block->isLoopHeader()) {
+        if (!blockInfo->append(block->lastIns()))
+            return false;
+        return true;
+    }
+
+
+    // Optimization for consecutive blocks.
+    if (block->numPredecessors() == 1) {
+        MBasicBlock* pred = block->getPredecessor(0);
+        if (pred->numSuccessors() == 1) {
+            stores_->swap(block, pred);
+            return true;
+        }
+        MOZ_ASSERT (pred->numSuccessors() > 1);
+        BlockStoreInfo& predInfo = stores_->get(pred);
+        return blockInfo->appendAll(predInfo);
+    }
+
+    // Heuristic: in most cases having more than 5 predecessors,
+    // increases the number of dependencies too much to still be able
+    // to do an optimization. Therefore don't do the merge work.
+    // For simplicity we take an non-dominant always existing instruction.
+    // That way we cannot accidentally move instructions depending on it.
+    if (block->numPredecessors() > 5) {
+        if (!blockInfo->append(block->getPredecessor(0)->lastIns()))
+            return false;
+        return true;
+    }
+
+    // Merging of multiple predecessors.
+    for (size_t pred = 0; pred < block->numPredecessors(); pred++) {
+        BlockStoreInfo& predInfo = stores_->get(block->getPredecessor(pred));
+        if (!AppendToWorklist(*blockInfo, predInfo))
+            return false;
+    }
+    SetNotInWorkList(*blockInfo);
+
+    return true;
+}