src/cpu/o3/iew.hh

   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_IEW_HH__
  32 #define __CPU_O3_IEW_HH__
  33
  34 #include "config/full_system.hh"
  35
  36 #include <queue>
  37
  38 #include "base/statistics.hh"
  39 #include "base/timebuf.hh"
  40 #include "cpu/o3/comm.hh"
  41 #include "cpu/o3/scoreboard.hh"
  42 #include "cpu/o3/lsq.hh"
  43
  44 class FUPool;
  45
  46 /**
  47  * DefaultIEW handles both single threaded and SMT IEW
  48  * (issue/execute/writeback).  It handles the dispatching of
  49  * instructions to the LSQ/IQ as part of the issue stage, and has the
  50  * IQ try to issue instructions each cycle. The execute latency is
  51  * actually tied into the issue latency to allow the IQ to be able to
  52  * do back-to-back scheduling without having to speculatively schedule
  53  * instructions. This happens by having the IQ have access to the
  54  * functional units, and the IQ gets the execution latencies from the
  55  * FUs when it issues instructions. Instructions reach the execute
  56  * stage on the last cycle of their execution, which is when the IQ
  57  * knows to wake up any dependent instructions, allowing back to back
  58  * scheduling. The execute portion of IEW separates memory
  59  * instructions from non-memory instructions, either telling the LSQ
  60  * to execute the instruction, or executing the instruction directly.
  61  * The writeback portion of IEW completes the instructions by waking
  62  * up any dependents, and marking the register ready on the
  63  * scoreboard.
  64  */
  65 template<class Impl>
  66 class DefaultIEW
  67 {
  68   private:
  69     //Typedefs from Impl
  70     typedef typename Impl::CPUPol CPUPol;
  71     typedef typename Impl::DynInstPtr DynInstPtr;
  72     typedef typename Impl::O3CPU O3CPU;
  73     typedef typename Impl::Params Params;
  74
  75     typedef typename CPUPol::IQ IQ;
  76     typedef typename CPUPol::RenameMap RenameMap;
  77     typedef typename CPUPol::LSQ LSQ;
  78
  79     typedef typename CPUPol::TimeStruct TimeStruct;
  80     typedef typename CPUPol::IEWStruct IEWStruct;
  81     typedef typename CPUPol::RenameStruct RenameStruct;
  82     typedef typename CPUPol::IssueStruct IssueStruct;
  83
  84     friend class Impl::O3CPU;
  85     friend class CPUPol::IQ;
  86
  87   public:
  88     /** Overall IEW stage status. Used to determine if the CPU can
  89      * deschedule itself due to a lack of activity.
  90      */
  91     enum Status {
  92         Active,
  93         Inactive
  94     };
  95
  96     /** Status for Issue, Execute, and Writeback stages. */
  97     enum StageStatus {
  98         Running,
  99         Blocked,
 100         Idle,
 101         StartSquash,
 102         Squashing,
 103         Unblocking
 104     };
 105
 106   private:
 107     /** Overall stage status. */
 108     Status _status;
 109     /** Dispatch status. */
 110     StageStatus dispatchStatus[Impl::MaxThreads];
 111     /** Execute status. */
 112     StageStatus exeStatus;
 113     /** Writeback status. */
 114     StageStatus wbStatus;
 115
 116   public:
 117     /** Constructs a DefaultIEW with the given parameters. */
 118     DefaultIEW(Params *params);
 119
 120     /** Returns the name of the DefaultIEW stage. */
 121     std::string name() const;
 122
 123     /** Registers statistics. */
 124     void regStats();
 125
 126     /** Initializes stage; sends back the number of free IQ and LSQ entries. */
 127     void initStage();
 128
 129     /** Returns the dcache port. */
 130     Port *getDcachePort() { return ldstQueue.getDcachePort(); }
 131
 132     /** Sets CPU pointer for IEW, IQ, and LSQ. */
 133     void setCPU(O3CPU *cpu_ptr);
 134
 135     /** Sets main time buffer used for backwards communication. */
 136     void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
 137
 138     /** Sets time buffer for getting instructions coming from rename. */
 139     void setRenameQueue(TimeBuffer<RenameStruct> *rq_ptr);
 140
 141     /** Sets time buffer to pass on instructions to commit. */
 142     void setIEWQueue(TimeBuffer<IEWStruct> *iq_ptr);
 143
 144     /** Sets pointer to list of active threads. */
 145     void setActiveThreads(std::list<unsigned> *at_ptr);
 146
 147     /** Sets pointer to the scoreboard. */
 148     void setScoreboard(Scoreboard *sb_ptr);
 149
 150     /** Drains IEW stage. */
 151     bool drain();
 152
 153     /** Resumes execution after a drain. */
 154     void resume();
 155
 156     /** Completes switch out of IEW stage. */
 157     void switchOut();
 158
 159     /** Takes over from another CPU's thread. */
 160     void takeOverFrom();
 161
 162     /** Returns if IEW is switched out. */
 163     bool isSwitchedOut() { return switchedOut; }
 164
 165     /** Squashes instructions in IEW for a specific thread. */
 166     void squash(unsigned tid);
 167
 168     /** Wakes all dependents of a completed instruction. */
 169     void wakeDependents(DynInstPtr &inst);
 170
 171     /** Tells memory dependence unit that a memory instruction needs to be
 172      * rescheduled. It will re-execute once replayMemInst() is called.
 173      */
 174     void rescheduleMemInst(DynInstPtr &inst);
 175
 176     /** Re-executes all rescheduled memory instructions. */
 177     void replayMemInst(DynInstPtr &inst);
 178
 179     /** Sends an instruction to commit through the time buffer. */
 180     void instToCommit(DynInstPtr &inst);
 181
 182     /** Inserts unused instructions of a thread into the skid buffer. */
 183     void skidInsert(unsigned tid);
 184
 185     /** Returns the max of the number of entries in all of the skid buffers. */
 186     int skidCount();
 187
 188     /** Returns if all of the skid buffers are empty. */
 189     bool skidsEmpty();
 190
 191     /** Updates overall IEW status based on all of the stages' statuses. */
 192     void updateStatus();
 193
 194     /** Resets entries of the IQ and the LSQ. */
 195     void resetEntries();
 196
 197     /** Tells the CPU to wakeup if it has descheduled itself due to no
 198      * activity. Used mainly by the LdWritebackEvent.
 199      */
 200     void wakeCPU();
 201
 202     /** Reports to the CPU that there is activity this cycle. */
 203     void activityThisCycle();
 204
 205     /** Tells CPU that the IEW stage is active and running. */
 206     inline void activateStage();
 207
 208     /** Tells CPU that the IEW stage is inactive and idle. */
 209     inline void deactivateStage();
 210
 211     /** Returns if the LSQ has any stores to writeback. */
 212     bool hasStoresToWB() { return ldstQueue.hasStoresToWB(); }
 213
 214     void incrWb(InstSeqNum &sn)
 215     {
 216         if (++wbOutstanding == wbMax)
 217             ableToIssue = false;
 218         DPRINTF(IEW, "wbOutstanding: %i\n", wbOutstanding);
 219         assert(wbOutstanding <= wbMax);
 220 #ifdef DEBUG
 221         wbList.insert(sn);
 222 #endif
 223     }
 224
 225     void decrWb(InstSeqNum &sn)
 226     {
 227         if (wbOutstanding-- == wbMax)
 228             ableToIssue = true;
 229         DPRINTF(IEW, "wbOutstanding: %i\n", wbOutstanding);
 230         assert(wbOutstanding >= 0);
 231 #ifdef DEBUG
 232         assert(wbList.find(sn) != wbList.end());
 233         wbList.erase(sn);
 234 #endif
 235     }
 236
 237 #ifdef DEBUG
 238     std::set<InstSeqNum> wbList;
 239
 240     void dumpWb()
 241     {
 242         std::set<InstSeqNum>::iterator wb_it = wbList.begin();
 243         while (wb_it != wbList.end()) {
 244             cprintf("[sn:%lli]\n",
 245                     (*wb_it));
 246             wb_it++;
 247         }
 248     }
 249 #endif
 250
 251     bool canIssue() { return ableToIssue; }
 252
 253     bool ableToIssue;
 254
 255   private:
 256     /** Sends commit proper information for a squash due to a branch
 257      * mispredict.
 258      */
 259     void squashDueToBranch(DynInstPtr &inst, unsigned thread_id);
 260
 261     /** Sends commit proper information for a squash due to a memory order
 262      * violation.
 263      */
 264     void squashDueToMemOrder(DynInstPtr &inst, unsigned thread_id);
 265
 266     /** Sends commit proper information for a squash due to memory becoming
 267      * blocked (younger issued instructions must be retried).
 268      */
 269     void squashDueToMemBlocked(DynInstPtr &inst, unsigned thread_id);
 270
 271     /** Sets Dispatch to blocked, and signals back to other stages to block. */
 272     void block(unsigned thread_id);
 273
 274     /** Unblocks Dispatch if the skid buffer is empty, and signals back to
 275      * other stages to unblock.
 276      */
 277     void unblock(unsigned thread_id);
 278
 279     /** Determines proper actions to take given Dispatch's status. */
 280     void dispatch(unsigned tid);
 281
 282     /** Dispatches instructions to IQ and LSQ. */
 283     void dispatchInsts(unsigned tid);
 284
 285     /** Executes instructions. In the case of memory operations, it informs the
 286      * LSQ to execute the instructions. Also handles any redirects that occur
 287      * due to the executed instructions.
 288      */
 289     void executeInsts();
 290
 291     /** Writebacks instructions. In our model, the instruction's execute()
 292      * function atomically reads registers, executes, and writes registers.
 293      * Thus this writeback only wakes up dependent instructions, and informs
 294      * the scoreboard of registers becoming ready.
 295      */
 296     void writebackInsts();
 297
 298     /** Returns the number of valid, non-squashed instructions coming from
 299      * rename to dispatch.
 300      */
 301     unsigned validInstsFromRename();
 302
 303     /** Reads the stall signals. */
 304     void readStallSignals(unsigned tid);
 305
 306     /** Checks if any of the stall conditions are currently true. */
 307     bool checkStall(unsigned tid);
 308
 309     /** Processes inputs and changes state accordingly. */
 310     void checkSignalsAndUpdate(unsigned tid);
 311
 312     /** Removes instructions from rename from a thread's instruction list. */
 313     void emptyRenameInsts(unsigned tid);
 314
 315     /** Sorts instructions coming from rename into lists separated by thread. */
 316     void sortInsts();
 317
 318   public:
 319     /** Ticks IEW stage, causing Dispatch, the IQ, the LSQ, Execute, and
 320      * Writeback to run for one cycle.
 321      */
 322     void tick();
 323
 324   private:
 325     /** Updates execution stats based on the instruction. */
 326     void updateExeInstStats(DynInstPtr &inst);
 327
 328     /** Pointer to main time buffer used for backwards communication. */
 329     TimeBuffer<TimeStruct> *timeBuffer;
 330
 331     /** Wire to write information heading to previous stages. */
 332     typename TimeBuffer<TimeStruct>::wire toFetch;
 333
 334     /** Wire to get commit's output from backwards time buffer. */
 335     typename TimeBuffer<TimeStruct>::wire fromCommit;
 336
 337     /** Wire to write information heading to previous stages. */
 338     typename TimeBuffer<TimeStruct>::wire toRename;
 339
 340     /** Rename instruction queue interface. */
 341     TimeBuffer<RenameStruct> *renameQueue;
 342
 343     /** Wire to get rename's output from rename queue. */
 344     typename TimeBuffer<RenameStruct>::wire fromRename;
 345
 346     /** Issue stage queue. */
 347     TimeBuffer<IssueStruct> issueToExecQueue;
 348
 349     /** Wire to read information from the issue stage time queue. */
 350     typename TimeBuffer<IssueStruct>::wire fromIssue;
 351
 352     /**
 353      * IEW stage time buffer.  Holds ROB indices of instructions that
 354      * can be marked as completed.
 355      */
 356     TimeBuffer<IEWStruct> *iewQueue;
 357
 358     /** Wire to write infromation heading to commit. */
 359     typename TimeBuffer<IEWStruct>::wire toCommit;
 360
 361     /** Queue of all instructions coming from rename this cycle. */
 362     std::queue<DynInstPtr> insts[Impl::MaxThreads];
 363
 364     /** Skid buffer between rename and IEW. */
 365     std::queue<DynInstPtr> skidBuffer[Impl::MaxThreads];
 366
 367     /** Scoreboard pointer. */
 368     Scoreboard* scoreboard;
 369
 370   public:
 371     /** Instruction queue. */
 372     IQ instQueue;
 373
 374     /** Load / store queue. */
 375     LSQ ldstQueue;
 376
 377     /** Pointer to the functional unit pool. */
 378     FUPool *fuPool;
 379
 380   private:
 381     /** CPU pointer. */
 382     O3CPU *cpu;
 383
 384     /** Records if IEW has written to the time buffer this cycle, so that the
 385      * CPU can deschedule itself if there is no activity.
 386      */
 387     bool wroteToTimeBuffer;
 388
 389     /** Source of possible stalls. */
 390     struct Stalls {
 391         bool commit;
 392     };
 393
 394     /** Stages that are telling IEW to stall. */
 395     Stalls stalls[Impl::MaxThreads];
 396
 397     /** Debug function to print instructions that are issued this cycle. */
 398     void printAvailableInsts();
 399
 400   public:
 401     /** Records if the LSQ needs to be updated on the next cycle, so that
 402      * IEW knows if there will be activity on the next cycle.
 403      */
 404     bool updateLSQNextCycle;
 405
 406   private:
 407     /** Records if there is a fetch redirect on this cycle for each thread. */
 408     bool fetchRedirect[Impl::MaxThreads];
 409
 410     /** Keeps track of the last valid branch delay slot instss for threads */
 411     InstSeqNum bdelayDoneSeqNum[Impl::MaxThreads];
 412
 413     /** Used to track if all instructions have been dispatched this cycle.
 414      * If they have not, then blocking must have occurred, and the instructions
 415      * would already be added to the skid buffer.
 416      * @todo: Fix this hack.
 417      */
 418     bool dispatchedAllInsts;
 419
 420     /** Records if the queues have been changed (inserted or issued insts),
 421      * so that IEW knows to broadcast the updated amount of free entries.
 422      */
 423     bool updatedQueues;
 424
 425     /** Commit to IEW delay, in ticks. */
 426     unsigned commitToIEWDelay;
 427
 428     /** Rename to IEW delay, in ticks. */
 429     unsigned renameToIEWDelay;
 430
 431     /**
 432      * Issue to execute delay, in ticks.  What this actually represents is
 433      * the amount of time it takes for an instruction to wake up, be
 434      * scheduled, and sent to a FU for execution.
 435      */
 436     unsigned issueToExecuteDelay;
 437
 438     /** Width of dispatch, in instructions. */
 439     unsigned dispatchWidth;
 440
 441     /** Width of issue, in instructions. */
 442     unsigned issueWidth;
 443
 444     /** Index into queue of instructions being written back. */
 445     unsigned wbNumInst;
 446
 447     /** Cycle number within the queue of instructions being written back.
 448      * Used in case there are too many instructions writing back at the current
 449      * cycle and writesbacks need to be scheduled for the future. See comments
 450      * in instToCommit().
 451      */
 452     unsigned wbCycle;
 453
 454     /** Number of instructions in flight that will writeback. */
 455
 456     /** Number of instructions in flight that will writeback. */
 457     int wbOutstanding;
 458
 459     /** Writeback width. */
 460     unsigned wbWidth;
 461
 462     /** Writeback width * writeback depth, where writeback depth is
 463      * the number of cycles of writing back instructions that can be
 464      * buffered. */
 465     unsigned wbMax;
 466
 467     /** Number of active threads. */
 468     unsigned numThreads;
 469
 470     /** Pointer to list of active threads. */
 471     std::list<unsigned> *activeThreads;
 472
 473     /** Maximum size of the skid buffer. */
 474     unsigned skidBufferMax;
 475
 476     /** Is this stage switched out. */
 477     bool switchedOut;
 478
 479     /** Stat for total number of idle cycles. */
 480     Stats::Scalar<> iewIdleCycles;
 481     /** Stat for total number of squashing cycles. */
 482     Stats::Scalar<> iewSquashCycles;
 483     /** Stat for total number of blocking cycles. */
 484     Stats::Scalar<> iewBlockCycles;
 485     /** Stat for total number of unblocking cycles. */
 486     Stats::Scalar<> iewUnblockCycles;
 487     /** Stat for total number of instructions dispatched. */
 488     Stats::Scalar<> iewDispatchedInsts;
 489     /** Stat for total number of squashed instructions dispatch skips. */
 490     Stats::Scalar<> iewDispSquashedInsts;
 491     /** Stat for total number of dispatched load instructions. */
 492     Stats::Scalar<> iewDispLoadInsts;
 493     /** Stat for total number of dispatched store instructions. */
 494     Stats::Scalar<> iewDispStoreInsts;
 495     /** Stat for total number of dispatched non speculative instructions. */
 496     Stats::Scalar<> iewDispNonSpecInsts;
 497     /** Stat for number of times the IQ becomes full. */
 498     Stats::Scalar<> iewIQFullEvents;
 499     /** Stat for number of times the LSQ becomes full. */
 500     Stats::Scalar<> iewLSQFullEvents;
 501     /** Stat for total number of memory ordering violation events. */
 502     Stats::Scalar<> memOrderViolationEvents;
 503     /** Stat for total number of incorrect predicted taken branches. */
 504     Stats::Scalar<> predictedTakenIncorrect;
 505     /** Stat for total number of incorrect predicted not taken branches. */
 506     Stats::Scalar<> predictedNotTakenIncorrect;
 507     /** Stat for total number of mispredicted branches detected at execute. */
 508     Stats::Formula branchMispredicts;
 509
 510     /** Stat for total number of executed instructions. */
 511     Stats::Scalar<> iewExecutedInsts;
 512     /** Stat for total number of executed load instructions. */
 513     Stats::Vector<> iewExecLoadInsts;
 514     /** Stat for total number of executed store instructions. */
 515 //    Stats::Scalar<> iewExecStoreInsts;
 516     /** Stat for total number of squashed instructions skipped at execute. */
 517     Stats::Scalar<> iewExecSquashedInsts;
 518     /** Number of executed software prefetches. */
 519     Stats::Vector<> iewExecutedSwp;
 520     /** Number of executed nops. */
 521     Stats::Vector<> iewExecutedNop;
 522     /** Number of executed meomory references. */
 523     Stats::Vector<> iewExecutedRefs;
 524     /** Number of executed branches. */
 525     Stats::Vector<> iewExecutedBranches;
 526     /** Number of executed store instructions. */
 527     Stats::Formula iewExecStoreInsts;
 528     /** Number of instructions executed per cycle. */
 529     Stats::Formula iewExecRate;
 530
 531     /** Number of instructions sent to commit. */
 532     Stats::Vector<> iewInstsToCommit;
 533     /** Number of instructions that writeback. */
 534     Stats::Vector<> writebackCount;
 535     /** Number of instructions that wake consumers. */
 536     Stats::Vector<> producerInst;
 537     /** Number of instructions that wake up from producers. */
 538     Stats::Vector<> consumerInst;
 539     /** Number of instructions that were delayed in writing back due
 540      * to resource contention.
 541      */
 542     Stats::Vector<> wbPenalized;
 543     /** Number of instructions per cycle written back. */
 544     Stats::Formula wbRate;
 545     /** Average number of woken instructions per writeback. */
 546     Stats::Formula wbFanout;
 547     /** Number of instructions per cycle delayed in writing back . */
 548     Stats::Formula wbPenalizedRate;
 549 };
 550
 551 #endif // __CPU_O3_IEW_HH__