The Tor Browser / file revision

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

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

  * 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 <stdio.h>

 #include "jit/Ion.h"

 #include "jit/IonBuilder.h"

 #include "jit/IonSpewer.h"

 #include "jit/MIR.h"

 #include "jit/MIRGraph.h"

 using namespace js;

 using namespace js::jit;

 using mozilla::Array;

 namespace js {

 namespace jit {

 class LoopAliasInfo : public TempObject

 {

   private:

     LoopAliasInfo *outer_;

     MBasicBlock *loopHeader_;

     MDefinitionVector 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(MDefinition *ins) {

         return invariantLoads_.append(ins);

     }

     const MDefinitionVector& invariantLoads() const {

         return invariantLoads_;

     }

     MDefinition *firstInstruction() const {

         return *loopHeader_->begin();

     }

 };

 } // namespace jit

 } // namespace js

 namespace {

 // Iterates over the flags in an AliasSet.

 class AliasSetIterator

 {

   private:

     uint32_t flags;

     unsigned pos;

   public:

     AliasSetIterator(AliasSet set)

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

     {

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

             flags >>= 1;

             pos++;

         }

     }

     AliasSetIterator& operator ++(int) {

         do {

             flags >>= 1;

             pos++;

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

         return *this;

     }

     operator bool() const {

         return !!flags;

     }

     unsigned operator *() const {

         JS_ASSERT(pos < AliasSet::NumCategories);

         return pos;

     }

 };

 } /* anonymous namespace */

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

   : mir(mir),

     graph_(graph),

     loop_(nullptr)

 {

 }

 // 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(MDefinition *load, MDefinition *store, const char *verb, const char *reason)

 {

     if (!IonSpewEnabled(IonSpew_Alias))

         return;

     fprintf(IonSpewFile, "Load ");

     load->printName(IonSpewFile);

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

     store->printName(IonSpewFile);

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

 }

 static void

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

 {

     if (!IonSpewEnabled(IonSpew_Alias))

         return;

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

     ins->printName(IonSpewFile);

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

 }

 // 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 invaraint 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()

 {

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

     // Initialize to the first instruction.

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

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

         MDefinitionVector defs(alloc());

         if (!defs.append(firstIns))

             return false;

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

             return false;

     }

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

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

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

     uint32_t newId = 1;

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

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

             return false;

         if (block->isLoopHeader()) {

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

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

         }

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

             def->setId(newId++);

             AliasSet set = def->getAliasSet();

             if (set.isNone())

                 continue;

             if (set.isStore()) {

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

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

                         return false;

                 }

                 if (IonSpewEnabled(IonSpew_Alias)) {

                     fprintf(IonSpewFile, "Processing store ");

                     def->printName(IonSpewFile);

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

                 }

             } else {

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

                 MDefinition *lastStore = firstIns;

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

                     MDefinitionVector &aliasedStores = stores[*iter];

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

                         MDefinition *store = aliasedStores[i];

                         if (def->mightAlias(store) && 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;

                 }

             }

         }

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

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

         if (block->isLoopBackedge()) {

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

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

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

             LoopAliasInfo *outerLoop = loop_->outer();

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

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

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

                 MDefinition *ins = invariant[i];

                 AliasSet set = ins->getAliasSet();

                 JS_ASSERT(set.isLoad());

                 bool hasAlias = false;

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

                     MDefinitionVector &aliasedStores = stores[*iter];

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

                         MDefinition *store = aliasedStores[i];

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

                             break;

                         if (ins->mightAlias(store)) {

                             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();

         }

     }

     JS_ASSERT(loop_ == nullptr);

     return true;

 }