src/cpu/o3/rename.hh

   1 /*
   2  * Copyright (c) 2012 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2004-2006 The Regents of The University of Michigan
  15  * Copyright (c) 2013 Advanced Micro Devices, Inc.
  16  * All rights reserved.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions are
  20  * met: redistributions of source code must retain the above copyright
  21  * notice, this list of conditions and the following disclaimer;
  22  * redistributions in binary form must reproduce the above copyright
  23  * notice, this list of conditions and the following disclaimer in the
  24  * documentation and/or other materials provided with the distribution;
  25  * neither the name of the copyright holders nor the names of its
  26  * contributors may be used to endorse or promote products derived from
  27  * this software without specific prior written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  30  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  31  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  32  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  33  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  34  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  35  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  36  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  37  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  38  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  39  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40  *
  41  * Authors: Kevin Lim
  42  */
  43
  44 #ifndef __CPU_O3_RENAME_HH__
  45 #define __CPU_O3_RENAME_HH__
  46
  47 #include <list>
  48 #include <utility>
  49
  50 #include "base/statistics.hh"
  51 #include "config/the_isa.hh"
  52 #include "cpu/timebuf.hh"
  53 #include "sim/probe/probe.hh"
  54
  55 struct DerivO3CPUParams;
  56
  57 /**
  58  * DefaultRename handles both single threaded and SMT rename. Its
  59  * width is specified by the parameters; each cycle it tries to rename
  60  * that many instructions. It holds onto the rename history of all
  61  * instructions with destination registers, storing the
  62  * arch. register, the new physical register, and the old physical
  63  * register, to allow for undoing of mappings if squashing happens, or
  64  * freeing up registers upon commit. Rename handles blocking if the
  65  * ROB, IQ, or LSQ is going to be full. Rename also handles barriers,
  66  * and does so by stalling on the instruction until the ROB is empty
  67  * and there are no instructions in flight to the ROB.
  68  */
  69 template<class Impl>
  70 class DefaultRename
  71 {
  72   public:
  73     // Typedefs from the Impl.
  74     typedef typename Impl::CPUPol CPUPol;
  75     typedef typename Impl::DynInstPtr DynInstPtr;
  76     typedef typename Impl::O3CPU O3CPU;
  77
  78     // Typedefs from the CPUPol
  79     typedef typename CPUPol::DecodeStruct DecodeStruct;
  80     typedef typename CPUPol::RenameStruct RenameStruct;
  81     typedef typename CPUPol::TimeStruct TimeStruct;
  82     typedef typename CPUPol::FreeList FreeList;
  83     typedef typename CPUPol::RenameMap RenameMap;
  84     // These are used only for initialization.
  85     typedef typename CPUPol::IEW IEW;
  86     typedef typename CPUPol::Commit Commit;
  87
  88     // Typedefs from the ISA.
  89     typedef TheISA::RegIndex RegIndex;
  90
  91     // A deque is used to queue the instructions. Barrier insts must
  92     // be added to the front of the queue, which is the only reason for
  93     // using a deque instead of a queue. (Most other stages use a
  94     // queue)
  95     typedef std::deque<DynInstPtr> InstQueue;
  96
  97   public:
  98     /** Overall rename status. Used to determine if the CPU can
  99      * deschedule itself due to a lack of activity.
 100      */
 101     enum RenameStatus {
 102         Active,
 103         Inactive
 104     };
 105
 106     /** Individual thread status. */
 107     enum ThreadStatus {
 108         Running,
 109         Idle,
 110         StartSquash,
 111         Squashing,
 112         Blocked,
 113         Unblocking,
 114         SerializeStall
 115     };
 116
 117   private:
 118     /** Rename status. */
 119     RenameStatus _status;
 120
 121     /** Per-thread status. */
 122     ThreadStatus renameStatus[Impl::MaxThreads];
 123
 124     /** Probe points. */
 125     typedef typename std::pair<InstSeqNum, short int> SeqNumRegPair;
 126     /** To probe when register renaming for an instruction is complete */
 127     ProbePointArg<DynInstPtr> *ppRename;
 128     /**
 129      * To probe when an instruction is squashed and the register mapping
 130      * for it needs to be undone
 131      */
 132     ProbePointArg<SeqNumRegPair> *ppSquashInRename;
 133
 134   public:
 135     /** DefaultRename constructor. */
 136     DefaultRename(O3CPU *_cpu, DerivO3CPUParams *params);
 137
 138     /** Returns the name of rename. */
 139     std::string name() const;
 140
 141     /** Registers statistics. */
 142     void regStats();
 143
 144     /** Registers probes. */
 145     void regProbePoints();
 146
 147     /** Sets the main backwards communication time buffer pointer. */
 148     void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
 149
 150     /** Sets pointer to time buffer used to communicate to the next stage. */
 151     void setRenameQueue(TimeBuffer<RenameStruct> *rq_ptr);
 152
 153     /** Sets pointer to time buffer coming from decode. */
 154     void setDecodeQueue(TimeBuffer<DecodeStruct> *dq_ptr);
 155
 156     /** Sets pointer to IEW stage. Used only for initialization. */
 157     void setIEWStage(IEW *iew_stage)
 158     { iew_ptr = iew_stage; }
 159
 160     /** Sets pointer to commit stage. Used only for initialization. */
 161     void setCommitStage(Commit *commit_stage)
 162     { commit_ptr = commit_stage; }
 163
 164   private:
 165     /** Pointer to IEW stage. Used only for initialization. */
 166     IEW *iew_ptr;
 167
 168     /** Pointer to commit stage. Used only for initialization. */
 169     Commit *commit_ptr;
 170
 171   public:
 172     /** Initializes variables for the stage. */
 173     void startupStage();
 174
 175     /** Sets pointer to list of active threads. */
 176     void setActiveThreads(std::list<ThreadID> *at_ptr);
 177
 178     /** Sets pointer to rename maps (per-thread structures). */
 179     void setRenameMap(RenameMap rm_ptr[Impl::MaxThreads]);
 180
 181     /** Sets pointer to the free list. */
 182     void setFreeList(FreeList *fl_ptr);
 183
 184     /** Sets pointer to the scoreboard. */
 185     void setScoreboard(Scoreboard *_scoreboard);
 186
 187     /** Perform sanity checks after a drain. */
 188     void drainSanityCheck() const;
 189
 190     /** Has the stage drained? */
 191     bool isDrained() const;
 192
 193     /** Takes over from another CPU's thread. */
 194     void takeOverFrom();
 195
 196     /** Squashes all instructions in a thread. */
 197     void squash(const InstSeqNum &squash_seq_num, ThreadID tid);
 198
 199     /** Ticks rename, which processes all input signals and attempts to rename
 200      * as many instructions as possible.
 201      */
 202     void tick();
 203
 204     /** Debugging function used to dump history buffer of renamings. */
 205     void dumpHistory();
 206
 207   private:
 208     /** Reset this pipeline stage */
 209     void resetStage();
 210
 211     /** Determines what to do based on rename's current status.
 212      * @param status_change rename() sets this variable if there was a status
 213      * change (ie switching from blocking to unblocking).
 214      * @param tid Thread id to rename instructions from.
 215      */
 216     void rename(bool &status_change, ThreadID tid);
 217
 218     /** Renames instructions for the given thread. Also handles serializing
 219      * instructions.
 220      */
 221     void renameInsts(ThreadID tid);
 222
 223     /** Inserts unused instructions from a given thread into the skid buffer,
 224      * to be renamed once rename unblocks.
 225      */
 226     void skidInsert(ThreadID tid);
 227
 228     /** Separates instructions from decode into individual lists of instructions
 229      * sorted by thread.
 230      */
 231     void sortInsts();
 232
 233     /** Returns if all of the skid buffers are empty. */
 234     bool skidsEmpty();
 235
 236     /** Updates overall rename status based on all of the threads' statuses. */
 237     void updateStatus();
 238
 239     /** Switches rename to blocking, and signals back that rename has become
 240      * blocked.
 241      * @return Returns true if there is a status change.
 242      */
 243     bool block(ThreadID tid);
 244
 245     /** Switches rename to unblocking if the skid buffer is empty, and signals
 246      * back that rename has unblocked.
 247      * @return Returns true if there is a status change.
 248      */
 249     bool unblock(ThreadID tid);
 250
 251     /** Executes actual squash, removing squashed instructions. */
 252     void doSquash(const InstSeqNum &squash_seq_num, ThreadID tid);
 253
 254     /** Removes a committed instruction's rename history. */
 255     void removeFromHistory(InstSeqNum inst_seq_num, ThreadID tid);
 256
 257     /** Renames the source registers of an instruction. */
 258     inline void renameSrcRegs(DynInstPtr &inst, ThreadID tid);
 259
 260     /** Renames the destination registers of an instruction. */
 261     inline void renameDestRegs(DynInstPtr &inst, ThreadID tid);
 262
 263     /** Calculates the number of free ROB entries for a specific thread. */
 264     inline int calcFreeROBEntries(ThreadID tid);
 265
 266     /** Calculates the number of free IQ entries for a specific thread. */
 267     inline int calcFreeIQEntries(ThreadID tid);
 268
 269     /** Calculates the number of free LQ entries for a specific thread. */
 270     inline int calcFreeLQEntries(ThreadID tid);
 271
 272     /** Calculates the number of free SQ entries for a specific thread. */
 273     inline int calcFreeSQEntries(ThreadID tid);
 274
 275     /** Returns the number of valid instructions coming from decode. */
 276     unsigned validInsts();
 277
 278     /** Reads signals telling rename to block/unblock. */
 279     void readStallSignals(ThreadID tid);
 280
 281     /** Checks if any stages are telling rename to block. */
 282     bool checkStall(ThreadID tid);
 283
 284     /** Gets the number of free entries for a specific thread. */
 285     void readFreeEntries(ThreadID tid);
 286
 287     /** Checks the signals and updates the status. */
 288     bool checkSignalsAndUpdate(ThreadID tid);
 289
 290     /** Either serializes on the next instruction available in the InstQueue,
 291      * or records that it must serialize on the next instruction to enter
 292      * rename.
 293      * @param inst_list The list of younger, unprocessed instructions for the
 294      * thread that has the serializeAfter instruction.
 295      * @param tid The thread id.
 296      */
 297     void serializeAfter(InstQueue &inst_list, ThreadID tid);
 298
 299     /** Holds the information for each destination register rename. It holds
 300      * the instruction's sequence number, the arch register, the old physical
 301      * register for that arch. register, and the new physical register.
 302      */
 303     struct RenameHistory {
 304         RenameHistory(InstSeqNum _instSeqNum, RegIndex _archReg,
 305                       PhysRegIndex _newPhysReg, PhysRegIndex _prevPhysReg)
 306             : instSeqNum(_instSeqNum), archReg(_archReg),
 307               newPhysReg(_newPhysReg), prevPhysReg(_prevPhysReg)
 308         {
 309         }
 310
 311         /** The sequence number of the instruction that renamed. */
 312         InstSeqNum instSeqNum;
 313         /** The architectural register index that was renamed. */
 314         RegIndex archReg;
 315         /** The new physical register that the arch. register is renamed to. */
 316         PhysRegIndex newPhysReg;
 317         /** The old physical register that the arch. register was renamed to. */
 318         PhysRegIndex prevPhysReg;
 319     };
 320
 321     /** A per-thread list of all destination register renames, used to either
 322      * undo rename mappings or free old physical registers.
 323      */
 324     std::list<RenameHistory> historyBuffer[Impl::MaxThreads];
 325
 326     /** Pointer to CPU. */
 327     O3CPU *cpu;
 328
 329     /** Pointer to main time buffer used for backwards communication. */
 330     TimeBuffer<TimeStruct> *timeBuffer;
 331
 332     /** Wire to get IEW's output from backwards time buffer. */
 333     typename TimeBuffer<TimeStruct>::wire fromIEW;
 334
 335     /** Wire to get commit's output from backwards time buffer. */
 336     typename TimeBuffer<TimeStruct>::wire fromCommit;
 337
 338     /** Wire to write infromation heading to previous stages. */
 339     typename TimeBuffer<TimeStruct>::wire toDecode;
 340
 341     /** Rename instruction queue. */
 342     TimeBuffer<RenameStruct> *renameQueue;
 343
 344     /** Wire to write any information heading to IEW. */
 345     typename TimeBuffer<RenameStruct>::wire toIEW;
 346
 347     /** Decode instruction queue interface. */
 348     TimeBuffer<DecodeStruct> *decodeQueue;
 349
 350     /** Wire to get decode's output from decode queue. */
 351     typename TimeBuffer<DecodeStruct>::wire fromDecode;
 352
 353     /** Queue of all instructions coming from decode this cycle. */
 354     InstQueue insts[Impl::MaxThreads];
 355
 356     /** Skid buffer between rename and decode. */
 357     InstQueue skidBuffer[Impl::MaxThreads];
 358
 359     /** Rename map interface. */
 360     RenameMap *renameMap[Impl::MaxThreads];
 361
 362     /** Free list interface. */
 363     FreeList *freeList;
 364
 365     /** Pointer to the list of active threads. */
 366     std::list<ThreadID> *activeThreads;
 367
 368     /** Pointer to the scoreboard. */
 369     Scoreboard *scoreboard;
 370
 371     /** Count of instructions in progress that have been sent off to the IQ
 372      * and ROB, but are not yet included in their occupancy counts.
 373      */
 374     int instsInProgress[Impl::MaxThreads];
 375
 376     /** Count of Load instructions in progress that have been sent off to the IQ
 377      * and ROB, but are not yet included in their occupancy counts.
 378      */
 379     int loadsInProgress[Impl::MaxThreads];
 380
 381     /** Count of Store instructions in progress that have been sent off to the IQ
 382      * and ROB, but are not yet included in their occupancy counts.
 383      */
 384     int storesInProgress[Impl::MaxThreads];
 385
 386     /** Variable that tracks if decode has written to the time buffer this
 387      * cycle. Used to tell CPU if there is activity this cycle.
 388      */
 389     bool wroteToTimeBuffer;
 390
 391     /** Structures whose free entries impact the amount of instructions that
 392      * can be renamed.
 393      */
 394     struct FreeEntries {
 395         unsigned iqEntries;
 396         unsigned robEntries;
 397         unsigned lqEntries;
 398         unsigned sqEntries;
 399     };
 400
 401     /** Per-thread tracking of the number of free entries of back-end
 402      * structures.
 403      */
 404     FreeEntries freeEntries[Impl::MaxThreads];
 405
 406     /** Records if the ROB is empty. In SMT mode the ROB may be dynamically
 407      * partitioned between threads, so the ROB must tell rename when it is
 408      * empty.
 409      */
 410     bool emptyROB[Impl::MaxThreads];
 411
 412     /** Source of possible stalls. */
 413     struct Stalls {
 414         bool iew;
 415         bool commit;
 416     };
 417
 418     /** Tracks which stages are telling decode to stall. */
 419     Stalls stalls[Impl::MaxThreads];
 420
 421     /** The serialize instruction that rename has stalled on. */
 422     DynInstPtr serializeInst[Impl::MaxThreads];
 423
 424     /** Records if rename needs to serialize on the next instruction for any
 425      * thread.
 426      */
 427     bool serializeOnNextInst[Impl::MaxThreads];
 428
 429     /** Delay between iew and rename, in ticks. */
 430     int iewToRenameDelay;
 431
 432     /** Delay between decode and rename, in ticks. */
 433     int decodeToRenameDelay;
 434
 435     /** Delay between commit and rename, in ticks. */
 436     unsigned commitToRenameDelay;
 437
 438     /** Rename width, in instructions. */
 439     unsigned renameWidth;
 440
 441     /** Commit width, in instructions.  Used so rename knows how many
 442      *  instructions might have freed registers in the previous cycle.
 443      */
 444     unsigned commitWidth;
 445
 446     /** The index of the instruction in the time buffer to IEW that rename is
 447      * currently using.
 448      */
 449     unsigned toIEWIndex;
 450
 451     /** Whether or not rename needs to block this cycle. */
 452     bool blockThisCycle;
 453
 454     /** Whether or not rename needs to resume a serialize instruction
 455      * after squashing. */
 456     bool resumeSerialize;
 457
 458     /** Whether or not rename needs to resume clearing out the skidbuffer
 459      * after squashing. */
 460     bool resumeUnblocking;
 461
 462     /** The number of threads active in rename. */
 463     ThreadID numThreads;
 464
 465     /** The maximum skid buffer size. */
 466     unsigned skidBufferMax;
 467
 468     PhysRegIndex maxPhysicalRegs;
 469
 470     /** Enum to record the source of a structure full stall.  Can come from
 471      * either ROB, IQ, LSQ, and it is priortized in that order.
 472      */
 473     enum FullSource {
 474         ROB,
 475         IQ,
 476         LQ,
 477         SQ,
 478         NONE
 479     };
 480
 481     /** Function used to increment the stat that corresponds to the source of
 482      * the stall.
 483      */
 484     inline void incrFullStat(const FullSource &source);
 485
 486     /** Stat for total number of cycles spent squashing. */
 487     Stats::Scalar renameSquashCycles;
 488     /** Stat for total number of cycles spent idle. */
 489     Stats::Scalar renameIdleCycles;
 490     /** Stat for total number of cycles spent blocking. */
 491     Stats::Scalar renameBlockCycles;
 492     /** Stat for total number of cycles spent stalling for a serializing inst. */
 493     Stats::Scalar renameSerializeStallCycles;
 494     /** Stat for total number of cycles spent running normally. */
 495     Stats::Scalar renameRunCycles;
 496     /** Stat for total number of cycles spent unblocking. */
 497     Stats::Scalar renameUnblockCycles;
 498     /** Stat for total number of renamed instructions. */
 499     Stats::Scalar renameRenamedInsts;
 500     /** Stat for total number of squashed instructions that rename discards. */
 501     Stats::Scalar renameSquashedInsts;
 502     /** Stat for total number of times that the ROB starts a stall in rename. */
 503     Stats::Scalar renameROBFullEvents;
 504     /** Stat for total number of times that the IQ starts a stall in rename. */
 505     Stats::Scalar renameIQFullEvents;
 506     /** Stat for total number of times that the LQ starts a stall in rename. */
 507     Stats::Scalar renameLQFullEvents;
 508     /** Stat for total number of times that the SQ starts a stall in rename. */
 509     Stats::Scalar renameSQFullEvents;
 510     /** Stat for total number of times that rename runs out of free registers
 511      * to use to rename. */
 512     Stats::Scalar renameFullRegistersEvents;
 513     /** Stat for total number of renamed destination registers. */
 514     Stats::Scalar renameRenamedOperands;
 515     /** Stat for total number of source register rename lookups. */
 516     Stats::Scalar renameRenameLookups;
 517     Stats::Scalar intRenameLookups;
 518     Stats::Scalar fpRenameLookups;
 519     /** Stat for total number of committed renaming mappings. */
 520     Stats::Scalar renameCommittedMaps;
 521     /** Stat for total number of mappings that were undone due to a squash. */
 522     Stats::Scalar renameUndoneMaps;
 523     /** Number of serialize instructions handled. */
 524     Stats::Scalar renamedSerializing;
 525     /** Number of instructions marked as temporarily serializing. */
 526     Stats::Scalar renamedTempSerializing;
 527     /** Number of instructions inserted into skid buffers. */
 528     Stats::Scalar renameSkidInsts;
 529 };
 530
 531 #endif // __CPU_O3_RENAME_HH__