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