js/src/jit/AliasAnalysis.cpp

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