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