inst_queue.hh

Go to the documentation of this file.

/*
 * Copyright (c) 2011-2012, 2014 ARM Limited
 * Copyright (c) 2013 Advanced Micro Devices, Inc.
 * All rights reserved.
 *
 * The license below extends only to copyright in the software and shall
 * not be construed as granting a license to any other intellectual
 * property including but not limited to intellectual property relating
 * to a hardware implementation of the functionality of the software
 * licensed hereunder.  You may use the software subject to the license
 * terms below provided that you ensure that this notice is replicated
 * unmodified and in its entirety in all distributions of the software,
 * modified or unmodified, in source code or in binary form.
 *
 * Copyright (c) 2004-2006 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_INST_QUEUE_HH__
#define __CPU_O3_INST_QUEUE_HH__

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

#include "base/statistics.hh"
#include "base/types.hh"
#include "cpu/o3/dep_graph.hh"
#include "cpu/inst_seq.hh"
#include "cpu/op_class.hh"
#include "cpu/timebuf.hh"
#include "sim/eventq.hh"

struct DerivO3CPUParams;
class FUPool;
class MemInterface;

template <class Impl>
class InstructionQueue
{
  public:
    //Typedefs from the Impl.
    typedef typename Impl::O3CPU O3CPU;
    typedef typename Impl::DynInstPtr DynInstPtr;

    typedef typename Impl::CPUPol::IEW IEW;
    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.
    typedef typename std::list<DynInstPtr>::iterator ListIt;

    class FUCompletion : public Event {
      private:
        DynInstPtr inst;

        int fuIdx;

        InstructionQueue<Impl> *iqPtr;

        bool freeFU;

      public:
        FUCompletion(DynInstPtr &_inst, int fu_idx,
                     InstructionQueue<Impl> *iq_ptr);

        virtual void process();
        virtual const char *description() const;
        void setFreeFU() { freeFU = true; }
    };

    InstructionQueue(O3CPU *cpu_ptr, IEW *iew_ptr, DerivO3CPUParams *params);

    ~InstructionQueue();

    std::string name() const;

    void regStats();

    void resetState();

    void setActiveThreads(std::list<ThreadID> *at_ptr);

    void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);

    void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);

    bool isDrained() const;

    void drainSanityCheck() const;

    void takeOverFrom();

    int entryAmount(ThreadID num_threads);

    void resetEntries();

    unsigned numFreeEntries();

    unsigned numFreeEntries(ThreadID tid);

    bool isFull();

    bool isFull(ThreadID tid);

    bool hasReadyInsts();

    void insert(DynInstPtr &new_inst);

    void insertNonSpec(DynInstPtr &new_inst);

    void insertBarrier(DynInstPtr &barr_inst);

    DynInstPtr getInstToExecute();

    DynInstPtr getDeferredMemInstToExecute();

    DynInstPtr getBlockedMemInstToExecute();

    void recordProducer(DynInstPtr &inst)
    { addToProducers(inst); }

    void processFUCompletion(DynInstPtr &inst, int fu_idx);

    void scheduleReadyInsts();

    void scheduleNonSpec(const InstSeqNum &inst);

    void commit(const InstSeqNum &inst, ThreadID tid = 0);

    int wakeDependents(DynInstPtr &completed_inst);

    void addReadyMemInst(DynInstPtr &ready_inst);

    void rescheduleMemInst(DynInstPtr &resched_inst);

    void replayMemInst(DynInstPtr &replay_inst);

    void completeMemInst(DynInstPtr &completed_inst);

    void deferMemInst(DynInstPtr &deferred_inst);

    void blockMemInst(DynInstPtr &blocked_inst);

    void cacheUnblocked();

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

    void squash(ThreadID tid);

    unsigned getCount(ThreadID tid) { return count[tid]; };

    void printInsts();

  private:
    void doSquash(ThreadID tid);

    // Various pointers

    O3CPU *cpu;

    MemInterface *dcacheInterface;

    IEW *iewStage;

    MemDepUnit memDepUnit[Impl::MaxThreads];

    TimeBuffer<IssueStruct> *issueToExecuteQueue;

    TimeBuffer<TimeStruct> *timeBuffer;

    typename TimeBuffer<TimeStruct>::wire fromCommit;

    FUPool *fuPool;

    // Instruction lists, ready queues, and ordering

    std::list<DynInstPtr> instList[Impl::MaxThreads];

    std::list<DynInstPtr> instsToExecute;

    std::list<DynInstPtr> deferredMemInsts;

    std::list<DynInstPtr> blockedMemInsts;

    std::list<DynInstPtr> retryMemInsts;

    struct pqCompare {
        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
        {
            return lhs->seqNum > rhs->seqNum;
        }
    };

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

    ReadyInstQueue readyInsts[Num_OpClasses];

    std::map<InstSeqNum, DynInstPtr> nonSpecInsts;

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

    struct ListOrderEntry {
        OpClass queueType;
        InstSeqNum oldestInst;
    };

    std::list<ListOrderEntry> listOrder;

    typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;

    bool queueOnList[Num_OpClasses];

    ListOrderIt readyIt[Num_OpClasses];

    void addToOrderList(OpClass op_class);

    void moveToYoungerInst(ListOrderIt age_order_it);

    DependencyGraph<DynInstPtr> dependGraph;

    // Various parameters

    enum IQPolicy {
        Dynamic,
        Partitioned,
        Threshold
    };

    IQPolicy iqPolicy;

    ThreadID numThreads;

    std::list<ThreadID> *activeThreads;

    unsigned count[Impl::MaxThreads];

    unsigned maxEntries[Impl::MaxThreads];

    unsigned freeEntries;

    unsigned numEntries;

    unsigned totalWidth;

    unsigned numPhysRegs;

    int wbOutstanding;

    Cycles commitToIEWDelay;

    InstSeqNum squashedSeqNum[Impl::MaxThreads];

    std::vector<bool> regScoreboard;

    bool addToDependents(DynInstPtr &new_inst);

    void addToProducers(DynInstPtr &new_inst);

    void addIfReady(DynInstPtr &inst);

    int countInsts();

    void dumpLists();

    void dumpInsts();

    Stats::Scalar iqInstsAdded;
    Stats::Scalar iqNonSpecInstsAdded;

    Stats::Scalar iqInstsIssued;
    Stats::Scalar iqIntInstsIssued;
    Stats::Scalar iqFloatInstsIssued;
    Stats::Scalar iqBranchInstsIssued;
    Stats::Scalar iqMemInstsIssued;
    Stats::Scalar iqMiscInstsIssued;
    Stats::Scalar iqSquashedInstsIssued;
    Stats::Scalar iqSquashedInstsExamined;
    Stats::Scalar iqSquashedOperandsExamined;
    Stats::Scalar iqSquashedNonSpecRemoved;
    // Also include number of instructions rescheduled and replayed.

//    Stats::VectorDistribution queueResDist;
    Stats::Distribution numIssuedDist;
//    Stats::VectorDistribution issueDelayDist;

    Stats::Vector statFuBusy;
//    Stats::Vector dist_unissued;
    Stats::Vector2d statIssuedInstType;

    Stats::Formula issueRate;

    Stats::Vector fuBusy;
    Stats::Formula fuBusyRate;
   public:
    Stats::Scalar intInstQueueReads;
    Stats::Scalar intInstQueueWrites;
    Stats::Scalar intInstQueueWakeupAccesses;
    Stats::Scalar fpInstQueueReads;
    Stats::Scalar fpInstQueueWrites;
    Stats::Scalar fpInstQueueWakeupQccesses;

    Stats::Scalar intAluAccesses;
    Stats::Scalar fpAluAccesses;
};

#endif //__CPU_O3_INST_QUEUE_HH__