/* -*- 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/JitSpewer.h"
#include "jit/MIR.h"
#include "jit/MIRGraph.h"

#include "vm/Printer.h"

using namespace js;
using namespace js::jit;

using mozilla::Array;

namespace js {
namespace jit {

class LoopAliasInfo : public TempObject
{
  private:
    LoopAliasInfo* outer_;
    MBasicBlock* loopHeader_;
    MInstructionVector 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(MInstruction* ins) {
        return invariantLoads_.append(ins);
    }
    const MInstructionVector& invariantLoads() const {
        return invariantLoads_;
    }
    MInstruction* 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:
    explicit 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;
    }
    explicit operator bool() const {
        return !!flags;
    }
    unsigned operator*() const {
        MOZ_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(MInstruction* load, MInstruction* store, const char* verb, const char* reason)
{
    if (!JitSpewEnabled(JitSpew_Alias))
        return;

    Fprinter& out = JitSpewPrinter();
    out.printf("Load ");
    load->printName(out);
    out.printf(" %s on store ", verb);
    store->printName(out);
    out.printf(" (%s)\n", reason);
}

static void
IonSpewAliasInfo(const char* pre, MInstruction* ins, const char* post)
{
    if (!JitSpewEnabled(JitSpew_Alias))
        return;

    Fprinter& out = JitSpewPrinter();
    out.printf("%s ", pre);
    ins->printName(out);
    out.printf(" %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 invariant 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<MInstructionVector, AliasSet::NumCategories, JitAllocPolicy> stores(alloc());

    // Initialize to the first instruction.
    MInstruction* firstIns = *graph_.entryBlock()->begin();
    for (unsigned i = 0; i < AliasSet::NumCategories; i++) {
        MInstructionVector 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.
    uint32_t newId = 0;

    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
        if (mir->shouldCancel("Alias Analysis (main loop)"))
            return false;

        if (block->isLoopHeader()) {
            JitSpew(JitSpew_Alias, "Processing loop header %d", block->id());
            loop_ = new(alloc()) LoopAliasInfo(alloc(), loop_, *block);
        }

        for (MPhiIterator def(block->phisBegin()), end(block->phisEnd()); def != end; ++def)
            def->setId(newId++);

        for (MInstructionIterator def(block->begin()), end(block->begin(block->lastIns()));
             def != end;
             ++def)
        {
            def->setId(newId++);

            AliasSet set = def->getAliasSet();
            if (set.isNone())
                continue;

            // For the purposes of alias analysis, all recoverable operations
            // are treated as effect free as the memory represented by these
            // operations cannot be aliased by others.
            if (def->canRecoverOnBailout())
                continue;

            if (set.isStore()) {
                for (AliasSetIterator iter(set); iter; iter++) {
                    if (!stores[*iter].append(*def))
                        return false;
                }

                if (JitSpewEnabled(JitSpew_Alias)) {
                    Fprinter& out = JitSpewPrinter();
                    out.printf("Processing store ");
                    def->printName(out);
                    out.printf(" (flags %x)\n", set.flags());
                }
            } else {
                // Find the most recent store on which this instruction depends.
                MInstruction* lastStore = firstIns;

                for (AliasSetIterator iter(set); iter; iter++) {
                    MInstructionVector& aliasedStores = stores[*iter];
                    for (int i = aliasedStores.length() - 1; i >= 0; i--) {
                        MInstruction* 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()) {
            MOZ_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge());
            JitSpew(JitSpew_Alias, "Processing loop backedge %d (header %d)", block->id(),
                    loop_->loopHeader()->id());
            LoopAliasInfo* outerLoop = loop_->outer();
            MInstruction* firstLoopIns = *loop_->loopHeader()->begin();

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

            for (unsigned i = 0; i < invariant.length(); i++) {
                MInstruction* ins = invariant[i];
                AliasSet set = ins->getAliasSet();
                MOZ_ASSERT(set.isLoad());

                bool hasAlias = false;
                for (AliasSetIterator iter(set); iter; iter++) {
                    MInstructionVector& aliasedStores = stores[*iter];
                    for (int i = aliasedStores.length() - 1;; i--) {
                        MInstruction* 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();
        }
    }

    MOZ_ASSERT(loop_ == nullptr);
    return true;
}