1/*
|
2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
|
2 * Copyright (c) 2004-2005 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
|
29#ifndef __CPU_O3_MEM_DEP_UNIT_HH__
30#define __CPU_O3_MEM_DEP_UNIT_HH__
|
31#ifndef __CPU_O3_CPU_MEM_DEP_UNIT_HH__ 32#define __CPU_O3_CPU_MEM_DEP_UNIT_HH__ |
33
|
32#include <list>
|
34#include <map> |
35#include <set> 36
|
35#include "base/hashmap.hh"
36#include "base/refcnt.hh"
|
37#include "base/statistics.hh" 38#include "cpu/inst_seq.hh" 39
|
40struct SNHash {
41 size_t operator() (const InstSeqNum &seq_num) const {
42 unsigned a = (unsigned)seq_num;
43 unsigned hash = (((a >> 14) ^ ((a >> 2) & 0xffff))) & 0x7FFFFFFF;
44
45 return hash;
46 }
47};
48
49template <class Impl>
50class InstructionQueue;
51
|
40/** 41 * Memory dependency unit class. This holds the memory dependence predictor. 42 * As memory operations are issued to the IQ, they are also issued to this 43 * unit, which then looks up the prediction as to what they are dependent 44 * upon. This unit must be checked prior to a memory operation being able 45 * to issue. Although this is templated, it's somewhat hard to make a generic 46 * memory dependence unit. This one is mostly for store sets; it will be 47 * quite limited in what other memory dependence predictions it can also 48 * utilize. Thus this class should be most likely be rewritten for other 49 * dependence prediction schemes. 50 */ 51template <class MemDepPred, class Impl> 52class MemDepUnit { 53 public: 54 typedef typename Impl::Params Params; 55 typedef typename Impl::DynInstPtr DynInstPtr; 56
|
69 /** Empty constructor. Must call init() prior to using in this case. */
70 MemDepUnit() {}
|
57 public: 58 MemDepUnit(Params ¶ms); |
59
|
72 /** Constructs a MemDepUnit with given parameters. */
73 MemDepUnit(Params *params);
74
75 /** Frees up any memory allocated. */
76 ~MemDepUnit();
77
78 /** Returns the name of the memory dependence unit. */
79 std::string name() const;
80
81 /** Initializes the unit with parameters and a thread id. */
82 void init(Params *params, int tid);
83
84 /** Registers statistics. */
|
60 void regStats(); 61
|
87 void switchOut();
88
89 void takeOverFrom();
90
91 /** Sets the pointer to the IQ. */
92 void setIQ(InstructionQueue<Impl> *iq_ptr);
93
94 /** Inserts a memory instruction. */
|
62 void insert(DynInstPtr &inst); 63
|
97 /** Inserts a non-speculative memory instruction. */
|
64 void insertNonSpec(DynInstPtr &inst); 65
|
100 /** Inserts a barrier instruction. */
101 void insertBarrier(DynInstPtr &barr_inst);
|
66 // Will want to make this operation relatively fast. Right now it 67 // is somewhat slow. 68 DynInstPtr &top(); |
69
|
103 /** Indicate that an instruction has its registers ready. */
|
70 void pop(); 71 |
72 void regsReady(DynInstPtr &inst); 73
|
106 /** Indicate that a non-speculative instruction is ready. */
|
74 void nonSpecInstReady(DynInstPtr &inst); 75
|
109 /** Reschedules an instruction to be re-executed. */
110 void reschedule(DynInstPtr &inst);
|
76 void issue(DynInstPtr &inst); |
77
|
112 /** Replays all instructions that have been rescheduled by moving them to
113 * the ready list.
114 */
115 void replay(DynInstPtr &inst);
116
117 /** Completes a memory instruction. */
118 void completed(DynInstPtr &inst);
119
120 /** Completes a barrier instruction. */
121 void completeBarrier(DynInstPtr &inst);
122
123 /** Wakes any dependents of a memory instruction. */
|
78 void wakeDependents(DynInstPtr &inst); 79
|
126 /** Squashes all instructions up until a given sequence number for a
127 * specific thread.
128 */
129 void squash(const InstSeqNum &squashed_num, unsigned tid);
|
80 void squash(const InstSeqNum &squashed_num); |
81
|
131 /** Indicates an ordering violation between a store and a younger load. */
|
82 void violation(DynInstPtr &store_inst, DynInstPtr &violating_load); 83
|
134 /** Issues the given instruction */
135 void issue(DynInstPtr &inst);
|
84 inline bool empty() 85 { return readyInsts.empty(); } |
86
|
137 /** Debugging function to dump the lists of instructions. */
138 void dumpLists();
139
|
87 private:
|
141 typedef typename std::list<DynInstPtr>::iterator ListIt;
|
88 typedef typename std::set<InstSeqNum>::iterator sn_it_t; 89 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator dyn_it_t; |
90
|
143 class MemDepEntry;
|
91 // Forward declarations so that the following two typedefs work. 92 class Dependency; 93 class ltDependency; |
94
|
145 typedef RefCountingPtr<MemDepEntry> MemDepEntryPtr;
|
95 typedef typename std::set<Dependency, ltDependency>::iterator dep_it_t; 96 typedef typename std::map<InstSeqNum, vector<dep_it_t> >::iterator 97 sd_it_t; |
98
|
147 /** Memory dependence entries that track memory operations, marking
148 * when the instruction is ready to execute and what instructions depend
149 * upon it.
150 */
151 class MemDepEntry : public RefCounted {
152 public:
153 /** Constructs a memory dependence entry. */
154 MemDepEntry(DynInstPtr &new_inst)
155 : inst(new_inst), regsReady(false), memDepReady(false),
156 completed(false), squashed(false)
157 {
158 ++memdep_count;
|
99 struct Dependency { 100 Dependency(const InstSeqNum &_seqNum) 101 : seqNum(_seqNum), regsReady(0), memDepReady(0) 102 { } |
103
|
160 DPRINTF(MemDepUnit, "Memory dependency entry created. "
161 "memdep_count=%i\n", memdep_count);
162 }
|
104 Dependency(const InstSeqNum &_seqNum, bool _regsReady, 105 bool _memDepReady) 106 : seqNum(_seqNum), regsReady(_regsReady), 107 memDepReady(_memDepReady) 108 { } |
109
|
164 /** Frees any pointers. */
165 ~MemDepEntry()
166 {
167 for (int i = 0; i < dependInsts.size(); ++i) {
168 dependInsts[i] = NULL;
169 }
|
110 InstSeqNum seqNum; 111 mutable bool regsReady; 112 mutable bool memDepReady; 113 mutable sd_it_t storeDep; 114 }; |
115
|
171 --memdep_count;
172
173 DPRINTF(MemDepUnit, "Memory dependency entry deleted. "
174 "memdep_count=%i\n", memdep_count);
|
116 struct ltDependency { 117 bool operator() (const Dependency &lhs, const Dependency &rhs) 118 { 119 return lhs.seqNum < rhs.seqNum; |
120 }
|
176
177 /** Returns the name of the memory dependence entry. */
178 std::string name() const { return "memdepentry"; }
179
180 /** The instruction being tracked. */
181 DynInstPtr inst;
182
183 /** The iterator to the instruction's location inside the list. */
184 ListIt listIt;
185
186 /** A vector of any dependent instructions. */
187 std::vector<MemDepEntryPtr> dependInsts;
188
189 /** If the registers are ready or not. */
190 bool regsReady;
191 /** If all memory dependencies have been satisfied. */
192 bool memDepReady;
193 /** If the instruction is completed. */
194 bool completed;
195 /** If the instruction is squashed. */
196 bool squashed;
197
198 /** For debugging. */
199 static int memdep_count;
200 static int memdep_insert;
201 static int memdep_erase;
|
121 }; 122
|
204 /** Finds the memory dependence entry in the hash map. */
205 inline MemDepEntryPtr &findInHash(const DynInstPtr &inst);
|
123 inline void moveToReady(dep_it_t &woken_inst); |
124
|
207 /** Moves an entry to the ready list. */
208 inline void moveToReady(MemDepEntryPtr &ready_inst_entry);
|
125 /** List of instructions that have passed through rename, yet are still 126 * waiting on either a memory dependence to resolve or source registers to 127 * become available before they can issue. 128 */ 129 std::set<Dependency, ltDependency> waitingInsts; |
130
|
210 typedef m5::hash_map<InstSeqNum, MemDepEntryPtr, SNHash> MemDepHash;
|
131 /** List of instructions that have all their predicted memory dependences 132 * resolved and their source registers ready. 133 */ 134 std::set<InstSeqNum> readyInsts; |
135
|
212 typedef typename MemDepHash::iterator MemDepHashIt;
|
136 // Change this to hold a vector of iterators, which will point to the 137 // entry of the waiting instructions. 138 /** List of stores' sequence numbers, each of which has a vector of 139 * iterators. The iterators point to the appropriate node within 140 * waitingInsts that has the depenendent instruction. 141 */ 142 std::map<InstSeqNum, vector<dep_it_t> > storeDependents; |
143
|
214 /** A hash map of all memory dependence entries. */
215 MemDepHash memDepHash;
|
144 // For now will implement this as a map...hash table might not be too 145 // bad, or could move to something that mimics the current dependency 146 // graph. 147 std::map<InstSeqNum, DynInstPtr> memInsts; |
148
|
217 /** A list of all instructions in the memory dependence unit. */
218 std::list<DynInstPtr> instList[Impl::MaxThreads];
|
149 // Iterator pointer to the top instruction which has is ready. 150 // Is set by the top() call. 151 dyn_it_t topInst; |
152
|
220 /** A list of all instructions that are going to be replayed. */
221 std::list<DynInstPtr> instsToReplay;
222
|
153 /** The memory dependence predictor. It is accessed upon new 154 * instructions being added to the IQ, and responds by telling 155 * this unit what instruction the newly added instruction is dependent 156 * upon. 157 */ 158 MemDepPred depPred; 159
|
230 bool loadBarrier;
231 InstSeqNum loadBarrierSN;
232 bool storeBarrier;
233 InstSeqNum storeBarrierSN;
234
235 /** Pointer to the IQ. */
236 InstructionQueue<Impl> *iqPtr;
237
238 /** The thread id of this memory dependence unit. */
239 int id;
240
241 /** Stat for number of inserted loads. */
|
160 Stats::Scalar<> insertedLoads;
|
243 /** Stat for number of inserted stores. */
|
161 Stats::Scalar<> insertedStores;
|
245 /** Stat for number of conflicting loads that had to wait for a store. */
|
162 Stats::Scalar<> conflictingLoads;
|
247 /** Stat for number of conflicting stores that had to wait for a store. */
|
163 Stats::Scalar<> conflictingStores; 164}; 165
|
251#endif // __CPU_O3_MEM_DEP_UNIT_HH__
|
166#endif // __CPU_O3_CPU_MEM_DEP_UNIT_HH__ |
|