diff options
Diffstat (limited to 'js/src/jit/FlowAliasAnalysis.cpp')
| -rw-r--r-- | js/src/jit/FlowAliasAnalysis.cpp | 949 |
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; +} |