summaryrefslogtreecommitdiffstats
path: root/js/src/jit/AliasAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/jit/AliasAnalysis.cpp')
-rw-r--r--js/src/jit/AliasAnalysis.cpp317
1 files changed, 317 insertions, 0 deletions
diff --git a/js/src/jit/AliasAnalysis.cpp b/js/src/jit/AliasAnalysis.cpp
new file mode 100644
index 0000000000..8334d55dfe
--- /dev/null
+++ b/js/src/jit/AliasAnalysis.cpp
@@ -0,0 +1,317 @@
+/* -*- 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 "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<MInstructionVector, AliasSet::NumCategories, JitAllocPolicy> 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++);
+ }
+
+ 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;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-09 19:53:10 +0000