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