From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- js/src/jit/AliasAnalysis.cpp | 339 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 339 insertions(+) create mode 100644 js/src/jit/AliasAnalysis.cpp (limited to 'js/src/jit/AliasAnalysis.cpp') diff --git a/js/src/jit/AliasAnalysis.cpp b/js/src/jit/AliasAnalysis.cpp new file mode 100644 index 0000000000..00b7829e11 --- /dev/null +++ b/js/src/jit/AliasAnalysis.cpp @@ -0,0 +1,339 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "jit/AliasAnalysis.h" + +#include "mozilla/DebugOnly.h" + +#include "jit/JitSpewer.h" +#include "jit/MIR.h" +#include "jit/MIRGenerator.h" +#include "jit/MIRGraph.h" + +#include "js/Printer.h" + +using namespace js; +using namespace js::jit; + +namespace js { +namespace jit { + +class LoopAliasInfo : public TempObject { + private: + LoopAliasInfo* outer_; + MBasicBlock* loopHeader_; + MInstructionVector invariantLoads_; + + public: + LoopAliasInfo(TempAllocator& alloc, LoopAliasInfo* outer, + MBasicBlock* loopHeader) + : outer_(outer), loopHeader_(loopHeader), invariantLoads_(alloc) {} + + MBasicBlock* loopHeader() const { return loopHeader_; } + LoopAliasInfo* outer() const { return outer_; } + bool addInvariantLoad(MInstruction* ins) { + return invariantLoads_.append(ins); + } + const MInstructionVector& invariantLoads() const { return invariantLoads_; } + MInstruction* firstInstruction() const { return *loopHeader_->begin(); } +}; + +} // namespace jit +} // namespace js + +void AliasAnalysis::spewDependencyList() { +#ifdef JS_JITSPEW + if (JitSpewEnabled(JitSpew_AliasSummaries)) { + Fprinter& print = JitSpewPrinter(); + JitSpewHeader(JitSpew_AliasSummaries); + print.printf("Dependency list for other passes:\n"); + + for (ReversePostorderIterator block(graph_.rpoBegin()); + block != graph_.rpoEnd(); block++) { + for (MInstructionIterator def(block->begin()), + end(block->begin(block->lastIns())); + def != end; ++def) { + if (!def->dependency()) { + continue; + } + if (!def->getAliasSet().isLoad()) { + continue; + } + + JitSpewHeader(JitSpew_AliasSummaries); + print.printf(" "); + MDefinition::PrintOpcodeName(print, def->op()); + print.printf("%u marked depending on ", def->id()); + MDefinition::PrintOpcodeName(print, def->dependency()->op()); + print.printf("%u\n", def->dependency()->id()); + } + } + } +#endif +} + +// Whether there might be a path from src to dest, excluding loop backedges. +// This is approximate and really ought to depend on precomputed reachability +// information. +static inline bool BlockMightReach(MBasicBlock* src, MBasicBlock* dest) { + while (src->id() <= dest->id()) { + if (src == dest) { + return true; + } + switch (src->numSuccessors()) { + case 0: + return false; + case 1: { + MBasicBlock* successor = src->getSuccessor(0); + if (successor->id() <= src->id()) { + return true; // Don't iloop. + } + src = successor; + break; + } + default: + return true; + } + } + return false; +} + +static void IonSpewDependency(MInstruction* load, MInstruction* store, + const char* verb, const char* reason) { +#ifdef JS_JITSPEW + if (!JitSpewEnabled(JitSpew_Alias)) { + return; + } + + JitSpewHeader(JitSpew_Alias); + Fprinter& out = JitSpewPrinter(); + out.printf(" Load "); + load->printName(out); + out.printf(" %s on store ", verb); + store->printName(out); + out.printf(" (%s)\n", reason); +#endif +} + +static void IonSpewAliasInfo(const char* pre, MInstruction* ins, + const char* post) { +#ifdef JS_JITSPEW + if (!JitSpewEnabled(JitSpew_Alias)) { + return; + } + + JitSpewHeader(JitSpew_Alias); + Fprinter& out = JitSpewPrinter(); + out.printf(" %s ", pre); + ins->printName(out); + out.printf(" %s\n", post); +#endif +} + +// [SMDOC] IonMonkey Alias Analysis +// +// This pass annotates every load instruction with the last store instruction +// on which it depends. The algorithm is optimistic in that it ignores explicit +// dependencies and only considers loads and stores. +// +// Loads inside loops only have an implicit dependency on a store before the +// loop header if no instruction inside the loop body aliases it. To calculate +// this efficiently, we maintain a list of maybe-invariant loads and the +// combined alias set for all stores inside the loop. When we see the loop's +// backedge, this information is used to mark every load we wrongly assumed to +// be loop invariant as having an implicit dependency on the last instruction of +// the loop header, so that it's never moved before the loop header. +// +// The algorithm depends on the invariant that both control instructions and +// effectful instructions (stores) are never hoisted. +bool AliasAnalysis::analyze() { + JitSpew(JitSpew_Alias, "Begin"); + Vector stores( + alloc()); + + // Initialize to the first instruction. + MInstruction* firstIns = *graph_.entryBlock()->begin(); + for (unsigned i = 0; i < AliasSet::NumCategories; i++) { + MInstructionVector defs(alloc()); + if (!defs.append(firstIns)) { + return false; + } + if (!stores.append(std::move(defs))) { + return false; + } + } + + // Type analysis may have inserted new instructions. Since this pass depends + // on the instruction number ordering, all instructions are renumbered. + uint32_t newId = 0; + + for (ReversePostorderIterator block(graph_.rpoBegin()); + block != graph_.rpoEnd(); block++) { + if (mir->shouldCancel("Alias Analysis (main loop)")) { + return false; + } + + if (block->isLoopHeader()) { + JitSpew(JitSpew_Alias, "Processing loop header %u", block->id()); + loop_ = new (alloc().fallible()) LoopAliasInfo(alloc(), loop_, *block); + if (!loop_) { + return false; + } + } + + for (MPhiIterator def(block->phisBegin()), end(block->phisEnd()); + def != end; ++def) { + def->setId(newId++); + } + + { + // "The block has one or more instructions" + MOZ_ASSERT(block->hasAnyIns()); + // "The last instruction is a control instruction" + MOZ_ASSERT(block->hasLastIns()); + // "The only control instructions that can have a non-empty alias set + // are MWasmCallCatchable and MWasmReturnCall". + // Note, this isn't a requirement that is intrinsic to MIR. In + // principle, any control instruction can have a non-empty alias set, + // and that should be correctly handled by this routine. The assertion + // merely reflects the current state of usage of MIR, in which + // MWasmCallCatchable and MWasmReturnCall are the only control + // instructions we generate that have non-empty alias sets. + // See bug 1837686. + mozilla::DebugOnly lastIns = block->lastIns(); + MOZ_ASSERT_IF( + !lastIns->isWasmCallCatchable() && !lastIns->isWasmReturnCall(), + lastIns->getAliasSet().isNone()); + } + + for (MInstructionIterator def(block->begin()), end(block->end()); + def != end; ++def) { + def->setId(newId++); + + AliasSet set = def->getAliasSet(); + if (set.isNone()) { + continue; + } + + // 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; + } + + if (set.isStore()) { + for (AliasSetIterator iter(set); iter; iter++) { + if (!stores[*iter].append(*def)) { + return false; + } + } + +#ifdef JS_JITSPEW + if (JitSpewEnabled(JitSpew_Alias)) { + JitSpewHeader(JitSpew_Alias); + Fprinter& out = JitSpewPrinter(); + out.printf("Processing store "); + def->printName(out); + out.printf(" (flags %x)\n", set.flags()); + } +#endif + } else { + // Find the most recent store on which this instruction depends. + MInstruction* lastStore = firstIns; + + for (AliasSetIterator iter(set); iter; iter++) { + MInstructionVector& aliasedStores = stores[*iter]; + for (int i = aliasedStores.length() - 1; i >= 0; i--) { + MInstruction* store = aliasedStores[i]; + if (def->mightAlias(store) != MDefinition::AliasType::NoAlias && + BlockMightReach(store->block(), *block)) { + if (lastStore->id() < store->id()) { + lastStore = store; + } + break; + } + } + } + + def->setDependency(lastStore); + IonSpewDependency(*def, lastStore, "depends", ""); + + // If the last store was before the current loop, we assume this load + // is loop invariant. If a later instruction writes to the same + // location, we will fix this at the end of the loop. + if (loop_ && lastStore->id() < loop_->firstInstruction()->id()) { + if (!loop_->addInvariantLoad(*def)) { + return false; + } + } + } + } + + if (block->isLoopBackedge()) { + MOZ_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge()); + JitSpew(JitSpew_Alias, "Processing loop backedge %u (header %u)", + block->id(), loop_->loopHeader()->id()); + LoopAliasInfo* outerLoop = loop_->outer(); + MInstruction* firstLoopIns = *loop_->loopHeader()->begin(); + + const MInstructionVector& invariant = loop_->invariantLoads(); + + for (unsigned i = 0; i < invariant.length(); i++) { + MInstruction* ins = invariant[i]; + AliasSet set = ins->getAliasSet(); + MOZ_ASSERT(set.isLoad()); + + bool hasAlias = false; + for (AliasSetIterator iter(set); iter; iter++) { + MInstructionVector& aliasedStores = stores[*iter]; + for (int i = aliasedStores.length() - 1;; i--) { + MInstruction* store = aliasedStores[i]; + if (store->id() < firstLoopIns->id()) { + break; + } + if (ins->mightAlias(store) != MDefinition::AliasType::NoAlias) { + hasAlias = true; + IonSpewDependency(ins, store, "aliases", "store in loop body"); + break; + } + } + if (hasAlias) { + break; + } + } + + if (hasAlias) { + // This instruction depends on stores inside the loop body. Mark it as + // having a dependency on the last instruction of the loop header. The + // last instruction is a control instruction and these are never + // hoisted. + MControlInstruction* controlIns = loop_->loopHeader()->lastIns(); + IonSpewDependency(ins, controlIns, "depends", + "due to stores in loop body"); + ins->setDependency(controlIns); + } else { + IonSpewAliasInfo("Load", ins, + "does not depend on any stores in this loop"); + + if (outerLoop && + ins->dependency()->id() < outerLoop->firstInstruction()->id()) { + IonSpewAliasInfo("Load", ins, "may be invariant in outer loop"); + if (!outerLoop->addInvariantLoad(ins)) { + return false; + } + } + } + } + loop_ = loop_->outer(); + } + } + + spewDependencyList(); + + MOZ_ASSERT(loop_ == nullptr); + return true; +} -- cgit v1.2.3