inst_queue.hh revision 1684
19793Sakash.bagdia@arm.com#ifndef __CPU_BETA_CPU_INST_QUEUE_HH__
27586SAli.Saidi@arm.com#define __CPU_BETA_CPU_INST_QUEUE_HH__
37586SAli.Saidi@arm.com
47586SAli.Saidi@arm.com#include <list>
57586SAli.Saidi@arm.com#include <map>
67586SAli.Saidi@arm.com#include <queue>
77586SAli.Saidi@arm.com#include <stdint.h>
87586SAli.Saidi@arm.com#include <vector>
97586SAli.Saidi@arm.com
107586SAli.Saidi@arm.com#include "base/statistics.hh"
117586SAli.Saidi@arm.com#include "base/timebuf.hh"
127586SAli.Saidi@arm.com#include "cpu/inst_seq.hh"
133970Sgblack@eecs.umich.edu
143005Sstever@eecs.umich.edu/**
153005Sstever@eecs.umich.edu * A standard instruction queue class.  It holds instructions in an
163005Sstever@eecs.umich.edu * array, holds the ordering of the instructions within a linked list,
173005Sstever@eecs.umich.edu * and tracks producer/consumer dependencies within a separate linked
183005Sstever@eecs.umich.edu * list.  Similar to the rename map and the free list, it expects that
193005Sstever@eecs.umich.edu * floating point registers have their indices start after the integer
203005Sstever@eecs.umich.edu * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
213005Sstever@eecs.umich.edu * and 96-191 are fp).  This remains true even for both logical and
223005Sstever@eecs.umich.edu * physical register indices.
233005Sstever@eecs.umich.edu */
243005Sstever@eecs.umich.edutemplate <class Impl>
253005Sstever@eecs.umich.educlass InstructionQueue
263005Sstever@eecs.umich.edu{
273005Sstever@eecs.umich.edu  public:
283005Sstever@eecs.umich.edu    //Typedefs from the Impl.
293005Sstever@eecs.umich.edu    typedef typename Impl::FullCPU FullCPU;
303005Sstever@eecs.umich.edu    typedef typename Impl::DynInstPtr DynInstPtr;
313005Sstever@eecs.umich.edu    typedef typename Impl::Params Params;
323005Sstever@eecs.umich.edu
333005Sstever@eecs.umich.edu    typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
343005Sstever@eecs.umich.edu    typedef typename Impl::CPUPol::IssueStruct IssueStruct;
353005Sstever@eecs.umich.edu    typedef typename Impl::CPUPol::TimeStruct TimeStruct;
363005Sstever@eecs.umich.edu
373005Sstever@eecs.umich.edu    // Typedef of iterator through the list of instructions.  Might be
383005Sstever@eecs.umich.edu    // better to untie this from the FullCPU or pass its information to
393005Sstever@eecs.umich.edu    // the stages.
403005Sstever@eecs.umich.edu    typedef typename std::list<DynInstPtr>::iterator ListIt;
416654Snate@binkert.org
426654Snate@binkert.org    /**
432889SN/A     * Struct for comparing entries to be added to the priority queue.  This
442710SN/A     * gives reverse ordering to the instructions in terms of sequence
456654Snate@binkert.org     * numbers: the instructions with smaller sequence numbers (and hence
466654Snate@binkert.org     * are older) will be at the top of the priority queue.
476654Snate@binkert.org     */
485457Ssaidi@eecs.umich.edu    struct pqCompare
496654Snate@binkert.org    {
506654Snate@binkert.org        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
512934SN/A        {
522549SN/A            return lhs->seqNum > rhs->seqNum;
532995SN/A        }
543395Shsul@eecs.umich.edu    };
556981SLisa.Hsu@amd.com
563448Shsul@eecs.umich.edu    /**
578920Snilay@cs.wisc.edu     * Struct for comparing entries to be added to the set.  This gives
583444Sktlim@umich.edu     * standard ordering in terms of sequence numbers.
592889SN/A     */
608920Snilay@cs.wisc.edu    struct setCompare
618920Snilay@cs.wisc.edu    {
623322Shsul@eecs.umich.edu        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
632710SN/A        {
642710SN/A            return lhs->seqNum < rhs->seqNum;
652710SN/A        }
662710SN/A    };
672710SN/A
682710SN/A    typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare>
693322Shsul@eecs.umich.edu    ReadyInstQueue;
703304Sstever@eecs.umich.edu
713322Shsul@eecs.umich.edu    InstructionQueue(Params &params);
723322Shsul@eecs.umich.edu
733304Sstever@eecs.umich.edu    void regStats();
749653SAndreas.Sandberg@ARM.com
759653SAndreas.Sandberg@ARM.com    void setCPU(FullCPU *cpu);
769653SAndreas.Sandberg@ARM.com
779653SAndreas.Sandberg@ARM.com    void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
789653SAndreas.Sandberg@ARM.com
799653SAndreas.Sandberg@ARM.com    void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
809653SAndreas.Sandberg@ARM.com
813481Shsul@eecs.umich.edu    unsigned numFreeEntries();
823481Shsul@eecs.umich.edu
832566SN/A    bool isFull();
849665Sandreas.hansson@arm.com
859665Sandreas.hansson@arm.com    void insert(DynInstPtr &new_inst);
869665Sandreas.hansson@arm.com
879665Sandreas.hansson@arm.com    void insertNonSpec(DynInstPtr &new_inst);
889665Sandreas.hansson@arm.com
892995SN/A    void advanceTail(DynInstPtr &inst);
903304Sstever@eecs.umich.edu
913304Sstever@eecs.umich.edu    void scheduleReadyInsts();
923304Sstever@eecs.umich.edu
932995SN/A    void scheduleNonSpec(const InstSeqNum &inst);
942995SN/A
952995SN/A    void wakeDependents(DynInstPtr &completed_inst);
962917SN/A
972995SN/A    void violation(DynInstPtr &store, DynInstPtr &faulting_load);
988956Sjayneel@cs.wisc.edu
992995SN/A    // Change this to take in the sequence number
1008956Sjayneel@cs.wisc.edu    void squash();
1013304Sstever@eecs.umich.edu
1026135Sgblack@eecs.umich.edu    void doSquash();
1036135Sgblack@eecs.umich.edu
1046654Snate@binkert.org    void stopSquash();
1059665Sandreas.hansson@arm.com
1066654Snate@binkert.org  private:
1079665Sandreas.hansson@arm.com    /** Pointer to the CPU. */
1086654Snate@binkert.org    FullCPU *cpu;
1099665Sandreas.hansson@arm.com
1106654Snate@binkert.org    /** The memory dependence unit, which tracks/predicts memory dependences
1119665Sandreas.hansson@arm.com     *  between instructions.
1129665Sandreas.hansson@arm.com     */
1137586SAli.Saidi@arm.com    MemDepUnit memDepUnit;
1149665Sandreas.hansson@arm.com
1159665Sandreas.hansson@arm.com    /** The queue to the execute stage.  Issued instructions will be written
1169665Sandreas.hansson@arm.com     *  into it.
1173819Shsul@eecs.umich.edu     */
1189059Snilay@cs.wisc.edu    TimeBuffer<IssueStruct> *issueToExecuteQueue;
1193819Shsul@eecs.umich.edu
1209793Sakash.bagdia@arm.com    /** The backwards time buffer. */
1219793Sakash.bagdia@arm.com    TimeBuffer<TimeStruct> *timeBuffer;
1229793Sakash.bagdia@arm.com
1239793Sakash.bagdia@arm.com    /** Wire to read information from timebuffer. */
1249793Sakash.bagdia@arm.com    typename TimeBuffer<TimeStruct>::wire fromCommit;
1259790Sakash.bagdia@arm.com
1263873Sbinkertn@umich.edu    enum InstList {
1273873Sbinkertn@umich.edu        Int,
1283873Sbinkertn@umich.edu        Float,
1293873Sbinkertn@umich.edu        Branch,
1303873Sbinkertn@umich.edu        Memory,
1313873Sbinkertn@umich.edu        Misc,
1328659SAli.Saidi@ARM.com        Squashed,
1338659SAli.Saidi@ARM.com        None
1349793Sakash.bagdia@arm.com    };
1359793Sakash.bagdia@arm.com
1369793Sakash.bagdia@arm.com    /** List of ready int instructions.  Used to keep track of the order in
1373668Srdreslin@umich.edu     *  which instructions should issue.
1389653SAndreas.Sandberg@ARM.com     */
1399653SAndreas.Sandberg@ARM.com    ReadyInstQueue readyIntInsts;
1409653SAndreas.Sandberg@ARM.com
1416636Ssteve.reinhardt@amd.com    /** List of ready floating point instructions. */
1429788Sakash.bagdia@arm.com    ReadyInstQueue readyFloatInsts;
1439788Sakash.bagdia@arm.com
1448839Sandreas.hansson@arm.com    /** List of ready branch instructions. */
1458839Sandreas.hansson@arm.com    ReadyInstQueue readyBranchInsts;
1468713Sandreas.hansson@arm.com
1479408Sandreas.hansson@arm.com    /** List of ready miscellaneous instructions. */
1488839Sandreas.hansson@arm.com    ReadyInstQueue readyMiscInsts;
1498839Sandreas.hansson@arm.com
1505142Ssaidi@eecs.umich.edu    /** List of squashed instructions (which are still valid and in IQ).
1518926Sandreas.hansson@arm.com     *  Implemented using a priority queue; the entries must contain both
1529317Sandreas.hansson@arm.com     *  the IQ index and sequence number of each instruction so that
1539317Sandreas.hansson@arm.com     *  ordering based on sequence numbers can be used.
1549317Sandreas.hansson@arm.com     */
1559317Sandreas.hansson@arm.com    ReadyInstQueue squashedInsts;
1569317Sandreas.hansson@arm.com
1578926Sandreas.hansson@arm.com    /** List of non-speculative instructions that will be scheduled
1583312Sstever@eecs.umich.edu     *  once the IQ gets a signal from commit.  While it's redundant to
1594968Sacolyte@umich.edu     *  have the key be a part of the value (the sequence number is stored
1608926Sandreas.hansson@arm.com     *  inside of DynInst), when these instructions are woken up only
1618887Sgeoffrey.blake@arm.com     *  the sequence number will be available.  Thus it is most efficient to be
1628887Sgeoffrey.blake@arm.com     *  able to search by the sequence number alone.
1639384SAndreas.Sandberg@arm.com     */
1648887Sgeoffrey.blake@arm.com    std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
1658887Sgeoffrey.blake@arm.com
1664968Sacolyte@umich.edu    typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t;
1673005Sstever@eecs.umich.edu
1686654Snate@binkert.org    /** Number of free IQ entries left. */
1699665Sandreas.hansson@arm.com    unsigned freeEntries;
1706654Snate@binkert.org
1719665Sandreas.hansson@arm.com    /** The number of entries in the instruction queue. */
1726654Snate@binkert.org    unsigned numEntries;
1739665Sandreas.hansson@arm.com
1746654Snate@binkert.org    /** The number of integer instructions that can be issued in one
1759665Sandreas.hansson@arm.com     *  cycle.
1767586SAli.Saidi@arm.com     */
1779665Sandreas.hansson@arm.com    unsigned intWidth;
1789665Sandreas.hansson@arm.com
1798661SAli.Saidi@ARM.com    /** The number of floating point instructions that can be issued
1809793Sakash.bagdia@arm.com     *  in one cycle.
1819793Sakash.bagdia@arm.com     */
1829790Sakash.bagdia@arm.com    unsigned floatWidth;
1839793Sakash.bagdia@arm.com
1849793Sakash.bagdia@arm.com    /** The number of branches that can be issued in one cycle. */
1859793Sakash.bagdia@arm.com    unsigned branchWidth;
1869793Sakash.bagdia@arm.com
1879793Sakash.bagdia@arm.com    /** The number of memory instructions that can be issued in one cycle. */
1889384SAndreas.Sandberg@arm.com    unsigned memoryWidth;
1898863Snilay@cs.wisc.edu
1907876Sgblack@eecs.umich.edu    /** The total number of instructions that can be issued in one cycle. */
1914968Sacolyte@umich.edu    unsigned totalWidth;
1928926Sandreas.hansson@arm.com
1934837Ssaidi@eecs.umich.edu    //The number of physical registers in the CPU.
1944837Ssaidi@eecs.umich.edu    unsigned numPhysRegs;
1959408Sandreas.hansson@arm.com
1969653SAndreas.Sandberg@ARM.com    /** The number of physical integer registers in the CPU. */
1979653SAndreas.Sandberg@ARM.com    unsigned numPhysIntRegs;
1989653SAndreas.Sandberg@ARM.com
1999164Sandreas.hansson@arm.com    /** The number of floating point registers in the CPU. */
2009408Sandreas.hansson@arm.com    unsigned numPhysFloatRegs;
2018845Sandreas.hansson@arm.com
2028845Sandreas.hansson@arm.com    /** Delay between commit stage and the IQ.
2034837Ssaidi@eecs.umich.edu     *  @todo: Make there be a distinction between the delays within IEW.
2048659SAli.Saidi@ARM.com     */
2058801Sgblack@eecs.umich.edu    unsigned commitToIEWDelay;
2063005Sstever@eecs.umich.edu
2078801Sgblack@eecs.umich.edu    //////////////////////////////////
2083005Sstever@eecs.umich.edu    // Variables needed for squashing
2093005Sstever@eecs.umich.edu    //////////////////////////////////
2103005Sstever@eecs.umich.edu
2112566SN/A    /** The sequence number of the squashed instruction. */
2127861Sgblack@eecs.umich.edu    InstSeqNum squashedSeqNum;
2137861Sgblack@eecs.umich.edu
2147861Sgblack@eecs.umich.edu    /** Iterator that points to the youngest instruction in the IQ. */
2158635Schris.emmons@arm.com    ListIt tail;
2168635Schris.emmons@arm.com
2178635Schris.emmons@arm.com    /** Iterator that points to the last instruction that has been squashed.
2189061Snilay@cs.wisc.edu     *  This will not be valid unless the IQ is in the process of squashing.
2193481Shsul@eecs.umich.edu     */
220    ListIt squashIt;
221
222    ///////////////////////////////////
223    // Dependency graph stuff
224    ///////////////////////////////////
225
226    class DependencyEntry
227    {
228      public:
229        DynInstPtr inst;
230        //Might want to include data about what arch. register the
231        //dependence is waiting on.
232        DependencyEntry *next;
233
234        //This function, and perhaps this whole class, stand out a little
235        //bit as they don't fit a classification well.  I want access
236        //to the underlying structure of the linked list, yet at
237        //the same time it feels like this should be something abstracted
238        //away.  So for now it will sit here, within the IQ, until
239        //a better implementation is decided upon.
240        // This function probably shouldn't be within the entry...
241        void insert(DynInstPtr &new_inst);
242
243        void remove(DynInstPtr &inst_to_remove);
244
245        // Debug variable, remove when done testing.
246        static unsigned mem_alloc_counter;
247    };
248
249    /** Array of linked lists.  Each linked list is a list of all the
250     *  instructions that depend upon a given register.  The actual
251     *  register's index is used to index into the graph; ie all
252     *  instructions in flight that are dependent upon r34 will be
253     *  in the linked list of dependGraph[34].
254     */
255    DependencyEntry *dependGraph;
256
257    /** A cache of the recently woken registers.  It is 1 if the register
258     *  has been woken up recently, and 0 if the register has been added
259     *  to the dependency graph and has not yet received its value.  It
260     *  is basically a secondary scoreboard, and should pretty much mirror
261     *  the scoreboard that exists in the rename map.
262     */
263    vector<bool> regScoreboard;
264
265    bool addToDependents(DynInstPtr &new_inst);
266    void insertDependency(DynInstPtr &new_inst);
267    void createDependency(DynInstPtr &new_inst);
268
269    void addIfReady(DynInstPtr &inst);
270
271  private:
272    /** Debugging function to count how many entries are in the IQ.  It does
273     *  a linear walk through the instructions, so do not call this function
274     *  during normal execution.
275     */
276    int countInsts();
277
278    /** Debugging function to dump out the dependency graph.
279     */
280    void dumpDependGraph();
281
282    /** Debugging function to dump all the list sizes, as well as print
283     *  out the list of nonspeculative instructions.  Should not be used
284     *  in any other capacity, but it has no harmful sideaffects.
285     */
286    void dumpLists();
287
288    Stats::Scalar<> iqInstsAdded;
289    Stats::Scalar<> iqNonSpecInstsAdded;
290//    Stats::Scalar<> iqIntInstsAdded;
291    Stats::Scalar<> iqIntInstsIssued;
292//    Stats::Scalar<> iqFloatInstsAdded;
293    Stats::Scalar<> iqFloatInstsIssued;
294//    Stats::Scalar<> iqBranchInstsAdded;
295    Stats::Scalar<> iqBranchInstsIssued;
296//    Stats::Scalar<> iqMemInstsAdded;
297    Stats::Scalar<> iqMemInstsIssued;
298//    Stats::Scalar<> iqMiscInstsAdded;
299    Stats::Scalar<> iqMiscInstsIssued;
300    Stats::Scalar<> iqSquashedInstsIssued;
301    Stats::Scalar<> iqLoopSquashStalls;
302    Stats::Scalar<> iqSquashedInstsExamined;
303    Stats::Scalar<> iqSquashedOperandsExamined;
304    Stats::Scalar<> iqSquashedNonSpecRemoved;
305
306};
307
308#endif //__CPU_BETA_CPU_INST_QUEUE_HH__
309