cpu/beta_cpu/inst_queue.hh

   1 #ifndef __INST_QUEUE_HH__
   2 #define __INST_QUEUE_HH__
   3
   4 #include <list>
   5 #include <map>
   6 #include <queue>
   7 #include <stdint.h>
   8 #include <vector>
   9
  10 #include "base/statistics.hh"
  11 #include "base/timebuf.hh"
  12 #include "cpu/inst_seq.hh"
  13
  14 /**
  15  * A standard instruction queue class.  It holds instructions in an
  16  * array, holds the ordering of the instructions within a linked list,
  17  * and tracks producer/consumer dependencies within a separate linked
  18  * list.  Similar to the rename map and the free list, it expects that
  19  * floating point registers have their indices start after the integer
  20  * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
  21  * and 96-191 are fp).  This remains true even for both logical and
  22  * physical register indices.
  23  */
  24 template <class Impl>
  25 class InstructionQueue
  26 {
  27   public:
  28     //Typedefs from the Impl.
  29     typedef typename Impl::FullCPU FullCPU;
  30     typedef typename Impl::DynInstPtr DynInstPtr;
  31     typedef typename Impl::Params Params;
  32
  33     typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
  34     typedef typename Impl::CPUPol::IssueStruct IssueStruct;
  35     typedef typename Impl::CPUPol::TimeStruct TimeStruct;
  36
  37     // Typedef of iterator through the list of instructions.  Might be
  38     // better to untie this from the FullCPU or pass its information to
  39     // the stages.
  40     typedef typename std::list<DynInstPtr>::iterator ListIt;
  41
  42     /**
  43      * Struct for comparing entries to be added to the priority queue.  This
  44      * gives reverse ordering to the instructions in terms of sequence
  45      * numbers: the instructions with smaller sequence numbers (and hence
  46      * are older) will be at the top of the priority queue.
  47      */
  48     struct pqCompare
  49     {
  50         bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
  51         {
  52             return lhs->seqNum > rhs->seqNum;
  53         }
  54     };
  55
  56     /**
  57      * Struct for comparing entries to be added to the set.  This gives
  58      * standard ordering in terms of sequence numbers.
  59      */
  60     struct setCompare
  61     {
  62         bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
  63         {
  64             return lhs->seqNum < rhs->seqNum;
  65         }
  66     };
  67
  68     typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare>
  69     ReadyInstQueue;
  70
  71     InstructionQueue(Params &params);
  72
  73     void regStats();
  74
  75     void setCPU(FullCPU *cpu);
  76
  77     void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
  78
  79     void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
  80
  81     unsigned numFreeEntries();
  82
  83     bool isFull();
  84
  85     void insert(DynInstPtr &new_inst);
  86
  87     void insertNonSpec(DynInstPtr &new_inst);
  88
  89     void advanceTail(DynInstPtr &inst);
  90
  91     void scheduleReadyInsts();
  92
  93     void scheduleNonSpec(const InstSeqNum &inst);
  94
  95     void wakeDependents(DynInstPtr &completed_inst);
  96
  97     void violation(DynInstPtr &store, DynInstPtr &faulting_load);
  98
  99     // Change this to take in the sequence number
 100     void squash();
 101
 102     void doSquash();
 103
 104     void stopSquash();
 105
 106     /** Debugging function to dump all the list sizes, as well as print
 107      *  out the list of nonspeculative instructions.  Should not be used
 108      *  in any other capacity, but it has no harmful sideaffects.
 109      */
 110     void dumpLists();
 111
 112   private:
 113     /** Debugging function to count how many entries are in the IQ.  It does
 114      *  a linear walk through the instructions, so do not call this function
 115      *  during normal execution.
 116      */
 117     int countInsts();
 118
 119   private:
 120     /** Pointer to the CPU. */
 121     FullCPU *cpu;
 122
 123     /** The memory dependence unit, which tracks/predicts memory dependences
 124      *  between instructions.
 125      */
 126     MemDepUnit memDepUnit;
 127
 128     /** The queue to the execute stage.  Issued instructions will be written
 129      *  into it.
 130      */
 131     TimeBuffer<IssueStruct> *issueToExecuteQueue;
 132
 133     /** The backwards time buffer. */
 134     TimeBuffer<TimeStruct> *timeBuffer;
 135
 136     /** Wire to read information from timebuffer. */
 137     typename TimeBuffer<TimeStruct>::wire fromCommit;
 138
 139     enum InstList {
 140         Int,
 141         Float,
 142         Branch,
 143         Memory,
 144         Misc,
 145         Squashed,
 146         None
 147     };
 148
 149     /** List of ready int instructions.  Used to keep track of the order in
 150      *  which instructions should issue.
 151      */
 152     ReadyInstQueue readyIntInsts;
 153
 154     /** List of ready floating point instructions. */
 155     ReadyInstQueue readyFloatInsts;
 156
 157     /** List of ready branch instructions. */
 158     ReadyInstQueue readyBranchInsts;
 159
 160     /** List of ready memory instructions. */
 161 //    ReadyInstQueue readyMemInsts;
 162
 163     /** List of ready miscellaneous instructions. */
 164     ReadyInstQueue readyMiscInsts;
 165
 166     /** List of squashed instructions (which are still valid and in IQ).
 167      *  Implemented using a priority queue; the entries must contain both
 168      *  the IQ index and sequence number of each instruction so that
 169      *  ordering based on sequence numbers can be used.
 170      */
 171     ReadyInstQueue squashedInsts;
 172
 173     /** List of non-speculative instructions that will be scheduled
 174      *  once the IQ gets a signal from commit.  While it's redundant to
 175      *  have the key be a part of the value (the sequence number is stored
 176      *  inside of DynInst), when these instructions are woken up only
 177      *  the sequence number will be available.  Thus it is necessary to be
 178      *  able to search by the sequence number alone.
 179      */
 180     std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
 181
 182     typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t;
 183
 184     /** Number of free IQ entries left. */
 185     unsigned freeEntries;
 186
 187     /** The number of entries in the instruction queue. */
 188     unsigned numEntries;
 189
 190     /** The number of integer instructions that can be issued in one
 191      *  cycle.
 192      */
 193     unsigned intWidth;
 194
 195     /** The number of floating point instructions that can be issued
 196      *  in one cycle.
 197      */
 198     unsigned floatWidth;
 199
 200     /** The number of branches that can be issued in one cycle. */
 201     unsigned branchWidth;
 202
 203     /** The number of memory instructions that can be issued in one cycle. */
 204     unsigned memoryWidth;
 205
 206     /** The total number of instructions that can be issued in one cycle. */
 207     unsigned totalWidth;
 208
 209     //The number of physical registers in the CPU.
 210     unsigned numPhysRegs;
 211
 212     /** The number of physical integer registers in the CPU. */
 213     unsigned numPhysIntRegs;
 214
 215     /** The number of floating point registers in the CPU. */
 216     unsigned numPhysFloatRegs;
 217
 218     /** Delay between commit stage and the IQ.
 219      *  @todo: Make there be a distinction between the delays within IEW.
 220      */
 221     unsigned commitToIEWDelay;
 222
 223     //////////////////////////////////
 224     // Variables needed for squashing
 225     //////////////////////////////////
 226
 227     /** The sequence number of the squashed instruction. */
 228     InstSeqNum squashedSeqNum;
 229
 230     /** Iterator that points to the youngest instruction in the IQ. */
 231     ListIt tail;
 232
 233     /** Iterator that points to the last instruction that has been squashed.
 234      *  This will not be valid unless the IQ is in the process of squashing.
 235      */
 236     ListIt squashIt;
 237
 238     ///////////////////////////////////
 239     // Dependency graph stuff
 240     ///////////////////////////////////
 241
 242     class DependencyEntry
 243     {
 244       public:
 245         DynInstPtr inst;
 246         //Might want to include data about what arch. register the
 247         //dependence is waiting on.
 248         DependencyEntry *next;
 249
 250         //This function, and perhaps this whole class, stand out a little
 251         //bit as they don't fit a classification well.  I want access
 252         //to the underlying structure of the linked list, yet at
 253         //the same time it feels like this should be something abstracted
 254         //away.  So for now it will sit here, within the IQ, until
 255         //a better implementation is decided upon.
 256         // This function probably shouldn't be within the entry...
 257         void insert(DynInstPtr &new_inst);
 258
 259         void remove(DynInstPtr &inst_to_remove);
 260
 261         // Debug variable, remove when done testing.
 262         static unsigned mem_alloc_counter;
 263     };
 264
 265     /** Array of linked lists.  Each linked list is a list of all the
 266      *  instructions that depend upon a given register.  The actual
 267      *  register's index is used to index into the graph; ie all
 268      *  instructions in flight that are dependent upon r34 will be
 269      *  in the linked list of dependGraph[34].
 270      */
 271     DependencyEntry *dependGraph;
 272
 273     /** A cache of the recently woken registers.  It is 1 if the register
 274      *  has been woken up recently, and 0 if the register has been added
 275      *  to the dependency graph and has not yet received its value.  It
 276      *  is basically a secondary scoreboard, and should pretty much mirror
 277      *  the scoreboard that exists in the rename map.
 278      */
 279     vector<bool> regScoreboard;
 280
 281     bool addToDependents(DynInstPtr &new_inst);
 282     void insertDependency(DynInstPtr &new_inst);
 283     void createDependency(DynInstPtr &new_inst);
 284     void dumpDependGraph();
 285
 286     void addIfReady(DynInstPtr &inst);
 287
 288     Stats::Scalar<> iqInstsAdded;
 289     Stats::Scalar<> iqNonSpecInstsAdded;
 290 //    Stats::Scalar<> iqIntInstsAdded;
 291     Stats::Scalar<> iqIntInstsIssued;
 292 //    Stats::Scalar<> iqFloatInstsAdded;
 293     Stats::Scalar<> iqFloatInstsIssued;
 294 //    Stats::Scalar<> iqBranchInstsAdded;
 295     Stats::Scalar<> iqBranchInstsIssued;
 296 //    Stats::Scalar<> iqMemInstsAdded;
 297     Stats::Scalar<> iqMemInstsIssued;
 298 //    Stats::Scalar<> iqMiscInstsAdded;
 299     Stats::Scalar<> iqMiscInstsIssued;
 300     Stats::Scalar<> iqSquashedInstsIssued;
 301     Stats::Scalar<> iqLoopSquashStalls;
 302     Stats::Scalar<> iqSquashedInstsExamined;
 303     Stats::Scalar<> iqSquashedOperandsExamined;
 304     Stats::Scalar<> iqSquashedNonSpecRemoved;
 305
 306 };
 307
 308 #endif //__INST_QUEUE_HH__