/*
 * Copyright (c) 2004-2005 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Kevin Lim
 */

#ifndef __CPU_O3_CPU_INST_QUEUE_HH__
#define __CPU_O3_CPU_INST_QUEUE_HH__

#include <list>
#include <map>
#include <queue>
#include <vector>

#include "base/statistics.hh"
#include "base/timebuf.hh"
#include "cpu/inst_seq.hh"
#include "sim/host.hh"

/**
 * A standard instruction queue class.  It holds ready instructions, in
 * order, in seperate priority queues to facilitate the scheduling of
 * instructions.  The IQ uses a separate linked list to track dependencies.
 * Similar to the rename map and the free list, it expects that
 * floating point registers have their indices start after the integer
 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
 * and 96-191 are fp).  This remains true even for both logical and
 * physical register indices.
 */
template <class Impl>
class InstructionQueue
{
  public:
    //Typedefs from the Impl.
    typedef typename Impl::FullCPU FullCPU;
    typedef typename Impl::DynInstPtr DynInstPtr;
    typedef typename Impl::Params Params;

    typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
    typedef typename Impl::CPUPol::IssueStruct IssueStruct;
    typedef typename Impl::CPUPol::TimeStruct TimeStruct;

    // Typedef of iterator through the list of instructions.  Might be
    // better to untie this from the FullCPU or pass its information to
    // the stages.
    typedef typename std::list<DynInstPtr>::iterator ListIt;

    /**
     * Struct for comparing entries to be added to the priority queue.  This
     * gives reverse ordering to the instructions in terms of sequence
     * numbers: the instructions with smaller sequence numbers (and hence
     * are older) will be at the top of the priority queue.
     */
    struct pqCompare
    {
        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
        {
            return lhs->seqNum > rhs->seqNum;
        }
    };

    /**
     * Struct for comparing entries to be added to the set.  This gives
     * standard ordering in terms of sequence numbers.
     */
    struct setCompare
    {
        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
        {
            return lhs->seqNum < rhs->seqNum;
        }
    };

    typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare>
    ReadyInstQueue;

    InstructionQueue(Params &params);

    void regStats();

    void setCPU(FullCPU *cpu);

    void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);

    void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);

    unsigned numFreeEntries();

    bool isFull();

    void insert(DynInstPtr &new_inst);

    void insertNonSpec(DynInstPtr &new_inst);

    void advanceTail(DynInstPtr &inst);

    void scheduleReadyInsts();

    void scheduleNonSpec(const InstSeqNum &inst);

    void wakeDependents(DynInstPtr &completed_inst);

    void violation(DynInstPtr &store, DynInstPtr &faulting_load);

    // Change this to take in the sequence number
    void squash();

    void doSquash();

    void stopSquash();

  private:
    /** Pointer to the CPU. */
    FullCPU *cpu;

    /** The memory dependence unit, which tracks/predicts memory dependences
     *  between instructions.
     */
    MemDepUnit memDepUnit;

    /** The queue to the execute stage.  Issued instructions will be written
     *  into it.
     */
    TimeBuffer<IssueStruct> *issueToExecuteQueue;

    /** The backwards time buffer. */
    TimeBuffer<TimeStruct> *timeBuffer;

    /** Wire to read information from timebuffer. */
    typename TimeBuffer<TimeStruct>::wire fromCommit;

    enum InstList {
        Int,
        Float,
        Branch,
        Memory,
        Misc,
        Squashed,
        None
    };

    /** List of ready int instructions.  Used to keep track of the order in
     *  which instructions should issue.
     */
    ReadyInstQueue readyIntInsts;

    /** List of ready floating point instructions. */
    ReadyInstQueue readyFloatInsts;

    /** List of ready branch instructions. */
    ReadyInstQueue readyBranchInsts;

    /** List of ready miscellaneous instructions. */
    ReadyInstQueue readyMiscInsts;

    /** List of squashed instructions (which are still valid and in IQ).
     *  Implemented using a priority queue; the entries must contain both
     *  the IQ index and sequence number of each instruction so that
     *  ordering based on sequence numbers can be used.
     */
    ReadyInstQueue squashedInsts;

    /** List of non-speculative instructions that will be scheduled
     *  once the IQ gets a signal from commit.  While it's redundant to
     *  have the key be a part of the value (the sequence number is stored
     *  inside of DynInst), when these instructions are woken up only
     *  the sequence number will be available.  Thus it is most efficient to be
     *  able to search by the sequence number alone.
     */
    std::map<InstSeqNum, DynInstPtr> nonSpecInsts;

    typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t;

    /** Number of free IQ entries left. */
    unsigned freeEntries;

    /** The number of entries in the instruction queue. */
    unsigned numEntries;

    /** The number of integer instructions that can be issued in one
     *  cycle.
     */
    unsigned intWidth;

    /** The number of floating point instructions that can be issued
     *  in one cycle.
     */
    unsigned floatWidth;

    /** The number of branches that can be issued in one cycle. */
    unsigned branchWidth;

    /** The number of memory instructions that can be issued in one cycle. */
    unsigned memoryWidth;

    /** The total number of instructions that can be issued in one cycle. */
    unsigned totalWidth;

    //The number of physical registers in the CPU.
    unsigned numPhysRegs;

    /** The number of physical integer registers in the CPU. */
    unsigned numPhysIntRegs;

    /** The number of floating point registers in the CPU. */
    unsigned numPhysFloatRegs;

    /** Delay between commit stage and the IQ.
     *  @todo: Make there be a distinction between the delays within IEW.
     */
    unsigned commitToIEWDelay;

    //////////////////////////////////
    // Variables needed for squashing
    //////////////////////////////////

    /** The sequence number of the squashed instruction. */
    InstSeqNum squashedSeqNum;

    /** Iterator that points to the youngest instruction in the IQ. */
    ListIt tail;

    /** Iterator that points to the last instruction that has been squashed.
     *  This will not be valid unless the IQ is in the process of squashing.
     */
    ListIt squashIt;

    ///////////////////////////////////
    // Dependency graph stuff
    ///////////////////////////////////

    class DependencyEntry
    {
      public:
        DynInstPtr inst;
        //Might want to include data about what arch. register the
        //dependence is waiting on.
        DependencyEntry *next;

        //This function, and perhaps this whole class, stand out a little
        //bit as they don't fit a classification well.  I want access
        //to the underlying structure of the linked list, yet at
        //the same time it feels like this should be something abstracted
        //away.  So for now it will sit here, within the IQ, until
        //a better implementation is decided upon.
        // This function probably shouldn't be within the entry...
        void insert(DynInstPtr &new_inst);

        void remove(DynInstPtr &inst_to_remove);

        // Debug variable, remove when done testing.
        static unsigned mem_alloc_counter;
    };

    /** Array of linked lists.  Each linked list is a list of all the
     *  instructions that depend upon a given register.  The actual
     *  register's index is used to index into the graph; ie all
     *  instructions in flight that are dependent upon r34 will be
     *  in the linked list of dependGraph[34].
     */
    DependencyEntry *dependGraph;

    /** A cache of the recently woken registers.  It is 1 if the register
     *  has been woken up recently, and 0 if the register has been added
     *  to the dependency graph and has not yet received its value.  It
     *  is basically a secondary scoreboard, and should pretty much mirror
     *  the scoreboard that exists in the rename map.
     */
    vector<bool> regScoreboard;

    bool addToDependents(DynInstPtr &new_inst);
    void insertDependency(DynInstPtr &new_inst);
    void createDependency(DynInstPtr &new_inst);

    void addIfReady(DynInstPtr &inst);

  private:
    /** Debugging function to count how many entries are in the IQ.  It does
     *  a linear walk through the instructions, so do not call this function
     *  during normal execution.
     */
    int countInsts();

    /** Debugging function to dump out the dependency graph.
     */
    void dumpDependGraph();

    /** Debugging function to dump all the list sizes, as well as print
     *  out the list of nonspeculative instructions.  Should not be used
     *  in any other capacity, but it has no harmful sideaffects.
     */
    void dumpLists();

    Stats::Scalar<> iqInstsAdded;
    Stats::Scalar<> iqNonSpecInstsAdded;
//    Stats::Scalar<> iqIntInstsAdded;
    Stats::Scalar<> iqIntInstsIssued;
//    Stats::Scalar<> iqFloatInstsAdded;
    Stats::Scalar<> iqFloatInstsIssued;
//    Stats::Scalar<> iqBranchInstsAdded;
    Stats::Scalar<> iqBranchInstsIssued;
//    Stats::Scalar<> iqMemInstsAdded;
    Stats::Scalar<> iqMemInstsIssued;
//    Stats::Scalar<> iqMiscInstsAdded;
    Stats::Scalar<> iqMiscInstsIssued;
    Stats::Scalar<> iqSquashedInstsIssued;
    Stats::Scalar<> iqLoopSquashStalls;
    Stats::Scalar<> iqSquashedInstsExamined;
    Stats::Scalar<> iqSquashedOperandsExamined;
    Stats::Scalar<> iqSquashedNonSpecRemoved;

};

#endif //__CPU_O3_CPU_INST_QUEUE_HH__