/* -*- 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; }