summaryrefslogtreecommitdiffstats
path: root/js/src/jit/FlowAliasAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/jit/FlowAliasAnalysis.cpp')
-rw-r--r--js/src/jit/FlowAliasAnalysis.cpp949
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;
+}