summaryrefslogtreecommitdiff
path: root/src/cpu/o3/inst_queue.hh
blob: d0f503977c4b67d941fc2e00e06d63603925033e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Kevin Lim
 */

#ifndef __CPU_O3_INST_QUEUE_HH__
#define __CPU_O3_INST_QUEUE_HH__

#include <list>
#include <map>
#include <queue>
#include <vector>

#include "base/statistics.hh"
#include "base/timebuf.hh"
#include "cpu/inst_seq.hh"
#include "cpu/o3/dep_graph.hh"
#include "cpu/op_class.hh"
#include "sim/host.hh"

class FUPool;
class MemInterface;

/**
 * A standard instruction queue class.  It holds ready instructions, in
 * order, in seperate priority queues to facilitate the scheduling of
 * instructions.  The IQ uses a separate linked list to track dependencies.
 * Similar to the rename map and the free list, it expects that
 * floating point registers have their indices start after the integer
 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
 * and 96-191 are fp).  This remains true even for both logical and
 * physical register indices. The IQ depends on the memory dependence unit to
 * track when memory operations are ready in terms of ordering; register
 * dependencies are tracked normally. Right now the IQ also handles the
 * execution timing; this is mainly to allow back-to-back scheduling without
 * requiring IEW to be able to peek into the IQ. At the end of the execution
 * latency, the instruction is put into the queue to execute, where it will
 * have the execute() function called on it.
 * @todo: Make IQ able to handle multiple FU pools.
 */
template <class Impl>
class InstructionQueue
{
  public:
    //Typedefs from the Impl.
    typedef typename Impl::O3CPU O3CPU;
    typedef typename Impl::DynInstPtr DynInstPtr;
    typedef typename Impl::Params Params;

    typedef typename Impl::CPUPol::IEW IEW;
    typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
    typedef typename Impl::CPUPol::IssueStruct IssueStruct;
    typedef typename Impl::CPUPol::TimeStruct TimeStruct;

    // Typedef of iterator through the list of instructions.
    typedef typename std::list<DynInstPtr>::iterator ListIt;

    friend class Impl::O3CPU;

    /** FU completion event class. */
    class FUCompletion : public Event {
      private:
        /** Executing instruction. */
        DynInstPtr inst;

        /** Index of the FU used for executing. */
        int fuIdx;

        /** Pointer back to the instruction queue. */
        InstructionQueue<Impl> *iqPtr;

        /** Should the FU be added to the list to be freed upon
         * completing this event.
         */
        bool freeFU;

      public:
        /** Construct a FU completion event. */
        FUCompletion(DynInstPtr &_inst, int fu_idx,
                     InstructionQueue<Impl> *iq_ptr);

        virtual void process();
        virtual const char *description() const;
        void setFreeFU() { freeFU = true; }
    };

    /** Constructs an IQ. */
    InstructionQueue(O3CPU *cpu_ptr, IEW *iew_ptr, Params *params);

    /** Destructs the IQ. */
    ~InstructionQueue();

    /** Returns the name of the IQ. */
    std::string name() const;

    /** Registers statistics. */
    void regStats();

    /** Resets all instruction queue state. */
    void resetState();

    /** Sets active threads list. */
    void setActiveThreads(std::list<unsigned> *at_ptr);

    /** Sets the timer buffer between issue and execute. */
    void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);

    /** Sets the global time buffer. */
    void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);

    /** Switches out the instruction queue. */
    void switchOut();

    /** Takes over execution from another CPU's thread. */
    void takeOverFrom();

    /** Returns if the IQ is switched out. */
    bool isSwitchedOut() { return switchedOut; }

    /** Number of entries needed for given amount of threads. */
    int entryAmount(int num_threads);

    /** Resets max entries for all threads. */
    void resetEntries();

    /** Returns total number of free entries. */
    unsigned numFreeEntries();

    /** Returns number of free entries for a thread. */
    unsigned numFreeEntries(unsigned tid);

    /** Returns whether or not the IQ is full. */
    bool isFull();

    /** Returns whether or not the IQ is full for a specific thread. */
    bool isFull(unsigned tid);

    /** Returns if there are any ready instructions in the IQ. */
    bool hasReadyInsts();

    /** Inserts a new instruction into the IQ. */
    void insert(DynInstPtr &new_inst);

    /** Inserts a new, non-speculative instruction into the IQ. */
    void insertNonSpec(DynInstPtr &new_inst);

    /** Inserts a memory or write barrier into the IQ to make sure
     *  loads and stores are ordered properly.
     */
    void insertBarrier(DynInstPtr &barr_inst);

    /** Returns the oldest scheduled instruction, and removes it from
     * the list of instructions waiting to execute.
     */
    DynInstPtr getInstToExecute();

    /**
     * Records the instruction as the producer of a register without
     * adding it to the rest of the IQ.
     */
    void recordProducer(DynInstPtr &inst)
    { addToProducers(inst); }

    /** Process FU completion event. */
    void processFUCompletion(DynInstPtr &inst, int fu_idx);

    /**
     * Schedules ready instructions, adding the ready ones (oldest first) to
     * the queue to execute.
     */
    void scheduleReadyInsts();

    /** Schedules a single specific non-speculative instruction. */
    void scheduleNonSpec(const InstSeqNum &inst);

    /**
     * Commits all instructions up to and including the given sequence number,
     * for a specific thread.
     */
    void commit(const InstSeqNum &inst, unsigned tid = 0);

    /** Wakes all dependents of a completed instruction. */
    int wakeDependents(DynInstPtr &completed_inst);

    /** Adds a ready memory instruction to the ready list. */
    void addReadyMemInst(DynInstPtr &ready_inst);

    /**
     * Reschedules a memory instruction. It will be ready to issue once
     * replayMemInst() is called.
     */
    void rescheduleMemInst(DynInstPtr &resched_inst);

    /** Replays a memory instruction. It must be rescheduled first. */
    void replayMemInst(DynInstPtr &replay_inst);

    /** Completes a memory operation. */
    void completeMemInst(DynInstPtr &completed_inst);

    /** Indicates an ordering violation between a store and a load. */
    void violation(DynInstPtr &store, DynInstPtr &faulting_load);

    /**
     * Squashes instructions for a thread. Squashing information is obtained
     * from the time buffer.
     */
    void squash(unsigned tid);

    /** Returns the number of used entries for a thread. */
    unsigned getCount(unsigned tid) { return count[tid]; };

    /** Debug function to print all instructions. */
    void printInsts();

  private:
    /** Does the actual squashing. */
    void doSquash(unsigned tid);

    /////////////////////////
    // Various pointers
    /////////////////////////

    /** Pointer to the CPU. */
    O3CPU *cpu;

    /** Cache interface. */
    MemInterface *dcacheInterface;

    /** Pointer to IEW stage. */
    IEW *iewStage;

    /** The memory dependence unit, which tracks/predicts memory dependences
     *  between instructions.
     */
    MemDepUnit memDepUnit[Impl::MaxThreads];

    /** The queue to the execute stage.  Issued instructions will be written
     *  into it.
     */
    TimeBuffer<IssueStruct> *issueToExecuteQueue;

    /** The backwards time buffer. */
    TimeBuffer<TimeStruct> *timeBuffer;

    /** Wire to read information from timebuffer. */
    typename TimeBuffer<TimeStruct>::wire fromCommit;

    /** Function unit pool. */
    FUPool *fuPool;

    //////////////////////////////////////
    // Instruction lists, ready queues, and ordering
    //////////////////////////////////////

    /** List of all the instructions in the IQ (some of which may be issued). */
    std::list<DynInstPtr> instList[Impl::MaxThreads];

    /** List of instructions that are ready to be executed. */
    std::list<DynInstPtr> instsToExecute;

    /**
     * Struct for comparing entries to be added to the priority queue.
     * This gives reverse ordering to the instructions in terms of
     * sequence numbers: the instructions with smaller sequence
     * numbers (and hence are older) will be at the top of the
     * priority queue.
     */
    struct pqCompare {
        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
        {
            return lhs->seqNum > rhs->seqNum;
        }
    };

    typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
    ReadyInstQueue;

    /** List of ready instructions, per op class.  They are separated by op
     *  class to allow for easy mapping to FUs.
     */
    ReadyInstQueue readyInsts[Num_OpClasses];

    /** List of non-speculative instructions that will be scheduled
     *  once the IQ gets a signal from commit.  While it's redundant to
     *  have the key be a part of the value (the sequence number is stored
     *  inside of DynInst), when these instructions are woken up only
     *  the sequence number will be available.  Thus it is most efficient to be
     *  able to search by the sequence number alone.
     */
    std::map<InstSeqNum, DynInstPtr> nonSpecInsts;

    typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;

    /** Entry for the list age ordering by op class. */
    struct ListOrderEntry {
        OpClass queueType;
        InstSeqNum oldestInst;
    };

    /** List that contains the age order of the oldest instruction of each
     *  ready queue.  Used to select the oldest instruction available
     *  among op classes.
     *  @todo: Might be better to just move these entries around instead
     *  of creating new ones every time the position changes due to an
     *  instruction issuing.  Not sure std::list supports this.
     */
    std::list<ListOrderEntry> listOrder;

    typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;

    /** Tracks if each ready queue is on the age order list. */
    bool queueOnList[Num_OpClasses];

    /** Iterators of each ready queue.  Points to their spot in the age order
     *  list.
     */
    ListOrderIt readyIt[Num_OpClasses];

    /** Add an op class to the age order list. */
    void addToOrderList(OpClass op_class);

    /**
     * Called when the oldest instruction has been removed from a ready queue;
     * this places that ready queue into the proper spot in the age order list.
     */
    void moveToYoungerInst(ListOrderIt age_order_it);

    DependencyGraph<DynInstPtr> dependGraph;

    //////////////////////////////////////
    // Various parameters
    //////////////////////////////////////

    /** IQ Resource Sharing Policy */
    enum IQPolicy {
        Dynamic,
        Partitioned,
        Threshold
    };

    /** IQ sharing policy for SMT. */
    IQPolicy iqPolicy;

    /** Number of Total Threads*/
    unsigned numThreads;

    /** Pointer to list of active threads. */
    std::list<unsigned> *activeThreads;

    /** Per Thread IQ count */
    unsigned count[Impl::MaxThreads];

    /** Max IQ Entries Per Thread */
    unsigned maxEntries[Impl::MaxThreads];

    /** Number of free IQ entries left. */
    unsigned freeEntries;

    /** The number of entries in the instruction queue. */
    unsigned numEntries;

    /** The total number of instructions that can be issued in one cycle. */
    unsigned totalWidth;

    /** The number of physical registers in the CPU. */
    unsigned numPhysRegs;

    /** The number of physical integer registers in the CPU. */
    unsigned numPhysIntRegs;

    /** The number of floating point registers in the CPU. */
    unsigned numPhysFloatRegs;

    /** Delay between commit stage and the IQ.
     *  @todo: Make there be a distinction between the delays within IEW.
     */
    unsigned commitToIEWDelay;

    /** Is the IQ switched out. */
    bool switchedOut;

    /** The sequence number of the squashed instruction. */
    InstSeqNum squashedSeqNum[Impl::MaxThreads];

    /** A cache of the recently woken registers.  It is 1 if the register
     *  has been woken up recently, and 0 if the register has been added
     *  to the dependency graph and has not yet received its value.  It
     *  is basically a secondary scoreboard, and should pretty much mirror
     *  the scoreboard that exists in the rename map.
     */
    std::vector<bool> regScoreboard;

    /** Adds an instruction to the dependency graph, as a consumer. */
    bool addToDependents(DynInstPtr &new_inst);

    /** Adds an instruction to the dependency graph, as a producer. */
    void addToProducers(DynInstPtr &new_inst);

    /** Moves an instruction to the ready queue if it is ready. */
    void addIfReady(DynInstPtr &inst);

    /** Debugging function to count how many entries are in the IQ.  It does
     *  a linear walk through the instructions, so do not call this function
     *  during normal execution.
     */
    int countInsts();

    /** Debugging function to dump all the list sizes, as well as print
     *  out the list of nonspeculative instructions.  Should not be used
     *  in any other capacity, but it has no harmful sideaffects.
     */
    void dumpLists();

    /** Debugging function to dump out all instructions that are in the
     *  IQ.
     */
    void dumpInsts();

    /** Stat for number of instructions added. */
    Stats::Scalar<> iqInstsAdded;
    /** Stat for number of non-speculative instructions added. */
    Stats::Scalar<> iqNonSpecInstsAdded;

    Stats::Scalar<> iqInstsIssued;
    /** Stat for number of integer instructions issued. */
    Stats::Scalar<> iqIntInstsIssued;
    /** Stat for number of floating point instructions issued. */
    Stats::Scalar<> iqFloatInstsIssued;
    /** Stat for number of branch instructions issued. */
    Stats::Scalar<> iqBranchInstsIssued;
    /** Stat for number of memory instructions issued. */
    Stats::Scalar<> iqMemInstsIssued;
    /** Stat for number of miscellaneous instructions issued. */
    Stats::Scalar<> iqMiscInstsIssued;
    /** Stat for number of squashed instructions that were ready to issue. */
    Stats::Scalar<> iqSquashedInstsIssued;
    /** Stat for number of squashed instructions examined when squashing. */
    Stats::Scalar<> iqSquashedInstsExamined;
    /** Stat for number of squashed instruction operands examined when
     * squashing.
     */
    Stats::Scalar<> iqSquashedOperandsExamined;
    /** Stat for number of non-speculative instructions removed due to a squash.
     */
    Stats::Scalar<> iqSquashedNonSpecRemoved;
    // Also include number of instructions rescheduled and replayed.

    /** Distribution of number of instructions in the queue.
     * @todo: Need to create struct to track the entry time for each
     * instruction. */
//    Stats::VectorDistribution<> queueResDist;
    /** Distribution of the number of instructions issued. */
    Stats::Distribution<> numIssuedDist;
    /** Distribution of the cycles it takes to issue an instruction.
     * @todo: Need to create struct to track the ready time for each
     * instruction. */
//    Stats::VectorDistribution<> issueDelayDist;

    /** Number of times an instruction could not be issued because a
     * FU was busy.
     */
    Stats::Vector<> statFuBusy;
//    Stats::Vector<> dist_unissued;
    /** Stat for total number issued for each instruction type. */
    Stats::Vector2d<> statIssuedInstType;

    /** Number of instructions issued per cycle. */
    Stats::Formula issueRate;

    /** Number of times the FU was busy. */
    Stats::Vector<> fuBusy;
    /** Number of times the FU was busy per instruction issued. */
    Stats::Formula fuBusyRate;
};

#endif //__CPU_O3_INST_QUEUE_HH__