mem_dep_unit.hh revision 13429:a1e199fd8122
111986Sandreas.sandberg@arm.com/* 211986Sandreas.sandberg@arm.com * Copyright (c) 2012, 2014 ARM Limited 311986Sandreas.sandberg@arm.com * All rights reserved 411986Sandreas.sandberg@arm.com * 511986Sandreas.sandberg@arm.com * The license below extends only to copyright in the software and shall 611986Sandreas.sandberg@arm.com * not be construed as granting a license to any other intellectual 711986Sandreas.sandberg@arm.com * property including but not limited to intellectual property relating 811986Sandreas.sandberg@arm.com * to a hardware implementation of the functionality of the software 911986Sandreas.sandberg@arm.com * licensed hereunder. You may use the software subject to the license 1011986Sandreas.sandberg@arm.com * terms below provided that you ensure that this notice is replicated 1111986Sandreas.sandberg@arm.com * unmodified and in its entirety in all distributions of the software, 1211986Sandreas.sandberg@arm.com * modified or unmodified, in source code or in binary form. 1312037Sandreas.sandberg@arm.com * 1412037Sandreas.sandberg@arm.com * Copyright (c) 2004-2006 The Regents of The University of Michigan 1511986Sandreas.sandberg@arm.com * All rights reserved. 1611986Sandreas.sandberg@arm.com * 1711986Sandreas.sandberg@arm.com * Redistribution and use in source and binary forms, with or without 1811986Sandreas.sandberg@arm.com * modification, are permitted provided that the following conditions are 1911986Sandreas.sandberg@arm.com * met: redistributions of source code must retain the above copyright 2011986Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer; 2111986Sandreas.sandberg@arm.com * redistributions in binary form must reproduce the above copyright 2211986Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer in the 2311986Sandreas.sandberg@arm.com * documentation and/or other materials provided with the distribution; 2411986Sandreas.sandberg@arm.com * neither the name of the copyright holders nor the names of its 2511986Sandreas.sandberg@arm.com * contributors may be used to endorse or promote products derived from 2611986Sandreas.sandberg@arm.com * this software without specific prior written permission. 2711986Sandreas.sandberg@arm.com * 2811986Sandreas.sandberg@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2911986Sandreas.sandberg@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3011986Sandreas.sandberg@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3111986Sandreas.sandberg@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3211986Sandreas.sandberg@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3311986Sandreas.sandberg@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3411986Sandreas.sandberg@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3511986Sandreas.sandberg@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3611986Sandreas.sandberg@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3711986Sandreas.sandberg@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3811986Sandreas.sandberg@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3911986Sandreas.sandberg@arm.com * 4011986Sandreas.sandberg@arm.com * Authors: Kevin Lim 4111986Sandreas.sandberg@arm.com */ 4211986Sandreas.sandberg@arm.com 4311986Sandreas.sandberg@arm.com#ifndef __CPU_O3_MEM_DEP_UNIT_HH__ 4411986Sandreas.sandberg@arm.com#define __CPU_O3_MEM_DEP_UNIT_HH__ 4511986Sandreas.sandberg@arm.com 4611986Sandreas.sandberg@arm.com#include <list> 4711986Sandreas.sandberg@arm.com#include <memory> 4811986Sandreas.sandberg@arm.com#include <set> 4911986Sandreas.sandberg@arm.com#include <unordered_map> 5011986Sandreas.sandberg@arm.com 5111986Sandreas.sandberg@arm.com#include "base/statistics.hh" 5211986Sandreas.sandberg@arm.com#include "cpu/inst_seq.hh" 5311986Sandreas.sandberg@arm.com#include "debug/MemDepUnit.hh" 5411986Sandreas.sandberg@arm.com 5511986Sandreas.sandberg@arm.comstruct SNHash { 5611986Sandreas.sandberg@arm.com size_t operator() (const InstSeqNum &seq_num) const { 5711986Sandreas.sandberg@arm.com unsigned a = (unsigned)seq_num; 5811986Sandreas.sandberg@arm.com unsigned hash = (((a >> 14) ^ ((a >> 2) & 0xffff))) & 0x7FFFFFFF; 5911986Sandreas.sandberg@arm.com 6011986Sandreas.sandberg@arm.com return hash; 6111986Sandreas.sandberg@arm.com } 6211986Sandreas.sandberg@arm.com}; 6311986Sandreas.sandberg@arm.com 6411986Sandreas.sandberg@arm.comstruct DerivO3CPUParams; 6511986Sandreas.sandberg@arm.com 6611986Sandreas.sandberg@arm.comtemplate <class Impl> 6711986Sandreas.sandberg@arm.comclass InstructionQueue; 6811986Sandreas.sandberg@arm.com 6911986Sandreas.sandberg@arm.com/** 7011986Sandreas.sandberg@arm.com * Memory dependency unit class. This holds the memory dependence predictor. 7111986Sandreas.sandberg@arm.com * As memory operations are issued to the IQ, they are also issued to this 7211986Sandreas.sandberg@arm.com * unit, which then looks up the prediction as to what they are dependent 7311986Sandreas.sandberg@arm.com * upon. This unit must be checked prior to a memory operation being able 7411986Sandreas.sandberg@arm.com * to issue. Although this is templated, it's somewhat hard to make a generic 7511986Sandreas.sandberg@arm.com * memory dependence unit. This one is mostly for store sets; it will be 7611986Sandreas.sandberg@arm.com * quite limited in what other memory dependence predictions it can also 7711986Sandreas.sandberg@arm.com * utilize. Thus this class should be most likely be rewritten for other 7811986Sandreas.sandberg@arm.com * dependence prediction schemes. 7911986Sandreas.sandberg@arm.com */ 8011986Sandreas.sandberg@arm.comtemplate <class MemDepPred, class Impl> 8111986Sandreas.sandberg@arm.comclass MemDepUnit 8211986Sandreas.sandberg@arm.com{ 8311986Sandreas.sandberg@arm.com protected: 8411986Sandreas.sandberg@arm.com std::string _name; 8511986Sandreas.sandberg@arm.com 8611986Sandreas.sandberg@arm.com public: 8711986Sandreas.sandberg@arm.com typedef typename Impl::DynInstPtr DynInstPtr; 8811986Sandreas.sandberg@arm.com typedef typename Impl::DynInstConstPtr DynInstConstPtr; 8911986Sandreas.sandberg@arm.com 9011986Sandreas.sandberg@arm.com /** Empty constructor. Must call init() prior to using in this case. */ 9111986Sandreas.sandberg@arm.com MemDepUnit(); 9211986Sandreas.sandberg@arm.com 9311986Sandreas.sandberg@arm.com /** Constructs a MemDepUnit with given parameters. */ 9411986Sandreas.sandberg@arm.com MemDepUnit(DerivO3CPUParams *params); 9511986Sandreas.sandberg@arm.com 9611986Sandreas.sandberg@arm.com /** Frees up any memory allocated. */ 9711986Sandreas.sandberg@arm.com ~MemDepUnit(); 9811986Sandreas.sandberg@arm.com 9911986Sandreas.sandberg@arm.com /** Returns the name of the memory dependence unit. */ 10011986Sandreas.sandberg@arm.com std::string name() const { return _name; } 10111986Sandreas.sandberg@arm.com 10211986Sandreas.sandberg@arm.com /** Initializes the unit with parameters and a thread id. */ 10311986Sandreas.sandberg@arm.com void init(DerivO3CPUParams *params, ThreadID tid); 10411986Sandreas.sandberg@arm.com 10511986Sandreas.sandberg@arm.com /** Registers statistics. */ 10612037Sandreas.sandberg@arm.com void regStats(); 10712037Sandreas.sandberg@arm.com 10812037Sandreas.sandberg@arm.com /** Determine if we are drained. */ 10911986Sandreas.sandberg@arm.com bool isDrained() const; 11011986Sandreas.sandberg@arm.com 11111986Sandreas.sandberg@arm.com /** Perform sanity checks after a drain. */ 11211986Sandreas.sandberg@arm.com void drainSanityCheck() const; 11311986Sandreas.sandberg@arm.com 11411986Sandreas.sandberg@arm.com /** Takes over from another CPU's thread. */ 11511986Sandreas.sandberg@arm.com void takeOverFrom(); 11611986Sandreas.sandberg@arm.com 11711986Sandreas.sandberg@arm.com /** Sets the pointer to the IQ. */ 11811986Sandreas.sandberg@arm.com void setIQ(InstructionQueue<Impl> *iq_ptr); 11911986Sandreas.sandberg@arm.com 12011986Sandreas.sandberg@arm.com /** Inserts a memory instruction. */ 12111986Sandreas.sandberg@arm.com void insert(const DynInstPtr &inst); 12211986Sandreas.sandberg@arm.com 12311986Sandreas.sandberg@arm.com /** Inserts a non-speculative memory instruction. */ 12411986Sandreas.sandberg@arm.com void insertNonSpec(const DynInstPtr &inst); 12511986Sandreas.sandberg@arm.com 12611986Sandreas.sandberg@arm.com /** Inserts a barrier instruction. */ 12711986Sandreas.sandberg@arm.com void insertBarrier(const DynInstPtr &barr_inst); 12811986Sandreas.sandberg@arm.com 12911986Sandreas.sandberg@arm.com /** Indicate that an instruction has its registers ready. */ 13011986Sandreas.sandberg@arm.com void regsReady(const DynInstPtr &inst); 13111986Sandreas.sandberg@arm.com 13211986Sandreas.sandberg@arm.com /** Indicate that a non-speculative instruction is ready. */ 13311986Sandreas.sandberg@arm.com void nonSpecInstReady(const DynInstPtr &inst); 13411986Sandreas.sandberg@arm.com 13511986Sandreas.sandberg@arm.com /** Reschedules an instruction to be re-executed. */ 13611986Sandreas.sandberg@arm.com void reschedule(const DynInstPtr &inst); 13711986Sandreas.sandberg@arm.com 13811986Sandreas.sandberg@arm.com /** Replays all instructions that have been rescheduled by moving them to 13911986Sandreas.sandberg@arm.com * the ready list. 14011986Sandreas.sandberg@arm.com */ 14111986Sandreas.sandberg@arm.com void replay(); 14211986Sandreas.sandberg@arm.com 14311986Sandreas.sandberg@arm.com /** Completes a memory instruction. */ 14411986Sandreas.sandberg@arm.com void completed(const DynInstPtr &inst); 14511986Sandreas.sandberg@arm.com 14611986Sandreas.sandberg@arm.com /** Completes a barrier instruction. */ 14711986Sandreas.sandberg@arm.com void completeBarrier(const DynInstPtr &inst); 14811986Sandreas.sandberg@arm.com 14911986Sandreas.sandberg@arm.com /** Wakes any dependents of a memory instruction. */ 15011986Sandreas.sandberg@arm.com void wakeDependents(const DynInstPtr &inst); 15111986Sandreas.sandberg@arm.com 15211986Sandreas.sandberg@arm.com /** Squashes all instructions up until a given sequence number for a 15311986Sandreas.sandberg@arm.com * specific thread. 15411986Sandreas.sandberg@arm.com */ 15511986Sandreas.sandberg@arm.com void squash(const InstSeqNum &squashed_num, ThreadID tid); 15611986Sandreas.sandberg@arm.com 15711986Sandreas.sandberg@arm.com /** Indicates an ordering violation between a store and a younger load. */ 15811986Sandreas.sandberg@arm.com void violation(const DynInstPtr &store_inst, 15911986Sandreas.sandberg@arm.com const DynInstPtr &violating_load); 16011986Sandreas.sandberg@arm.com 16111986Sandreas.sandberg@arm.com /** Issues the given instruction */ 16211986Sandreas.sandberg@arm.com void issue(const DynInstPtr &inst); 16311986Sandreas.sandberg@arm.com 16411986Sandreas.sandberg@arm.com /** Debugging function to dump the lists of instructions. */ 16511986Sandreas.sandberg@arm.com void dumpLists(); 16611986Sandreas.sandberg@arm.com 16711986Sandreas.sandberg@arm.com private: 16811986Sandreas.sandberg@arm.com typedef typename std::list<DynInstPtr>::iterator ListIt; 16911986Sandreas.sandberg@arm.com 17011986Sandreas.sandberg@arm.com class MemDepEntry; 17111986Sandreas.sandberg@arm.com 17211986Sandreas.sandberg@arm.com typedef std::shared_ptr<MemDepEntry> MemDepEntryPtr; 17311986Sandreas.sandberg@arm.com 17411986Sandreas.sandberg@arm.com /** Memory dependence entries that track memory operations, marking 17511986Sandreas.sandberg@arm.com * when the instruction is ready to execute and what instructions depend 17611986Sandreas.sandberg@arm.com * upon it. 17711986Sandreas.sandberg@arm.com */ 17811986Sandreas.sandberg@arm.com class MemDepEntry { 17911986Sandreas.sandberg@arm.com public: 18011986Sandreas.sandberg@arm.com /** Constructs a memory dependence entry. */ 18112037Sandreas.sandberg@arm.com MemDepEntry(const DynInstPtr &new_inst) 18212037Sandreas.sandberg@arm.com : inst(new_inst), regsReady(false), memDepReady(false), 18312037Sandreas.sandberg@arm.com completed(false), squashed(false) 18412037Sandreas.sandberg@arm.com { 18512037Sandreas.sandberg@arm.com#ifdef DEBUG 18612037Sandreas.sandberg@arm.com ++memdep_count; 18712037Sandreas.sandberg@arm.com 18811986Sandreas.sandberg@arm.com DPRINTF(MemDepUnit, "Memory dependency entry created. " 18911986Sandreas.sandberg@arm.com "memdep_count=%i %s\n", memdep_count, inst->pcState()); 19011986Sandreas.sandberg@arm.com#endif 19111986Sandreas.sandberg@arm.com } 19211986Sandreas.sandberg@arm.com 19311986Sandreas.sandberg@arm.com /** Frees any pointers. */ 19411986Sandreas.sandberg@arm.com ~MemDepEntry() 19511986Sandreas.sandberg@arm.com { 19611986Sandreas.sandberg@arm.com for (int i = 0; i < dependInsts.size(); ++i) { 19711986Sandreas.sandberg@arm.com dependInsts[i] = NULL; 19811986Sandreas.sandberg@arm.com } 19912391Sjason@lowepower.com#ifdef DEBUG 20011986Sandreas.sandberg@arm.com --memdep_count; 20111986Sandreas.sandberg@arm.com 20212037Sandreas.sandberg@arm.com DPRINTF(MemDepUnit, "Memory dependency entry deleted. " 20311986Sandreas.sandberg@arm.com "memdep_count=%i %s\n", memdep_count, inst->pcState()); 20411986Sandreas.sandberg@arm.com#endif 20511986Sandreas.sandberg@arm.com } 20611986Sandreas.sandberg@arm.com 20711986Sandreas.sandberg@arm.com /** Returns the name of the memory dependence entry. */ 20811986Sandreas.sandberg@arm.com std::string name() const { return "memdepentry"; } 20911986Sandreas.sandberg@arm.com 21011986Sandreas.sandberg@arm.com /** The instruction being tracked. */ 21111986Sandreas.sandberg@arm.com DynInstPtr inst; 21211986Sandreas.sandberg@arm.com 21312037Sandreas.sandberg@arm.com /** The iterator to the instruction's location inside the list. */ 21412391Sjason@lowepower.com ListIt listIt; 21512391Sjason@lowepower.com 21612037Sandreas.sandberg@arm.com /** A vector of any dependent instructions. */ 21711986Sandreas.sandberg@arm.com std::vector<MemDepEntryPtr> dependInsts; 21811986Sandreas.sandberg@arm.com 21911986Sandreas.sandberg@arm.com /** If the registers are ready or not. */ 22011986Sandreas.sandberg@arm.com bool regsReady; 22111986Sandreas.sandberg@arm.com /** If all memory dependencies have been satisfied. */ 22211986Sandreas.sandberg@arm.com bool memDepReady; 22311986Sandreas.sandberg@arm.com /** If the instruction is completed. */ 22411986Sandreas.sandberg@arm.com bool completed; 22511986Sandreas.sandberg@arm.com /** If the instruction is squashed. */ 22611986Sandreas.sandberg@arm.com bool squashed; 22711986Sandreas.sandberg@arm.com 22811986Sandreas.sandberg@arm.com /** For debugging. */ 22911986Sandreas.sandberg@arm.com#ifdef DEBUG 23011986Sandreas.sandberg@arm.com static int memdep_count; 23111986Sandreas.sandberg@arm.com static int memdep_insert; 23211986Sandreas.sandberg@arm.com static int memdep_erase; 23311986Sandreas.sandberg@arm.com#endif 23411986Sandreas.sandberg@arm.com }; 23511986Sandreas.sandberg@arm.com 23611986Sandreas.sandberg@arm.com /** Finds the memory dependence entry in the hash map. */ 23711986Sandreas.sandberg@arm.com inline MemDepEntryPtr &findInHash(const DynInstConstPtr& inst); 23811986Sandreas.sandberg@arm.com 23911986Sandreas.sandberg@arm.com /** Moves an entry to the ready list. */ 24011986Sandreas.sandberg@arm.com inline void moveToReady(MemDepEntryPtr &ready_inst_entry); 24111986Sandreas.sandberg@arm.com 242 typedef std::unordered_map<InstSeqNum, MemDepEntryPtr, SNHash> MemDepHash; 243 244 typedef typename MemDepHash::iterator MemDepHashIt; 245 246 /** A hash map of all memory dependence entries. */ 247 MemDepHash memDepHash; 248 249 /** A list of all instructions in the memory dependence unit. */ 250 std::list<DynInstPtr> instList[Impl::MaxThreads]; 251 252 /** A list of all instructions that are going to be replayed. */ 253 std::list<DynInstPtr> instsToReplay; 254 255 /** The memory dependence predictor. It is accessed upon new 256 * instructions being added to the IQ, and responds by telling 257 * this unit what instruction the newly added instruction is dependent 258 * upon. 259 */ 260 MemDepPred depPred; 261 262 /** Is there an outstanding load barrier that loads must wait on. */ 263 bool loadBarrier; 264 /** The sequence number of the load barrier. */ 265 InstSeqNum loadBarrierSN; 266 /** Is there an outstanding store barrier that loads must wait on. */ 267 bool storeBarrier; 268 /** The sequence number of the store barrier. */ 269 InstSeqNum storeBarrierSN; 270 271 /** Pointer to the IQ. */ 272 InstructionQueue<Impl> *iqPtr; 273 274 /** The thread id of this memory dependence unit. */ 275 int id; 276 277 /** Stat for number of inserted loads. */ 278 Stats::Scalar insertedLoads; 279 /** Stat for number of inserted stores. */ 280 Stats::Scalar insertedStores; 281 /** Stat for number of conflicting loads that had to wait for a store. */ 282 Stats::Scalar conflictingLoads; 283 /** Stat for number of conflicting stores that had to wait for a store. */ 284 Stats::Scalar conflictingStores; 285}; 286 287#endif // __CPU_O3_MEM_DEP_UNIT_HH__ 288