rename.hh revision 2670:9107b8bd08cd
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::FullCPU FullCPU; 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 80 public: 81 /** Overall rename status. Used to determine if the CPU can 82 * deschedule itself due to a lack of activity. 83 */ 84 enum RenameStatus { 85 Active, 86 Inactive 87 }; 88 89 /** Individual thread status. */ 90 enum ThreadStatus { 91 Running, 92 Idle, 93 StartSquash, 94 Squashing, 95 Blocked, 96 Unblocking, 97 SerializeStall 98 }; 99 100 private: 101 /** Rename status. */ 102 RenameStatus _status; 103 104 /** Per-thread status. */ 105 ThreadStatus renameStatus[Impl::MaxThreads]; 106 107 public: 108 /** DefaultRename constructor. */ 109 DefaultRename(Params *params); 110 111 /** Returns the name of rename. */ 112 std::string name() const; 113 114 /** Registers statistics. */ 115 void regStats(); 116 117 /** Sets CPU pointer. */ 118 void setCPU(FullCPU *cpu_ptr); 119 120 /** Sets the main backwards communication time buffer pointer. */ 121 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr); 122 123 /** Sets pointer to time buffer used to communicate to the next stage. */ 124 void setRenameQueue(TimeBuffer<RenameStruct> *rq_ptr); 125 126 /** Sets pointer to time buffer coming from decode. */ 127 void setDecodeQueue(TimeBuffer<DecodeStruct> *dq_ptr); 128 129 /** Sets pointer to IEW stage. Used only for initialization. */ 130 void setIEWStage(IEW *iew_stage) 131 { iew_ptr = iew_stage; } 132 133 /** Sets pointer to commit stage. Used only for initialization. */ 134 void setCommitStage(Commit *commit_stage) 135 { commit_ptr = commit_stage; } 136 137 private: 138 /** Pointer to IEW stage. Used only for initialization. */ 139 IEW *iew_ptr; 140 141 /** Pointer to commit stage. Used only for initialization. */ 142 Commit *commit_ptr; 143 144 public: 145 /** Initializes variables for the stage. */ 146 void initStage(); 147 148 /** Sets pointer to list of active threads. */ 149 void setActiveThreads(std::list<unsigned> *at_ptr); 150 151 /** Sets pointer to rename maps (per-thread structures). */ 152 void setRenameMap(RenameMap rm_ptr[Impl::MaxThreads]); 153 154 /** Sets pointer to the free list. */ 155 void setFreeList(FreeList *fl_ptr); 156 157 /** Sets pointer to the scoreboard. */ 158 void setScoreboard(Scoreboard *_scoreboard); 159 160 void switchOut(); 161 162 void doSwitchOut(); 163 164 void takeOverFrom(); 165 166 /** Squashes all instructions in a thread. */ 167 void squash(unsigned tid); 168 169 /** Ticks rename, which processes all input signals and attempts to rename 170 * as many instructions as possible. 171 */ 172 void tick(); 173 174 /** Debugging function used to dump history buffer of renamings. */ 175 void dumpHistory(); 176 177 private: 178 /** Determines what to do based on rename's current status. 179 * @param status_change rename() sets this variable if there was a status 180 * change (ie switching from blocking to unblocking). 181 * @param tid Thread id to rename instructions from. 182 */ 183 void rename(bool &status_change, unsigned tid); 184 185 /** Renames instructions for the given thread. Also handles serializing 186 * instructions. 187 */ 188 void renameInsts(unsigned tid); 189 190 /** Inserts unused instructions from a given thread into the skid buffer, 191 * to be renamed once rename unblocks. 192 */ 193 void skidInsert(unsigned tid); 194 195 /** Separates instructions from decode into individual lists of instructions 196 * sorted by thread. 197 */ 198 void sortInsts(); 199 200 /** Returns if all of the skid buffers are empty. */ 201 bool skidsEmpty(); 202 203 /** Updates overall rename status based on all of the threads' statuses. */ 204 void updateStatus(); 205 206 /** Switches rename to blocking, and signals back that rename has become 207 * blocked. 208 * @return Returns true if there is a status change. 209 */ 210 bool block(unsigned tid); 211 212 /** Switches rename to unblocking if the skid buffer is empty, and signals 213 * back that rename has unblocked. 214 * @return Returns true if there is a status change. 215 */ 216 bool unblock(unsigned tid); 217 218 /** Executes actual squash, removing squashed instructions. */ 219 void doSquash(unsigned tid); 220 221 /** Removes a committed instruction's rename history. */ 222 void removeFromHistory(InstSeqNum inst_seq_num, unsigned tid); 223 224 /** Renames the source registers of an instruction. */ 225 inline void renameSrcRegs(DynInstPtr &inst, unsigned tid); 226 227 /** Renames the destination registers of an instruction. */ 228 inline void renameDestRegs(DynInstPtr &inst, unsigned tid); 229 230 /** Calculates the number of free ROB entries for a specific thread. */ 231 inline int calcFreeROBEntries(unsigned tid); 232 233 /** Calculates the number of free IQ entries for a specific thread. */ 234 inline int calcFreeIQEntries(unsigned tid); 235 236 /** Calculates the number of free LSQ entries for a specific thread. */ 237 inline int calcFreeLSQEntries(unsigned tid); 238 239 /** Returns the number of valid instructions coming from decode. */ 240 unsigned validInsts(); 241 242 /** Reads signals telling rename to block/unblock. */ 243 void readStallSignals(unsigned tid); 244 245 /** Checks if any stages are telling rename to block. */ 246 bool checkStall(unsigned tid); 247 248 void readFreeEntries(unsigned tid); 249 250 bool checkSignalsAndUpdate(unsigned tid); 251 252 /** Either serializes on the next instruction available in the InstQueue, 253 * or records that it must serialize on the next instruction to enter 254 * rename. 255 * @param inst_list The list of younger, unprocessed instructions for the 256 * thread that has the serializeAfter instruction. 257 * @param tid The thread id. 258 */ 259 void serializeAfter(InstQueue &inst_list, unsigned tid); 260 261 /** Holds the information for each destination register rename. It holds 262 * the instruction's sequence number, the arch register, the old physical 263 * register for that arch. register, and the new physical register. 264 */ 265 struct RenameHistory { 266 RenameHistory(InstSeqNum _instSeqNum, RegIndex _archReg, 267 PhysRegIndex _newPhysReg, PhysRegIndex _prevPhysReg) 268 : instSeqNum(_instSeqNum), archReg(_archReg), 269 newPhysReg(_newPhysReg), prevPhysReg(_prevPhysReg) 270 { 271 } 272 273 /** The sequence number of the instruction that renamed. */ 274 InstSeqNum instSeqNum; 275 /** The architectural register index that was renamed. */ 276 RegIndex archReg; 277 /** The new physical register that the arch. register is renamed to. */ 278 PhysRegIndex newPhysReg; 279 /** The old physical register that the arch. register was renamed to. */ 280 PhysRegIndex prevPhysReg; 281 }; 282 283 /** A per-thread list of all destination register renames, used to either 284 * undo rename mappings or free old physical registers. 285 */ 286 std::list<RenameHistory> historyBuffer[Impl::MaxThreads]; 287 288 /** Pointer to CPU. */ 289 FullCPU *cpu; 290 291 /** Pointer to main time buffer used for backwards communication. */ 292 TimeBuffer<TimeStruct> *timeBuffer; 293 294 /** Wire to get IEW's output from backwards time buffer. */ 295 typename TimeBuffer<TimeStruct>::wire fromIEW; 296 297 /** Wire to get commit's output from backwards time buffer. */ 298 typename TimeBuffer<TimeStruct>::wire fromCommit; 299 300 /** Wire to write infromation heading to previous stages. */ 301 typename TimeBuffer<TimeStruct>::wire toDecode; 302 303 /** Rename instruction queue. */ 304 TimeBuffer<RenameStruct> *renameQueue; 305 306 /** Wire to write any information heading to IEW. */ 307 typename TimeBuffer<RenameStruct>::wire toIEW; 308 309 /** Decode instruction queue interface. */ 310 TimeBuffer<DecodeStruct> *decodeQueue; 311 312 /** Wire to get decode's output from decode queue. */ 313 typename TimeBuffer<DecodeStruct>::wire fromDecode; 314 315 /** Queue of all instructions coming from decode this cycle. */ 316 InstQueue insts[Impl::MaxThreads]; 317 318 /** Skid buffer between rename and decode. */ 319 InstQueue skidBuffer[Impl::MaxThreads]; 320 321 /** Rename map interface. */ 322 RenameMap *renameMap[Impl::MaxThreads]; 323 324 /** Free list interface. */ 325 FreeList *freeList; 326 327 /** Pointer to the list of active threads. */ 328 std::list<unsigned> *activeThreads; 329 330 /** Pointer to the scoreboard. */ 331 Scoreboard *scoreboard; 332 333 /** Count of instructions in progress that have been sent off to the IQ 334 * and ROB, but are not yet included in their occupancy counts. 335 */ 336 int instsInProgress[Impl::MaxThreads]; 337 338 /** Variable that tracks if decode has written to the time buffer this 339 * cycle. Used to tell CPU if there is activity this cycle. 340 */ 341 bool wroteToTimeBuffer; 342 343 /** Structures whose free entries impact the amount of instructions that 344 * can be renamed. 345 */ 346 struct FreeEntries { 347 unsigned iqEntries; 348 unsigned lsqEntries; 349 unsigned robEntries; 350 }; 351 352 /** Per-thread tracking of the number of free entries of back-end 353 * structures. 354 */ 355 FreeEntries freeEntries[Impl::MaxThreads]; 356 357 /** Records if the ROB is empty. In SMT mode the ROB may be dynamically 358 * partitioned between threads, so the ROB must tell rename when it is 359 * empty. 360 */ 361 bool emptyROB[Impl::MaxThreads]; 362 363 /** Source of possible stalls. */ 364 struct Stalls { 365 bool iew; 366 bool commit; 367 }; 368 369 /** Tracks which stages are telling decode to stall. */ 370 Stalls stalls[Impl::MaxThreads]; 371 372 /** The serialize instruction that rename has stalled on. */ 373 DynInstPtr serializeInst[Impl::MaxThreads]; 374 375 /** Records if rename needs to serialize on the next instruction for any 376 * thread. 377 */ 378 bool serializeOnNextInst[Impl::MaxThreads]; 379 380 /** Delay between iew and rename, in ticks. */ 381 int iewToRenameDelay; 382 383 /** Delay between decode and rename, in ticks. */ 384 int decodeToRenameDelay; 385 386 /** Delay between commit and rename, in ticks. */ 387 unsigned commitToRenameDelay; 388 389 /** Rename width, in instructions. */ 390 unsigned renameWidth; 391 392 /** Commit width, in instructions. Used so rename knows how many 393 * instructions might have freed registers in the previous cycle. 394 */ 395 unsigned commitWidth; 396 397 /** The index of the instruction in the time buffer to IEW that rename is 398 * currently using. 399 */ 400 unsigned toIEWIndex; 401 402 /** Whether or not rename needs to block this cycle. */ 403 bool blockThisCycle; 404 405 /** The number of threads active in rename. */ 406 unsigned numThreads; 407 408 /** The maximum skid buffer size. */ 409 unsigned skidBufferMax; 410 411 /** Enum to record the source of a structure full stall. Can come from 412 * either ROB, IQ, LSQ, and it is priortized in that order. 413 */ 414 enum FullSource { 415 ROB, 416 IQ, 417 LSQ, 418 NONE 419 }; 420 421 /** Function used to increment the stat that corresponds to the source of 422 * the stall. 423 */ 424 inline void incrFullStat(const FullSource &source); 425 426 /** Stat for total number of cycles spent squashing. */ 427 Stats::Scalar<> renameSquashCycles; 428 /** Stat for total number of cycles spent idle. */ 429 Stats::Scalar<> renameIdleCycles; 430 /** Stat for total number of cycles spent blocking. */ 431 Stats::Scalar<> renameBlockCycles; 432 /** Stat for total number of cycles spent stalling for a serializing inst. */ 433 Stats::Scalar<> renameSerializeStallCycles; 434 /** Stat for total number of cycles spent running normally. */ 435 Stats::Scalar<> renameRunCycles; 436 /** Stat for total number of cycles spent unblocking. */ 437 Stats::Scalar<> renameUnblockCycles; 438 /** Stat for total number of renamed instructions. */ 439 Stats::Scalar<> renameRenamedInsts; 440 /** Stat for total number of squashed instructions that rename discards. */ 441 Stats::Scalar<> renameSquashedInsts; 442 /** Stat for total number of times that the ROB starts a stall in rename. */ 443 Stats::Scalar<> renameROBFullEvents; 444 /** Stat for total number of times that the IQ starts a stall in rename. */ 445 Stats::Scalar<> renameIQFullEvents; 446 /** Stat for total number of times that the LSQ starts a stall in rename. */ 447 Stats::Scalar<> renameLSQFullEvents; 448 /** Stat for total number of times that rename runs out of free registers 449 * to use to rename. */ 450 Stats::Scalar<> renameFullRegistersEvents; 451 /** Stat for total number of renamed destination registers. */ 452 Stats::Scalar<> renameRenamedOperands; 453 /** Stat for total number of source register rename lookups. */ 454 Stats::Scalar<> renameRenameLookups; 455 /** Stat for total number of committed renaming mappings. */ 456 Stats::Scalar<> renameCommittedMaps; 457 /** Stat for total number of mappings that were undone due to a squash. */ 458 Stats::Scalar<> renameUndoneMaps; 459 Stats::Scalar<> renamedSerializing; 460 Stats::Scalar<> renamedTempSerializing; 461 Stats::Scalar<> renameSkidInsts; 462}; 463 464#endif // __CPU_O3_RENAME_HH__ 465