michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jit/AliasAnalysis.h"
michael@0: 
michael@0: #include <stdio.h>
michael@0: 
michael@0: #include "jit/Ion.h"
michael@0: #include "jit/IonBuilder.h"
michael@0: #include "jit/IonSpewer.h"
michael@0: #include "jit/MIR.h"
michael@0: #include "jit/MIRGraph.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace js::jit;
michael@0: 
michael@0: using mozilla::Array;
michael@0: 
michael@0: namespace js {
michael@0: namespace jit {
michael@0: 
michael@0: class LoopAliasInfo : public TempObject
michael@0: {
michael@0:   private:
michael@0:     LoopAliasInfo *outer_;
michael@0:     MBasicBlock *loopHeader_;
michael@0:     MDefinitionVector invariantLoads_;
michael@0: 
michael@0:   public:
michael@0:     LoopAliasInfo(TempAllocator &alloc, LoopAliasInfo *outer, MBasicBlock *loopHeader)
michael@0:       : outer_(outer), loopHeader_(loopHeader), invariantLoads_(alloc)
michael@0:     { }
michael@0: 
michael@0:     MBasicBlock *loopHeader() const {
michael@0:         return loopHeader_;
michael@0:     }
michael@0:     LoopAliasInfo *outer() const {
michael@0:         return outer_;
michael@0:     }
michael@0:     bool addInvariantLoad(MDefinition *ins) {
michael@0:         return invariantLoads_.append(ins);
michael@0:     }
michael@0:     const MDefinitionVector& invariantLoads() const {
michael@0:         return invariantLoads_;
michael@0:     }
michael@0:     MDefinition *firstInstruction() const {
michael@0:         return *loopHeader_->begin();
michael@0:     }
michael@0: };
michael@0: 
michael@0: } // namespace jit
michael@0: } // namespace js
michael@0: 
michael@0: namespace {
michael@0: 
michael@0: // Iterates over the flags in an AliasSet.
michael@0: class AliasSetIterator
michael@0: {
michael@0:   private:
michael@0:     uint32_t flags;
michael@0:     unsigned pos;
michael@0: 
michael@0:   public:
michael@0:     AliasSetIterator(AliasSet set)
michael@0:       : flags(set.flags()), pos(0)
michael@0:     {
michael@0:         while (flags && (flags & 1) == 0) {
michael@0:             flags >>= 1;
michael@0:             pos++;
michael@0:         }
michael@0:     }
michael@0:     AliasSetIterator& operator ++(int) {
michael@0:         do {
michael@0:             flags >>= 1;
michael@0:             pos++;
michael@0:         } while (flags && (flags & 1) == 0);
michael@0:         return *this;
michael@0:     }
michael@0:     operator bool() const {
michael@0:         return !!flags;
michael@0:     }
michael@0:     unsigned operator *() const {
michael@0:         JS_ASSERT(pos < AliasSet::NumCategories);
michael@0:         return pos;
michael@0:     }
michael@0: };
michael@0: 
michael@0: } /* anonymous namespace */
michael@0: 
michael@0: AliasAnalysis::AliasAnalysis(MIRGenerator *mir, MIRGraph &graph)
michael@0:   : mir(mir),
michael@0:     graph_(graph),
michael@0:     loop_(nullptr)
michael@0: {
michael@0: }
michael@0: 
michael@0: // Whether there might be a path from src to dest, excluding loop backedges. This is
michael@0: // approximate and really ought to depend on precomputed reachability information.
michael@0: static inline bool
michael@0: BlockMightReach(MBasicBlock *src, MBasicBlock *dest)
michael@0: {
michael@0:     while (src->id() <= dest->id()) {
michael@0:         if (src == dest)
michael@0:             return true;
michael@0:         switch (src->numSuccessors()) {
michael@0:           case 0:
michael@0:             return false;
michael@0:           case 1: {
michael@0:             MBasicBlock *successor = src->getSuccessor(0);
michael@0:             if (successor->id() <= src->id())
michael@0:                 return true; // Don't iloop.
michael@0:             src = successor;
michael@0:             break;
michael@0:           }
michael@0:           default:
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: static void
michael@0: IonSpewDependency(MDefinition *load, MDefinition *store, const char *verb, const char *reason)
michael@0: {
michael@0:     if (!IonSpewEnabled(IonSpew_Alias))
michael@0:         return;
michael@0: 
michael@0:     fprintf(IonSpewFile, "Load ");
michael@0:     load->printName(IonSpewFile);
michael@0:     fprintf(IonSpewFile, " %s on store ", verb);
michael@0:     store->printName(IonSpewFile);
michael@0:     fprintf(IonSpewFile, " (%s)\n", reason);
michael@0: }
michael@0: 
michael@0: static void
michael@0: IonSpewAliasInfo(const char *pre, MDefinition *ins, const char *post)
michael@0: {
michael@0:     if (!IonSpewEnabled(IonSpew_Alias))
michael@0:         return;
michael@0: 
michael@0:     fprintf(IonSpewFile, "%s ", pre);
michael@0:     ins->printName(IonSpewFile);
michael@0:     fprintf(IonSpewFile, " %s\n", post);
michael@0: }
michael@0: 
michael@0: // This pass annotates every load instruction with the last store instruction
michael@0: // on which it depends. The algorithm is optimistic in that it ignores explicit
michael@0: // dependencies and only considers loads and stores.
michael@0: //
michael@0: // Loads inside loops only have an implicit dependency on a store before the
michael@0: // loop header if no instruction inside the loop body aliases it. To calculate
michael@0: // this efficiently, we maintain a list of maybe-invariant loads and the combined
michael@0: // alias set for all stores inside the loop. When we see the loop's backedge, this
michael@0: // information is used to mark every load we wrongly assumed to be loop invaraint as
michael@0: // having an implicit dependency on the last instruction of the loop header, so that
michael@0: // it's never moved before the loop header.
michael@0: //
michael@0: // The algorithm depends on the invariant that both control instructions and effectful
michael@0: // instructions (stores) are never hoisted.
michael@0: bool
michael@0: AliasAnalysis::analyze()
michael@0: {
michael@0:     Vector<MDefinitionVector, AliasSet::NumCategories, IonAllocPolicy> stores(alloc());
michael@0: 
michael@0:     // Initialize to the first instruction.
michael@0:     MDefinition *firstIns = *graph_.begin()->begin();
michael@0:     for (unsigned i = 0; i < AliasSet::NumCategories; i++) {
michael@0:         MDefinitionVector defs(alloc());
michael@0:         if (!defs.append(firstIns))
michael@0:             return false;
michael@0:         if (!stores.append(Move(defs)))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     // Type analysis may have inserted new instructions. Since this pass depends
michael@0:     // on the instruction number ordering, all instructions are renumbered.
michael@0:     // We start with 1 because some passes use 0 to denote failure.
michael@0:     uint32_t newId = 1;
michael@0: 
michael@0:     for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
michael@0:         if (mir->shouldCancel("Alias Analysis (main loop)"))
michael@0:             return false;
michael@0: 
michael@0:         if (block->isLoopHeader()) {
michael@0:             IonSpew(IonSpew_Alias, "Processing loop header %d", block->id());
michael@0:             loop_ = new(alloc()) LoopAliasInfo(alloc(), loop_, *block);
michael@0:         }
michael@0: 
michael@0:         for (MDefinitionIterator def(*block); def; def++) {
michael@0:             def->setId(newId++);
michael@0: 
michael@0:             AliasSet set = def->getAliasSet();
michael@0:             if (set.isNone())
michael@0:                 continue;
michael@0: 
michael@0:             if (set.isStore()) {
michael@0:                 for (AliasSetIterator iter(set); iter; iter++) {
michael@0:                     if (!stores[*iter].append(*def))
michael@0:                         return false;
michael@0:                 }
michael@0: 
michael@0:                 if (IonSpewEnabled(IonSpew_Alias)) {
michael@0:                     fprintf(IonSpewFile, "Processing store ");
michael@0:                     def->printName(IonSpewFile);
michael@0:                     fprintf(IonSpewFile, " (flags %x)\n", set.flags());
michael@0:                 }
michael@0:             } else {
michael@0:                 // Find the most recent store on which this instruction depends.
michael@0:                 MDefinition *lastStore = firstIns;
michael@0: 
michael@0:                 for (AliasSetIterator iter(set); iter; iter++) {
michael@0:                     MDefinitionVector &aliasedStores = stores[*iter];
michael@0:                     for (int i = aliasedStores.length() - 1; i >= 0; i--) {
michael@0:                         MDefinition *store = aliasedStores[i];
michael@0:                         if (def->mightAlias(store) && BlockMightReach(store->block(), *block)) {
michael@0:                             if (lastStore->id() < store->id())
michael@0:                                 lastStore = store;
michael@0:                             break;
michael@0:                         }
michael@0:                     }
michael@0:                 }
michael@0: 
michael@0:                 def->setDependency(lastStore);
michael@0:                 IonSpewDependency(*def, lastStore, "depends", "");
michael@0: 
michael@0:                 // If the last store was before the current loop, we assume this load
michael@0:                 // is loop invariant. If a later instruction writes to the same location,
michael@0:                 // we will fix this at the end of the loop.
michael@0:                 if (loop_ && lastStore->id() < loop_->firstInstruction()->id()) {
michael@0:                     if (!loop_->addInvariantLoad(*def))
michael@0:                         return false;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // Renumber the last instruction, as the analysis depends on this and the order.
michael@0:         block->lastIns()->setId(newId++);
michael@0: 
michael@0:         if (block->isLoopBackedge()) {
michael@0:             JS_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge());
michael@0:             IonSpew(IonSpew_Alias, "Processing loop backedge %d (header %d)", block->id(),
michael@0:                     loop_->loopHeader()->id());
michael@0:             LoopAliasInfo *outerLoop = loop_->outer();
michael@0:             MInstruction *firstLoopIns = *loop_->loopHeader()->begin();
michael@0: 
michael@0:             const MDefinitionVector &invariant = loop_->invariantLoads();
michael@0: 
michael@0:             for (unsigned i = 0; i < invariant.length(); i++) {
michael@0:                 MDefinition *ins = invariant[i];
michael@0:                 AliasSet set = ins->getAliasSet();
michael@0:                 JS_ASSERT(set.isLoad());
michael@0: 
michael@0:                 bool hasAlias = false;
michael@0:                 for (AliasSetIterator iter(set); iter; iter++) {
michael@0:                     MDefinitionVector &aliasedStores = stores[*iter];
michael@0:                     for (int i = aliasedStores.length() - 1;; i--) {
michael@0:                         MDefinition *store = aliasedStores[i];
michael@0:                         if (store->id() < firstLoopIns->id())
michael@0:                             break;
michael@0:                         if (ins->mightAlias(store)) {
michael@0:                             hasAlias = true;
michael@0:                             IonSpewDependency(ins, store, "aliases", "store in loop body");
michael@0:                             break;
michael@0:                         }
michael@0:                     }
michael@0:                     if (hasAlias)
michael@0:                         break;
michael@0:                 }
michael@0: 
michael@0:                 if (hasAlias) {
michael@0:                     // This instruction depends on stores inside the loop body. Mark it as having a
michael@0:                     // dependency on the last instruction of the loop header. The last instruction is a
michael@0:                     // control instruction and these are never hoisted.
michael@0:                     MControlInstruction *controlIns = loop_->loopHeader()->lastIns();
michael@0:                     IonSpewDependency(ins, controlIns, "depends", "due to stores in loop body");
michael@0:                     ins->setDependency(controlIns);
michael@0:                 } else {
michael@0:                     IonSpewAliasInfo("Load", ins, "does not depend on any stores in this loop");
michael@0: 
michael@0:                     if (outerLoop && ins->dependency()->id() < outerLoop->firstInstruction()->id()) {
michael@0:                         IonSpewAliasInfo("Load", ins, "may be invariant in outer loop");
michael@0:                         if (!outerLoop->addInvariantLoad(ins))
michael@0:                             return false;
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:             loop_ = loop_->outer();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     JS_ASSERT(loop_ == nullptr);
michael@0:     return true;
michael@0: }