tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

AliasAnalysis.cpp (11355B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
      2 * vim: set ts=8 sts=2 et sw=2 tw=80:
      3 * This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this
      5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 #include "jit/AliasAnalysis.h"
      8 
      9 #include "mozilla/DebugOnly.h"
     10 
     11 #include "jit/JitSpewer.h"
     12 #include "jit/MIR-wasm.h"
     13 #include "jit/MIR.h"
     14 #include "jit/MIRGenerator.h"
     15 #include "jit/MIRGraph.h"
     16 
     17 #include "js/Printer.h"
     18 
     19 using namespace js;
     20 using namespace js::jit;
     21 
     22 namespace js {
     23 namespace jit {
     24 
     25 class LoopAliasInfo : public TempObject {
     26 private:
     27  LoopAliasInfo* outer_;
     28  MBasicBlock* loopHeader_;
     29  MInstructionVector invariantLoads_;
     30 
     31 public:
     32  LoopAliasInfo(TempAllocator& alloc, LoopAliasInfo* outer,
     33                MBasicBlock* loopHeader)
     34      : outer_(outer), loopHeader_(loopHeader), invariantLoads_(alloc) {}
     35 
     36  MBasicBlock* loopHeader() const { return loopHeader_; }
     37  LoopAliasInfo* outer() const { return outer_; }
     38  bool addInvariantLoad(MInstruction* ins) {
     39    return invariantLoads_.append(ins);
     40  }
     41  const MInstructionVector& invariantLoads() const { return invariantLoads_; }
     42  MInstruction* firstInstruction() const { return *loopHeader_->begin(); }
     43 };
     44 
     45 }  // namespace jit
     46 }  // namespace js
     47 
     48 void AliasAnalysis::spewDependencyList() {
     49 #ifdef JS_JITSPEW
     50  if (JitSpewEnabled(JitSpew_AliasSummaries)) {
     51    Fprinter& print = JitSpewPrinter();
     52    JitSpewHeader(JitSpew_AliasSummaries);
     53    print.printf("Dependency list for other passes:\n");
     54 
     55    for (ReversePostorderIterator block(graph_.rpoBegin());
     56         block != graph_.rpoEnd(); block++) {
     57      for (MInstructionIterator def(block->begin()),
     58           end(block->begin(block->lastIns()));
     59           def != end; ++def) {
     60        if (!def->dependency()) {
     61          continue;
     62        }
     63        if (!def->getAliasSet().isLoad()) {
     64          continue;
     65        }
     66 
     67        JitSpewHeader(JitSpew_AliasSummaries);
     68        print.printf(" ");
     69        MDefinition::PrintOpcodeName(print, def->op());
     70        print.printf("%u marked depending on ", def->id());
     71        MDefinition::PrintOpcodeName(print, def->dependency()->op());
     72        print.printf("%u\n", def->dependency()->id());
     73      }
     74    }
     75  }
     76 #endif
     77 }
     78 
     79 // Whether there might be a path from src to dest, excluding loop backedges.
     80 // This is approximate and really ought to depend on precomputed reachability
     81 // information.
     82 static inline bool BlockMightReach(MBasicBlock* src, MBasicBlock* dest) {
     83  while (src->id() <= dest->id()) {
     84    if (src == dest) {
     85      return true;
     86    }
     87    switch (src->numSuccessors()) {
     88      case 0:
     89        return false;
     90      case 1: {
     91        MBasicBlock* successor = src->getSuccessor(0);
     92        if (successor->id() <= src->id()) {
     93          return true;  // Don't iloop.
     94        }
     95        src = successor;
     96        break;
     97      }
     98      default:
     99        return true;
    100    }
    101  }
    102  return false;
    103 }
    104 
    105 static void IonSpewDependency(MInstruction* load, MInstruction* store,
    106                              const char* verb, const char* reason) {
    107 #ifdef JS_JITSPEW
    108  if (!JitSpewEnabled(JitSpew_Alias)) {
    109    return;
    110  }
    111 
    112  JitSpewHeader(JitSpew_Alias);
    113  Fprinter& out = JitSpewPrinter();
    114  out.printf("  Load ");
    115  load->printName(out);
    116  out.printf(" %s on store ", verb);
    117  store->printName(out);
    118  out.printf(" (%s)\n", reason);
    119 #endif
    120 }
    121 
    122 static void IonSpewAliasInfo(const char* pre, MInstruction* ins,
    123                             const char* post) {
    124 #ifdef JS_JITSPEW
    125  if (!JitSpewEnabled(JitSpew_Alias)) {
    126    return;
    127  }
    128 
    129  JitSpewHeader(JitSpew_Alias);
    130  Fprinter& out = JitSpewPrinter();
    131  out.printf("  %s ", pre);
    132  ins->printName(out);
    133  out.printf(" %s\n", post);
    134 #endif
    135 }
    136 
    137 // [SMDOC] IonMonkey Alias Analysis
    138 //
    139 // This pass annotates every load instruction with the last store instruction
    140 // on which it depends. The algorithm is optimistic in that it ignores explicit
    141 // dependencies and only considers loads and stores.
    142 //
    143 // Loads inside loops only have an implicit dependency on a store before the
    144 // loop header if no instruction inside the loop body aliases it. To calculate
    145 // this efficiently, we maintain a list of maybe-invariant loads and the
    146 // combined alias set for all stores inside the loop. When we see the loop's
    147 // backedge, this information is used to mark every load we wrongly assumed to
    148 // be loop invariant as having an implicit dependency on the last instruction of
    149 // the loop header, so that it's never moved before the loop header.
    150 //
    151 // The algorithm depends on the invariant that both control instructions and
    152 // effectful instructions (stores) are never hoisted.
    153 bool AliasAnalysis::analyze() {
    154  JitSpew(JitSpew_Alias, "Begin");
    155  Vector<MInstructionVector, AliasSet::NumCategories, JitAllocPolicy> stores(
    156      alloc());
    157 
    158  // Initialize to the first instruction.
    159  MInstruction* firstIns = *graph_.entryBlock()->begin();
    160  for (unsigned i = 0; i < AliasSet::NumCategories; i++) {
    161    MInstructionVector defs(alloc());
    162    if (!defs.append(firstIns)) {
    163      return false;
    164    }
    165    if (!stores.append(std::move(defs))) {
    166      return false;
    167    }
    168  }
    169 
    170  // Type analysis may have inserted new instructions. Since this pass depends
    171  // on the instruction number ordering, all instructions are renumbered.
    172  uint32_t newId = 0;
    173 
    174  for (ReversePostorderIterator block(graph_.rpoBegin());
    175       block != graph_.rpoEnd(); block++) {
    176    if (mir->shouldCancel("Alias Analysis (main loop)")) {
    177      return false;
    178    }
    179 
    180    if (block->isLoopHeader()) {
    181      JitSpew(JitSpew_Alias, "Processing loop header %u", block->id());
    182      loop_ = new (alloc().fallible()) LoopAliasInfo(alloc(), loop_, *block);
    183      if (!loop_) {
    184        return false;
    185      }
    186    }
    187 
    188    for (MPhiIterator def(block->phisBegin()), end(block->phisEnd());
    189         def != end; ++def) {
    190      def->setId(newId++);
    191    }
    192 
    193    {
    194      // "The block has one or more instructions"
    195      MOZ_ASSERT(block->hasAnyIns());
    196      // "The last instruction is a control instruction"
    197      MOZ_ASSERT(block->hasLastIns());
    198      // "The only control instructions that can have a non-empty alias set
    199      //  are MWasmCallCatchable and MWasmReturnCall".
    200      // Note, this isn't a requirement that is intrinsic to MIR.  In
    201      // principle, any control instruction can have a non-empty alias set,
    202      // and that should be correctly handled by this routine.  The assertion
    203      // merely reflects the current state of usage of MIR, in which
    204      // MWasmCallCatchable and MWasmReturnCall are the only control
    205      // instructions we generate that have non-empty alias sets.
    206      // See bug 1837686.
    207      mozilla::DebugOnly<MControlInstruction*> lastIns = block->lastIns();
    208      MOZ_ASSERT_IF(
    209          !lastIns->isWasmCallCatchable() && !lastIns->isWasmReturnCall(),
    210          lastIns->getAliasSet().isNone());
    211    }
    212 
    213    for (MInstructionIterator def(block->begin()), end(block->end());
    214         def != end; ++def) {
    215      def->setId(newId++);
    216 
    217      AliasSet set = def->getAliasSet();
    218      if (set.isNone()) {
    219        continue;
    220      }
    221 
    222      // For the purposes of alias analysis, all recoverable operations
    223      // are treated as effect free as the memory represented by these
    224      // operations cannot be aliased by others.
    225      if (def->canRecoverOnBailout()) {
    226        continue;
    227      }
    228 
    229      if (set.isStore()) {
    230        for (AliasSetIterator iter(set); iter; iter++) {
    231          if (!stores[*iter].append(*def)) {
    232            return false;
    233          }
    234        }
    235 
    236 #ifdef JS_JITSPEW
    237        if (JitSpewEnabled(JitSpew_Alias)) {
    238          JitSpewHeader(JitSpew_Alias);
    239          Fprinter& out = JitSpewPrinter();
    240          out.printf("Processing store ");
    241          def->printName(out);
    242          out.printf(" (flags %x)\n", set.flags());
    243        }
    244 #endif
    245      } else {
    246        // Find the most recent store on which this instruction depends.
    247        MInstruction* lastStore = firstIns;
    248 
    249        for (AliasSetIterator iter(set); iter; iter++) {
    250          MInstructionVector& aliasedStores = stores[*iter];
    251          for (int i = aliasedStores.length() - 1; i >= 0; i--) {
    252            MInstruction* store = aliasedStores[i];
    253            if (def->mightAlias(store) != MDefinition::AliasType::NoAlias &&
    254                BlockMightReach(store->block(), *block)) {
    255              if (lastStore->id() < store->id()) {
    256                lastStore = store;
    257              }
    258              break;
    259            }
    260          }
    261        }
    262 
    263        def->setDependency(lastStore);
    264        IonSpewDependency(*def, lastStore, "depends", "");
    265 
    266        // If the last store was before the current loop, we assume this load
    267        // is loop invariant. If a later instruction writes to the same
    268        // location, we will fix this at the end of the loop.
    269        if (loop_ && lastStore->id() < loop_->firstInstruction()->id()) {
    270          if (!loop_->addInvariantLoad(*def)) {
    271            return false;
    272          }
    273        }
    274      }
    275    }
    276 
    277    if (block->isLoopBackedge()) {
    278      MOZ_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge());
    279      JitSpew(JitSpew_Alias, "Processing loop backedge %u (header %u)",
    280              block->id(), loop_->loopHeader()->id());
    281      LoopAliasInfo* outerLoop = loop_->outer();
    282      MInstruction* firstLoopIns = *loop_->loopHeader()->begin();
    283 
    284      const MInstructionVector& invariant = loop_->invariantLoads();
    285 
    286      for (unsigned i = 0; i < invariant.length(); i++) {
    287        MInstruction* ins = invariant[i];
    288        AliasSet set = ins->getAliasSet();
    289        MOZ_ASSERT(set.isLoad());
    290 
    291        bool hasAlias = false;
    292        for (AliasSetIterator iter(set); iter; iter++) {
    293          MInstructionVector& aliasedStores = stores[*iter];
    294          for (int i = aliasedStores.length() - 1;; i--) {
    295            MInstruction* store = aliasedStores[i];
    296            if (store->id() < firstLoopIns->id()) {
    297              break;
    298            }
    299            if (ins->mightAlias(store) != MDefinition::AliasType::NoAlias) {
    300              hasAlias = true;
    301              IonSpewDependency(ins, store, "aliases", "store in loop body");
    302              break;
    303            }
    304          }
    305          if (hasAlias) {
    306            break;
    307          }
    308        }
    309 
    310        if (hasAlias) {
    311          // This instruction depends on stores inside the loop body. Mark it as
    312          // having a dependency on the last instruction of the loop header. The
    313          // last instruction is a control instruction and these are never
    314          // hoisted.
    315          MControlInstruction* controlIns = loop_->loopHeader()->lastIns();
    316          IonSpewDependency(ins, controlIns, "depends",
    317                            "due to stores in loop body");
    318          ins->setDependency(controlIns);
    319        } else {
    320          IonSpewAliasInfo("Load", ins,
    321                           "does not depend on any stores in this loop");
    322 
    323          if (outerLoop &&
    324              ins->dependency()->id() < outerLoop->firstInstruction()->id()) {
    325            IonSpewAliasInfo("Load", ins, "may be invariant in outer loop");
    326            if (!outerLoop->addInvariantLoad(ins)) {
    327              return false;
    328            }
    329          }
    330        }
    331      }
    332      loop_ = loop_->outer();
    333    }
    334  }
    335 
    336  spewDependencyList();
    337 
    338  MOZ_ASSERT(loop_ == nullptr);
    339  return true;
    340 }