src/cpu/o3/mem_dep_unit.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_MEM_DEP_UNIT_HH__
  32 #define __CPU_O3_MEM_DEP_UNIT_HH__
  33
  34 #include <list>
  35 #include <set>
  36
  37 #include "base/hashmap.hh"
  38 #include "base/refcnt.hh"
  39 #include "base/statistics.hh"
  40 #include "cpu/inst_seq.hh"
  41
  42 struct SNHash {
  43     size_t operator() (const InstSeqNum &seq_num) const {
  44         unsigned a = (unsigned)seq_num;
  45         unsigned hash = (((a >> 14) ^ ((a >> 2) & 0xffff))) & 0x7FFFFFFF;
  46
  47         return hash;
  48     }
  49 };
  50
  51 template <class Impl>
  52 class InstructionQueue;
  53
  54 /**
  55  * Memory dependency unit class.  This holds the memory dependence predictor.
  56  * As memory operations are issued to the IQ, they are also issued to this
  57  * unit, which then looks up the prediction as to what they are dependent
  58  * upon.  This unit must be checked prior to a memory operation being able
  59  * to issue.  Although this is templated, it's somewhat hard to make a generic
  60  * memory dependence unit.  This one is mostly for store sets; it will be
  61  * quite limited in what other memory dependence predictions it can also
  62  * utilize.  Thus this class should be most likely be rewritten for other
  63  * dependence prediction schemes.
  64  */
  65 template <class MemDepPred, class Impl>
  66 class MemDepUnit {
  67   public:
  68     typedef typename Impl::Params Params;
  69     typedef typename Impl::DynInstPtr DynInstPtr;
  70
  71     /** Empty constructor. Must call init() prior to using in this case. */
  72     MemDepUnit();
  73
  74     /** Constructs a MemDepUnit with given parameters. */
  75     MemDepUnit(Params *params);
  76
  77     /** Frees up any memory allocated. */
  78     ~MemDepUnit();
  79
  80     /** Returns the name of the memory dependence unit. */
  81     std::string name() const;
  82
  83     /** Initializes the unit with parameters and a thread id. */
  84     void init(Params *params, int tid);
  85
  86     /** Registers statistics. */
  87     void regStats();
  88
  89     /** Switches out the memory dependence predictor. */
  90     void switchOut();
  91
  92     /** Takes over from another CPU's thread. */
  93     void takeOverFrom();
  94
  95     /** Sets the pointer to the IQ. */
  96     void setIQ(InstructionQueue<Impl> *iq_ptr);
  97
  98     /** Inserts a memory instruction. */
  99     void insert(DynInstPtr &inst);
 100
 101     /** Inserts a non-speculative memory instruction. */
 102     void insertNonSpec(DynInstPtr &inst);
 103
 104     /** Inserts a barrier instruction. */
 105     void insertBarrier(DynInstPtr &barr_inst);
 106
 107     /** Indicate that an instruction has its registers ready. */
 108     void regsReady(DynInstPtr &inst);
 109
 110     /** Indicate that a non-speculative instruction is ready. */
 111     void nonSpecInstReady(DynInstPtr &inst);
 112
 113     /** Reschedules an instruction to be re-executed. */
 114     void reschedule(DynInstPtr &inst);
 115
 116     /** Replays all instructions that have been rescheduled by moving them to
 117      *  the ready list.
 118      */
 119     void replay(DynInstPtr &inst);
 120
 121     /** Completes a memory instruction. */
 122     void completed(DynInstPtr &inst);
 123
 124     /** Completes a barrier instruction. */
 125     void completeBarrier(DynInstPtr &inst);
 126
 127     /** Wakes any dependents of a memory instruction. */
 128     void wakeDependents(DynInstPtr &inst);
 129
 130     /** Squashes all instructions up until a given sequence number for a
 131      *  specific thread.
 132      */
 133     void squash(const InstSeqNum &squashed_num, unsigned tid);
 134
 135     /** Indicates an ordering violation between a store and a younger load. */
 136     void violation(DynInstPtr &store_inst, DynInstPtr &violating_load);
 137
 138     /** Issues the given instruction */
 139     void issue(DynInstPtr &inst);
 140
 141     /** Debugging function to dump the lists of instructions. */
 142     void dumpLists();
 143
 144   private:
 145     typedef typename std::list<DynInstPtr>::iterator ListIt;
 146
 147     class MemDepEntry;
 148
 149     typedef RefCountingPtr<MemDepEntry> MemDepEntryPtr;
 150
 151     /** Memory dependence entries that track memory operations, marking
 152      *  when the instruction is ready to execute and what instructions depend
 153      *  upon it.
 154      */
 155     class MemDepEntry : public RefCounted {
 156       public:
 157         /** Constructs a memory dependence entry. */
 158         MemDepEntry(DynInstPtr &new_inst)
 159             : inst(new_inst), regsReady(false), memDepReady(false),
 160               completed(false), squashed(false)
 161         {
 162 #ifdef DEBUG
 163             ++memdep_count;
 164
 165             DPRINTF(MemDepUnit, "Memory dependency entry created.  "
 166                     "memdep_count=%i\n", memdep_count);
 167 #endif
 168         }
 169
 170         /** Frees any pointers. */
 171         ~MemDepEntry()
 172         {
 173             for (int i = 0; i < dependInsts.size(); ++i) {
 174                 dependInsts[i] = NULL;
 175             }
 176 #ifdef DEBUG
 177             --memdep_count;
 178
 179             DPRINTF(MemDepUnit, "Memory dependency entry deleted.  "
 180                     "memdep_count=%i\n", memdep_count);
 181 #endif
 182         }
 183
 184         /** Returns the name of the memory dependence entry. */
 185         std::string name() const { return "memdepentry"; }
 186
 187         /** The instruction being tracked. */
 188         DynInstPtr inst;
 189
 190         /** The iterator to the instruction's location inside the list. */
 191         ListIt listIt;
 192
 193         /** A vector of any dependent instructions. */
 194         std::vector<MemDepEntryPtr> dependInsts;
 195
 196         /** If the registers are ready or not. */
 197         bool regsReady;
 198         /** If all memory dependencies have been satisfied. */
 199         bool memDepReady;
 200         /** If the instruction is completed. */
 201         bool completed;
 202         /** If the instruction is squashed. */
 203         bool squashed;
 204
 205         /** For debugging. */
 206 #ifdef DEBUG
 207         static int memdep_count;
 208         static int memdep_insert;
 209         static int memdep_erase;
 210 #endif
 211     };
 212
 213     /** Finds the memory dependence entry in the hash map. */
 214     inline MemDepEntryPtr &findInHash(const DynInstPtr &inst);
 215
 216     /** Moves an entry to the ready list. */
 217     inline void moveToReady(MemDepEntryPtr &ready_inst_entry);
 218
 219     typedef m5::hash_map<InstSeqNum, MemDepEntryPtr, SNHash> MemDepHash;
 220
 221     typedef typename MemDepHash::iterator MemDepHashIt;
 222
 223     /** A hash map of all memory dependence entries. */
 224     MemDepHash memDepHash;
 225
 226     /** A list of all instructions in the memory dependence unit. */
 227     std::list<DynInstPtr> instList[Impl::MaxThreads];
 228
 229     /** A list of all instructions that are going to be replayed. */
 230     std::list<DynInstPtr> instsToReplay;
 231
 232     /** The memory dependence predictor.  It is accessed upon new
 233      *  instructions being added to the IQ, and responds by telling
 234      *  this unit what instruction the newly added instruction is dependent
 235      *  upon.
 236      */
 237     MemDepPred depPred;
 238
 239     /** Is there an outstanding load barrier that loads must wait on. */
 240     bool loadBarrier;
 241     /** The sequence number of the load barrier. */
 242     InstSeqNum loadBarrierSN;
 243     /** Is there an outstanding store barrier that loads must wait on. */
 244     bool storeBarrier;
 245     /** The sequence number of the store barrier. */
 246     InstSeqNum storeBarrierSN;
 247
 248     /** Pointer to the IQ. */
 249     InstructionQueue<Impl> *iqPtr;
 250
 251     /** The thread id of this memory dependence unit. */
 252     int id;
 253
 254     /** Stat for number of inserted loads. */
 255     Stats::Scalar<> insertedLoads;
 256     /** Stat for number of inserted stores. */
 257     Stats::Scalar<> insertedStores;
 258     /** Stat for number of conflicting loads that had to wait for a store. */
 259     Stats::Scalar<> conflictingLoads;
 260     /** Stat for number of conflicting stores that had to wait for a store. */
 261     Stats::Scalar<> conflictingStores;
 262 };
 263
 264 #endif // __CPU_O3_MEM_DEP_UNIT_HH__