The Tor Browser: js/src/jit/AliasAnalysis.cpp@6474c204b198

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

     2  * vim: set ts=8 sts=4 et sw=4 tw=99:

     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/. */

     7 #include "jit/AliasAnalysis.h"

     9 #include <stdio.h>

    11 #include "jit/Ion.h"

    12 #include "jit/IonBuilder.h"

    13 #include "jit/IonSpewer.h"

    14 #include "jit/MIR.h"

    15 #include "jit/MIRGraph.h"

    17 using namespace js;

    18 using namespace js::jit;

    20 using mozilla::Array;

    22 namespace js {

    23 namespace jit {

    25 class LoopAliasInfo : public TempObject

    26 {

    27   private:

    28     LoopAliasInfo *outer_;

    29     MBasicBlock *loopHeader_;

    30     MDefinitionVector invariantLoads_;

    32   public:

    33     LoopAliasInfo(TempAllocator &alloc, LoopAliasInfo *outer, MBasicBlock *loopHeader)

    34       : outer_(outer), loopHeader_(loopHeader), invariantLoads_(alloc)

    35     { }

    37     MBasicBlock *loopHeader() const {

    38         return loopHeader_;

    39     }

    40     LoopAliasInfo *outer() const {

    41         return outer_;

    42     }

    43     bool addInvariantLoad(MDefinition *ins) {

    44         return invariantLoads_.append(ins);

    45     }

    46     const MDefinitionVector& invariantLoads() const {

    47         return invariantLoads_;

    48     }

    49     MDefinition *firstInstruction() const {

    50         return *loopHeader_->begin();

    51     }

    52 };

    54 } // namespace jit

    55 } // namespace js

    57 namespace {

    59 // Iterates over the flags in an AliasSet.

    60 class AliasSetIterator

    61 {

    62   private:

    63     uint32_t flags;

    64     unsigned pos;

    66   public:

    67     AliasSetIterator(AliasSet set)

    68       : flags(set.flags()), pos(0)

    69     {

    70         while (flags && (flags & 1) == 0) {

    71             flags >>= 1;

    72             pos++;

    73         }

    74     }

    75     AliasSetIterator& operator ++(int) {

    76         do {

    77             flags >>= 1;

    78             pos++;

    79         } while (flags && (flags & 1) == 0);

    80         return *this;

    81     }

    82     operator bool() const {

    83         return !!flags;

    84     }

    85     unsigned operator *() const {

    86         JS_ASSERT(pos < AliasSet::NumCategories);

    87         return pos;

    88     }

    89 };

    91 } /* anonymous namespace */

    93 AliasAnalysis::AliasAnalysis(MIRGenerator *mir, MIRGraph &graph)

    94   : mir(mir),

    95     graph_(graph),

    96     loop_(nullptr)

    97 {

    98 }

   100 // Whether there might be a path from src to dest, excluding loop backedges. This is

   101 // approximate and really ought to depend on precomputed reachability information.

   102 static inline bool

   103 BlockMightReach(MBasicBlock *src, MBasicBlock *dest)

   104 {

   105     while (src->id() <= dest->id()) {

   106         if (src == dest)

   107             return true;

   108         switch (src->numSuccessors()) {

   109           case 0:

   110             return false;

   111           case 1: {

   112             MBasicBlock *successor = src->getSuccessor(0);

   113             if (successor->id() <= src->id())

   114                 return true; // Don't iloop.

   115             src = successor;

   116             break;

   117           }

   118           default:

   119             return true;

   120         }

   121     }

   122     return false;

   123 }

   125 static void

   126 IonSpewDependency(MDefinition *load, MDefinition *store, const char *verb, const char *reason)

   127 {

   128     if (!IonSpewEnabled(IonSpew_Alias))

   129         return;

   131     fprintf(IonSpewFile, "Load ");

   132     load->printName(IonSpewFile);

   133     fprintf(IonSpewFile, " %s on store ", verb);

   134     store->printName(IonSpewFile);

   135     fprintf(IonSpewFile, " (%s)\n", reason);

   136 }

   138 static void

   139 IonSpewAliasInfo(const char *pre, MDefinition *ins, const char *post)

   140 {

   141     if (!IonSpewEnabled(IonSpew_Alias))

   142         return;

   144     fprintf(IonSpewFile, "%s ", pre);

   145     ins->printName(IonSpewFile);

   146     fprintf(IonSpewFile, " %s\n", post);

   147 }

   149 // This pass annotates every load instruction with the last store instruction

   150 // on which it depends. The algorithm is optimistic in that it ignores explicit

   151 // dependencies and only considers loads and stores.

   152 //

   153 // Loads inside loops only have an implicit dependency on a store before the

   154 // loop header if no instruction inside the loop body aliases it. To calculate

   155 // this efficiently, we maintain a list of maybe-invariant loads and the combined

   156 // alias set for all stores inside the loop. When we see the loop's backedge, this

   157 // information is used to mark every load we wrongly assumed to be loop invaraint as

   158 // having an implicit dependency on the last instruction of the loop header, so that

   159 // it's never moved before the loop header.

   160 //

   161 // The algorithm depends on the invariant that both control instructions and effectful

   162 // instructions (stores) are never hoisted.

   163 bool

   164 AliasAnalysis::analyze()

   165 {

   166     Vector<MDefinitionVector, AliasSet::NumCategories, IonAllocPolicy> stores(alloc());

   168     // Initialize to the first instruction.

   169     MDefinition *firstIns = *graph_.begin()->begin();

   170     for (unsigned i = 0; i < AliasSet::NumCategories; i++) {

   171         MDefinitionVector defs(alloc());

   172         if (!defs.append(firstIns))

   173             return false;

   174         if (!stores.append(Move(defs)))

   175             return false;

   176     }

   178     // Type analysis may have inserted new instructions. Since this pass depends

   179     // on the instruction number ordering, all instructions are renumbered.

   180     // We start with 1 because some passes use 0 to denote failure.

   181     uint32_t newId = 1;

   183     for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {

   184         if (mir->shouldCancel("Alias Analysis (main loop)"))

   185             return false;

   187         if (block->isLoopHeader()) {

   188             IonSpew(IonSpew_Alias, "Processing loop header %d", block->id());

   189             loop_ = new(alloc()) LoopAliasInfo(alloc(), loop_, *block);

   190         }

   192         for (MDefinitionIterator def(*block); def; def++) {

   193             def->setId(newId++);

   195             AliasSet set = def->getAliasSet();

   196             if (set.isNone())

   197                 continue;

   199             if (set.isStore()) {

   200                 for (AliasSetIterator iter(set); iter; iter++) {

   201                     if (!stores[*iter].append(*def))

   202                         return false;

   203                 }

   205                 if (IonSpewEnabled(IonSpew_Alias)) {

   206                     fprintf(IonSpewFile, "Processing store ");

   207                     def->printName(IonSpewFile);

   208                     fprintf(IonSpewFile, " (flags %x)\n", set.flags());

   209                 }

   210             } else {

   211                 // Find the most recent store on which this instruction depends.

   212                 MDefinition *lastStore = firstIns;

   214                 for (AliasSetIterator iter(set); iter; iter++) {

   215                     MDefinitionVector &aliasedStores = stores[*iter];

   216                     for (int i = aliasedStores.length() - 1; i >= 0; i--) {

   217                         MDefinition *store = aliasedStores[i];

   218                         if (def->mightAlias(store) && BlockMightReach(store->block(), *block)) {

   219                             if (lastStore->id() < store->id())

   220                                 lastStore = store;

   221                             break;

   222                         }

   223                     }

   224                 }

   226                 def->setDependency(lastStore);

   227                 IonSpewDependency(*def, lastStore, "depends", "");

   229                 // If the last store was before the current loop, we assume this load

   230                 // is loop invariant. If a later instruction writes to the same location,

   231                 // we will fix this at the end of the loop.

   232                 if (loop_ && lastStore->id() < loop_->firstInstruction()->id()) {

   233                     if (!loop_->addInvariantLoad(*def))

   234                         return false;

   235                 }

   236             }

   237         }

   239         // Renumber the last instruction, as the analysis depends on this and the order.

   240         block->lastIns()->setId(newId++);

   242         if (block->isLoopBackedge()) {

   243             JS_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge());

   244             IonSpew(IonSpew_Alias, "Processing loop backedge %d (header %d)", block->id(),

   245                     loop_->loopHeader()->id());

   246             LoopAliasInfo *outerLoop = loop_->outer();

   247             MInstruction *firstLoopIns = *loop_->loopHeader()->begin();

   249             const MDefinitionVector &invariant = loop_->invariantLoads();

   251             for (unsigned i = 0; i < invariant.length(); i++) {

   252                 MDefinition *ins = invariant[i];

   253                 AliasSet set = ins->getAliasSet();

   254                 JS_ASSERT(set.isLoad());

   256                 bool hasAlias = false;

   257                 for (AliasSetIterator iter(set); iter; iter++) {

   258                     MDefinitionVector &aliasedStores = stores[*iter];

   259                     for (int i = aliasedStores.length() - 1;; i--) {

   260                         MDefinition *store = aliasedStores[i];

   261                         if (store->id() < firstLoopIns->id())

   262                             break;

   263                         if (ins->mightAlias(store)) {

   264                             hasAlias = true;

   265                             IonSpewDependency(ins, store, "aliases", "store in loop body");

   266                             break;

   267                         }

   268                     }

   269                     if (hasAlias)

   270                         break;

   271                 }

   273                 if (hasAlias) {

   274                     // This instruction depends on stores inside the loop body. Mark it as having a

   275                     // dependency on the last instruction of the loop header. The last instruction is a

   276                     // control instruction and these are never hoisted.

   277                     MControlInstruction *controlIns = loop_->loopHeader()->lastIns();

   278                     IonSpewDependency(ins, controlIns, "depends", "due to stores in loop body");

   279                     ins->setDependency(controlIns);

   280                 } else {

   281                     IonSpewAliasInfo("Load", ins, "does not depend on any stores in this loop");

   283                     if (outerLoop && ins->dependency()->id() < outerLoop->firstInstruction()->id()) {

   284                         IonSpewAliasInfo("Load", ins, "may be invariant in outer loop");

   285                         if (!outerLoop->addInvariantLoad(ins))

   286                             return false;

   287                     }

   288                 }

   289             }

   290             loop_ = loop_->outer();

   291         }

   292     }

   294     JS_ASSERT(loop_ == nullptr);

   295     return true;

   296 }

The Tor Browser / file revision

js/src/jit/AliasAnalysis.cpp@6474c204b198

js/src/jit/AliasAnalysis.cpp