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

#ifndef jit_RegisterAllocator_h
#define jit_RegisterAllocator_h

#include "mozilla/Attributes.h"
#include "mozilla/MathAlgorithms.h"

#include "jit/LIR.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"

// Generic structures and functions for use by register allocators.

namespace js {
namespace jit {

class LIRGenerator;

// Structure for running a liveness analysis on a finished register allocation.
// This analysis can be used for two purposes:
//
// - Check the integrity of the allocation, i.e. that the reads and writes of
//   physical values preserve the semantics of the original virtual registers.
//
// - Populate safepoints with live registers, GC thing and value data, to
//   streamline the process of prototyping new allocators.
struct AllocationIntegrityState
{
    explicit AllocationIntegrityState(LIRGraph& graph)
      : graph(graph)
    {}

    // Record all virtual registers in the graph. This must be called before
    // register allocation, to pick up the original LUses.
    MOZ_MUST_USE bool record();

    // Perform the liveness analysis on the graph, and assert on an invalid
    // allocation. This must be called after register allocation, to pick up
    // all assigned physical values. If populateSafepoints is specified,
    // safepoints will be filled in with liveness information.
    MOZ_MUST_USE bool check(bool populateSafepoints);

  private:

    LIRGraph& graph;

    // For all instructions and phis in the graph, keep track of the virtual
    // registers for all inputs and outputs of the nodes. These are overwritten
    // in place during register allocation. This information is kept on the
    // side rather than in the instructions and phis themselves to avoid
    // debug-builds-only bloat in the size of the involved structures.

    struct InstructionInfo {
        Vector<LAllocation, 2, SystemAllocPolicy> inputs;
        Vector<LDefinition, 0, SystemAllocPolicy> temps;
        Vector<LDefinition, 1, SystemAllocPolicy> outputs;

        InstructionInfo()
        { }

        InstructionInfo(const InstructionInfo& o)
        {
            AutoEnterOOMUnsafeRegion oomUnsafe;
            if (!inputs.appendAll(o.inputs) ||
                !temps.appendAll(o.temps) ||
                !outputs.appendAll(o.outputs))
            {
                oomUnsafe.crash("InstructionInfo::InstructionInfo");
            }
        }
    };
    Vector<InstructionInfo, 0, SystemAllocPolicy> instructions;

    struct BlockInfo {
        Vector<InstructionInfo, 5, SystemAllocPolicy> phis;
        BlockInfo() {}
        BlockInfo(const BlockInfo& o) {
            AutoEnterOOMUnsafeRegion oomUnsafe;
            if (!phis.appendAll(o.phis))
                oomUnsafe.crash("BlockInfo::BlockInfo");
        }
    };
    Vector<BlockInfo, 0, SystemAllocPolicy> blocks;

    Vector<LDefinition*, 20, SystemAllocPolicy> virtualRegisters;

    // Describes a correspondence that should hold at the end of a block.
    // The value which was written to vreg in the original LIR should be
    // physically stored in alloc after the register allocation.
    struct IntegrityItem
    {
        LBlock* block;
        uint32_t vreg;
        LAllocation alloc;

        // Order of insertion into seen, for sorting.
        uint32_t index;

        typedef IntegrityItem Lookup;
        static HashNumber hash(const IntegrityItem& item) {
            HashNumber hash = item.alloc.hash();
            hash = mozilla::RotateLeft(hash, 4) ^ item.vreg;
            hash = mozilla::RotateLeft(hash, 4) ^ HashNumber(item.block->mir()->id());
            return hash;
        }
        static bool match(const IntegrityItem& one, const IntegrityItem& two) {
            return one.block == two.block
                && one.vreg == two.vreg
                && one.alloc == two.alloc;
        }
    };

    // Items still to be processed.
    Vector<IntegrityItem, 10, SystemAllocPolicy> worklist;

    // Set of all items that have already been processed.
    typedef HashSet<IntegrityItem, IntegrityItem, SystemAllocPolicy> IntegrityItemSet;
    IntegrityItemSet seen;

    MOZ_MUST_USE bool checkIntegrity(LBlock* block, LInstruction* ins, uint32_t vreg,
                                     LAllocation alloc, bool populateSafepoints);
    MOZ_MUST_USE bool checkSafepointAllocation(LInstruction* ins, uint32_t vreg, LAllocation alloc,
                                               bool populateSafepoints);
    MOZ_MUST_USE bool addPredecessor(LBlock* block, uint32_t vreg, LAllocation alloc);

    void dump();
};

// Represents with better-than-instruction precision a position in the
// instruction stream.
//
// An issue comes up when performing register allocation as to how to represent
// information such as "this register is only needed for the input of
// this instruction, it can be clobbered in the output". Just having ranges
// of instruction IDs is insufficiently expressive to denote all possibilities.
// This class solves this issue by associating an extra bit with the instruction
// ID which indicates whether the position is the input half or output half of
// an instruction.
class CodePosition
{
  private:
    constexpr explicit CodePosition(uint32_t bits)
      : bits_(bits)
    { }

    static const unsigned int INSTRUCTION_SHIFT = 1;
    static const unsigned int SUBPOSITION_MASK = 1;
    uint32_t bits_;

  public:
    static const CodePosition MAX;
    static const CodePosition MIN;

    // This is the half of the instruction this code position represents, as
    // described in the huge comment above.
    enum SubPosition {
        INPUT,
        OUTPUT
    };

    constexpr CodePosition() : bits_(0)
    { }

    CodePosition(uint32_t instruction, SubPosition where) {
        MOZ_ASSERT(instruction < 0x80000000u);
        MOZ_ASSERT(((uint32_t)where & SUBPOSITION_MASK) == (uint32_t)where);
        bits_ = (instruction << INSTRUCTION_SHIFT) | (uint32_t)where;
    }

    uint32_t ins() const {
        return bits_ >> INSTRUCTION_SHIFT;
    }

    uint32_t bits() const {
        return bits_;
    }

    SubPosition subpos() const {
        return (SubPosition)(bits_ & SUBPOSITION_MASK);
    }

    bool operator <(CodePosition other) const {
        return bits_ < other.bits_;
    }

    bool operator <=(CodePosition other) const {
        return bits_ <= other.bits_;
    }

    bool operator !=(CodePosition other) const {
        return bits_ != other.bits_;
    }

    bool operator ==(CodePosition other) const {
        return bits_ == other.bits_;
    }

    bool operator >(CodePosition other) const {
        return bits_ > other.bits_;
    }

    bool operator >=(CodePosition other) const {
        return bits_ >= other.bits_;
    }

    uint32_t operator -(CodePosition other) const {
        MOZ_ASSERT(bits_ >= other.bits_);
        return bits_ - other.bits_;
    }

    CodePosition previous() const {
        MOZ_ASSERT(*this != MIN);
        return CodePosition(bits_ - 1);
    }
    CodePosition next() const {
        MOZ_ASSERT(*this != MAX);
        return CodePosition(bits_ + 1);
    }
};

// Structure to track all moves inserted next to instructions in a graph.
class InstructionDataMap
{
    FixedList<LNode*> insData_;

  public:
    InstructionDataMap()
      : insData_()
    { }

    MOZ_MUST_USE bool init(MIRGenerator* gen, uint32_t numInstructions) {
        if (!insData_.init(gen->alloc(), numInstructions))
            return false;
        memset(&insData_[0], 0, sizeof(LNode*) * numInstructions);
        return true;
    }

    LNode*& operator[](CodePosition pos) {
        return operator[](pos.ins());
    }
    LNode* const& operator[](CodePosition pos) const {
        return operator[](pos.ins());
    }
    LNode*& operator[](uint32_t ins) {
        return insData_[ins];
    }
    LNode* const& operator[](uint32_t ins) const {
        return insData_[ins];
    }
};

// Common superclass for register allocators.
class RegisterAllocator
{
    void operator=(const RegisterAllocator&) = delete;
    RegisterAllocator(const RegisterAllocator&) = delete;

  protected:
    // Context
    MIRGenerator* mir;
    LIRGenerator* lir;
    LIRGraph& graph;

    // Pool of all registers that should be considered allocateable
    AllocatableRegisterSet allRegisters_;

    // Computed data
    InstructionDataMap insData;
    Vector<CodePosition, 12, SystemAllocPolicy> entryPositions;
    Vector<CodePosition, 12, SystemAllocPolicy> exitPositions;

    RegisterAllocator(MIRGenerator* mir, LIRGenerator* lir, LIRGraph& graph)
      : mir(mir),
        lir(lir),
        graph(graph),
        allRegisters_(RegisterSet::All())
    {
        if (mir->compilingWasm()) {
#if defined(JS_CODEGEN_X64)
            allRegisters_.take(AnyRegister(HeapReg));
#elif defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_MIPS32) || defined(JS_CODEGEN_MIPS64)
            allRegisters_.take(AnyRegister(HeapReg));
            allRegisters_.take(AnyRegister(GlobalReg));
#elif defined(JS_CODEGEN_ARM64)
            allRegisters_.take(AnyRegister(HeapReg));
            allRegisters_.take(AnyRegister(HeapLenReg));
            allRegisters_.take(AnyRegister(GlobalReg));
#endif
        } else {
            if (FramePointer != InvalidReg && mir->instrumentedProfiling())
                allRegisters_.take(AnyRegister(FramePointer));
        }
    }

    MOZ_MUST_USE bool init();

    TempAllocator& alloc() const {
        return mir->alloc();
    }

    CodePosition outputOf(const LNode* ins) const {
        return ins->isPhi()
               ? outputOf(ins->toPhi())
               : outputOf(ins->toInstruction());
    }
    CodePosition outputOf(const LPhi* ins) const {
        // All phis in a block write their outputs after all of them have
        // read their inputs. Consequently, it doesn't make sense to talk
        // about code positions in the middle of a series of phis.
        LBlock* block = ins->block();
        return CodePosition(block->getPhi(block->numPhis() - 1)->id(), CodePosition::OUTPUT);
    }
    CodePosition outputOf(const LInstruction* ins) const {
        return CodePosition(ins->id(), CodePosition::OUTPUT);
    }
    CodePosition inputOf(const LNode* ins) const {
        return ins->isPhi()
               ? inputOf(ins->toPhi())
               : inputOf(ins->toInstruction());
    }
    CodePosition inputOf(const LPhi* ins) const {
        // All phis in a block read their inputs before any of them write their
        // outputs. Consequently, it doesn't make sense to talk about code
        // positions in the middle of a series of phis.
        return CodePosition(ins->block()->getPhi(0)->id(), CodePosition::INPUT);
    }
    CodePosition inputOf(const LInstruction* ins) const {
        return CodePosition(ins->id(), CodePosition::INPUT);
    }
    CodePosition entryOf(const LBlock* block) {
        return entryPositions[block->mir()->id()];
    }
    CodePosition exitOf(const LBlock* block) {
        return exitPositions[block->mir()->id()];
    }

    LMoveGroup* getInputMoveGroup(LInstruction* ins);
    LMoveGroup* getFixReuseMoveGroup(LInstruction* ins);
    LMoveGroup* getMoveGroupAfter(LInstruction* ins);

    CodePosition minimalDefEnd(LNode* ins) {
        // Compute the shortest interval that captures vregs defined by ins.
        // Watch for instructions that are followed by an OSI point.
        // If moves are introduced between the instruction and the OSI point then
        // safepoint information for the instruction may be incorrect.
        while (true) {
            LNode* next = insData[ins->id() + 1];
            if (!next->isOsiPoint())
                break;
            ins = next;
        }

        return outputOf(ins);
    }

    void dumpInstructions();
};

static inline AnyRegister
GetFixedRegister(const LDefinition* def, const LUse* use)
{
    return def->isFloatReg()
           ? AnyRegister(FloatRegister::FromCode(use->registerCode()))
           : AnyRegister(Register::FromCode(use->registerCode()));
}

} // namespace jit
} // namespace js

#endif /* jit_RegisterAllocator_h */