mem-cache: ReplacementPolicy specific replacement data

Replacement data is specific for each replacement policy, and thus
should be instantiated differently by each policy.

Touch() and reset() do not need to be aware of CacheBlk, as they
only update its ReplacementData.

Invalidate() makes replacement policies independent of cache blocks,
by removing the awareness of the valid state.

An inheritable base ReplaceableEntry class was created to allow usage
of replacement policies with any table-like structure.

Change-Id: I998917d800fa48504ed95abffa2f1b7bfd68522b
Reviewed-on: https://gem5-review.googlesource.com/9421
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

22 files changed, 646 insertions, 300 deletions

diff --git a/src/mem/cache/blk.hh b/src/mem/cache/blk.hh
index 65f32ff91..b57c61b63 100644
--- a/src/mem/cache/blk.hh
+++ b/src/mem/cache/blk.hh
@@ -51,6 +51,7 @@
 #include <list>
 
 #include "base/printable.hh"
+#include "mem/cache/replacement_policies/base.hh"
 #include "mem/packet.hh"
 #include "mem/request.hh"
 
@@ -76,7 +77,7 @@ enum CacheBlkStatusBits : unsigned {
  * A Basic Cache block.
  * Contains the tag, status, and a pointer to data.
  */
-class CacheBlk
+class CacheBlk : public ReplaceableEntry
 {
   public:
     /** Task Id associated with this block */
@@ -109,9 +110,9 @@ class CacheBlk
     int set, way;
 
     /**
-      * Whether this block has been touched since simulation started.
-      * Used to calculate number of used tags.
-      */
+     * Whether this block has been touched since simulation started.
+     * Used to calculate number of used tags.
+     */
     bool isTouched;
 
     /** Number of references to this block since it was brought in. */
@@ -123,17 +124,6 @@ class CacheBlk
     /** Tick on which the block was inserted in the cache. */
     Tick tickInserted;
 
-    /**
-     * Replacement policy data. As of now it is only an update timestamp.
-     * Tick on which the block was last touched.
-     */
-    Tick lastTouchTick;
-
-    /**
-     * Re-Reference Interval Prediction Value. Used with RRIP repl policy.
-     */
-    unsigned rrpv;
-
   protected:
     /**
      * Represents that the indicated thread context has a "lock" on
diff --git a/src/mem/cache/replacement_policies/ReplacementPolicies.py b/src/mem/cache/replacement_policies/ReplacementPolicies.py
index f2cee35d1..381f386ed 100644
--- a/src/mem/cache/replacement_policies/ReplacementPolicies.py
+++ b/src/mem/cache/replacement_policies/ReplacementPolicies.py
@@ -73,7 +73,7 @@ class BRRIPRP(BaseReplacementPolicy):
     type = 'BRRIPRP'
     cxx_class = 'BRRIPRP'
     cxx_header = "mem/cache/replacement_policies/brrip_rp.hh"
-    max_RRPV = Param.Unsigned(3, "Maximum RRPV possible")
+    max_RRPV = Param.Int(3, "Maximum RRPV possible")
     hit_priority = Param.Bool(False,
         "Prioritize evicting blocks that havent had a hit recently")
     btp = Param.Percent(3,
diff --git a/src/mem/cache/replacement_policies/SConscript b/src/mem/cache/replacement_policies/SConscript
index 8036ac7cb..74022feda 100644
--- a/src/mem/cache/replacement_policies/SConscript
+++ b/src/mem/cache/replacement_policies/SConscript
@@ -32,7 +32,6 @@ Import('*')
 
 SimObject('ReplacementPolicies.py')
 
-Source('base.cc')
 Source('bip_rp.cc')
 Source('brrip_rp.cc')
 Source('fifo_rp.cc')
diff --git a/src/mem/cache/replacement_policies/base.cc b/src/mem/cache/replacement_policies/base.cc
deleted file mode 100644
index c422a75d8..000000000
--- a/src/mem/cache/replacement_policies/base.cc
+++ /dev/null
@@ -1,66 +0,0 @@
-/**
- * Copyright (c) 2018 Inria
- * 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: Daniel Carvalho
- */
-
-/**
- * @file
- * Declaration of a common base class for cache replacement policy objects.
- * In general replacement policies try to use invalid entries as victims,
- * and if no such blocks exist the replacement policy is applied.
- */
-
-#include "mem/cache/replacement_policies/base.hh"
-
-BaseReplacementPolicy::BaseReplacementPolicy(const Params *p)
-    : SimObject(p)
-{
-}
-
-void
-BaseReplacementPolicy::touch(CacheBlk *blk)
-{
-    // Inform block has been touched
-    blk->isTouched = true;
-
-    // Update frequency counter
-    blk->refCount++;
-}
-
-void
-BaseReplacementPolicy::reset(CacheBlk *blk)
-{
-    // Inform block has been touched
-    blk->isTouched = true;
-
-    // Set insertion tick
-    blk->tickInserted = curTick();
-
-    // Reset frequency counter
-    blk->refCount = 0;
-}
diff --git a/src/mem/cache/replacement_policies/base.hh b/src/mem/cache/replacement_policies/base.hh
index 383f3f01a..0ce86d091 100644
--- a/src/mem/cache/replacement_policies/base.hh
+++ b/src/mem/cache/replacement_policies/base.hh
@@ -31,26 +31,37 @@
 #ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BASE_HH__
 #define __MEM_CACHE_REPLACEMENT_POLICIES_BASE_HH__
 
-#include "mem/cache/base.hh"
-#include "mem/cache/blk.hh"
+#include <memory>
+
 #include "params/BaseReplacementPolicy.hh"
 #include "sim/sim_object.hh"
 
 /**
+ * The replacement data needed by the replacement policy.
+ * Each replacement policy should have its own replacement data.
+ */
+struct ReplacementData {};
+
+/**
+ * A replaceable entry is used by any table-like structure that needs to
+ * implement replacement functionality. It provides the replacement data
+ * pointer instantiated and needed by the replacement policy used.
+ * @sa Replacement Policies
+ */
+class ReplaceableEntry
+{
+  public:
+    /**
+     * Replacement data associated to this entry.
+     * It is instantiated by the replacement policy.
+     */
+    std::shared_ptr<ReplacementData> replacementData;
+};
+
+/**
  * Replacement candidates as chosen by the indexing policy.
- *
- * The base functions touch() and reset() must be called by all subclasses
- * that override them.
- *
- * @todo
- *   Currently the replacement candidates are simply the cache blocks
- *   derived from the possible placement locations of an address, as
- *   defined by the getPossibleLocations() from BaseTags. In a future
- *   patch it should be an inheritable class to allow the replacement
- *   policies to be used with any table-like structure that needs to
- *   replace its entries.
  */
-typedef std::vector<CacheBlk*> ReplacementCandidates;
+typedef std::vector<ReplaceableEntry*> ReplacementCandidates;
 
 /**
  * A common base class of cache replacement policy objects.
@@ -66,7 +77,7 @@ class BaseReplacementPolicy : public SimObject
     /**
      * Construct and initiliaze this replacement policy.
      */
-    BaseReplacementPolicy(const Params *p);
+    BaseReplacementPolicy(const Params *p) : SimObject(p) {}
 
     /**
      * Destructor.
@@ -74,32 +85,44 @@ class BaseReplacementPolicy : public SimObject
     virtual ~BaseReplacementPolicy() {}
 
     /**
-     * Touch a block to update its replacement data.
-     * Updates number of references.
+     * Invalidate replacement data to set it as the next probable victim.
      *
-     * This base function must be called by all subclasses that override it.
-     *
-     * @param blk Cache block to be touched.
+     * @param replacement_data Replacement data to be invalidated.
      */
-    virtual void touch(CacheBlk *blk);
+    virtual void invalidate(const std::shared_ptr<ReplacementData>&
+                                                replacement_data) const = 0;
 
     /**
-     * Reset replacement data for a block. Used when a block is inserted.
-     * Sets the insertion tick, and update number of references.
+     * Update replacement data.
      *
-     * This base function must be called by all subclasses that override it.
+     * @param replacement_data Replacement data to be touched.
+     */
+    virtual void touch(const std::shared_ptr<ReplacementData>&
+                                                replacement_data) const = 0;
+
+    /**
+     * Reset replacement data. Used when it's holder is inserted/validated.
      *
-     * @param blk Cache block to be reset.
+     * @param replacement_data Replacement data to be reset.
      */
-    virtual void reset(CacheBlk *blk);
+    virtual void reset(const std::shared_ptr<ReplacementData>&
+                                                replacement_data) const = 0;
 
     /**
      * Find replacement victim among candidates.
      *
      * @param candidates Replacement candidates, selected by indexing policy.
-     * @return Cache block to be replaced.
+     * @return Replacement entry to be replaced.
+     */
+    virtual ReplaceableEntry* getVictim(
+                           const ReplacementCandidates& candidates) const = 0;
+
+    /**
+     * Instantiate a replacement data entry.
+     *
+     * @return A shared pointer to the new replacement data.
      */
-    virtual CacheBlk* getVictim(const ReplacementCandidates& candidates) = 0;
+    virtual std::shared_ptr<ReplacementData> instantiateEntry() = 0;
 };
 
 #endif // __MEM_CACHE_REPLACEMENT_POLICIES_BASE_HH__
diff --git a/src/mem/cache/replacement_policies/bip_rp.cc b/src/mem/cache/replacement_policies/bip_rp.cc
index 215711bb9..4a3a516f4 100644
--- a/src/mem/cache/replacement_policies/bip_rp.cc
+++ b/src/mem/cache/replacement_policies/bip_rp.cc
@@ -30,8 +30,9 @@
 
 #include "mem/cache/replacement_policies/bip_rp.hh"
 
+#include <memory>
+
 #include "base/random.hh"
-#include "debug/CacheRepl.hh"
 
 BIPRP::BIPRP(const Params *p)
     : LRURP(p), btp(p->btp)
@@ -39,16 +40,17 @@ BIPRP::BIPRP(const Params *p)
 }
 
 void
-BIPRP::reset(CacheBlk *blk)
+BIPRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
 {
-    BaseReplacementPolicy::reset(blk);
+    std::shared_ptr<LRUReplData> casted_replacement_data =
+        std::static_pointer_cast<LRUReplData>(replacement_data);
 
-    // Blocks are inserted as MRU if lower than btp, LRU otherwise
+    // Entries are inserted as MRU if lower than btp, LRU otherwise
     if (random_mt.random<unsigned>(1, 100) <= btp) {
-        blk->lastTouchTick = curTick();
+        casted_replacement_data->lastTouchTick = curTick();
     } else {
         // Make their timestamps as old as possible, so that they become LRU
-        blk->lastTouchTick = 0;
+        casted_replacement_data->lastTouchTick = 1;
     }
 }
 
diff --git a/src/mem/cache/replacement_policies/bip_rp.hh b/src/mem/cache/replacement_policies/bip_rp.hh
index f6e2a9c64..ac4db02e0 100644
--- a/src/mem/cache/replacement_policies/bip_rp.hh
+++ b/src/mem/cache/replacement_policies/bip_rp.hh
@@ -31,7 +31,7 @@
 /**
  * @file
  * Declaration of a Bimodal Interval Prediction replacement policy.
- * Has a probability of when placing new blocks, placing them as MRU.
+ * Has a probability of when placing new entries, placing them as MRU.
  *
  * Although both LRU and LIP can be seen as specific cases of BIP
  * where the bimodal throtle parameter are 1 and 0, respectively, we
@@ -41,8 +41,8 @@
  * In the original paper they use btp = 1/32 ~= 3%.
  */
 
-#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_LIP_RP_HH__
-#define __MEM_CACHE_REPLACEMENT_POLICIES_LIP_RP_HH__
+#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BIP_RP_HH__
+#define __MEM_CACHE_REPLACEMENT_POLICIES_BIP_RP_HH__
 
 #include "mem/cache/replacement_policies/lru_rp.hh"
 #include "params/BIPRP.hh"
@@ -52,7 +52,7 @@ class BIPRP : public LRURP
   protected:
     /**
      * Bimodal throtle parameter. Value in the range [0,100] used to decide
-     * if a new block is inserted at the MRU or LRU position.
+     * if a new entry is inserted at the MRU or LRU position.
      */
     const unsigned btp;
 
@@ -71,14 +71,14 @@ class BIPRP : public LRURP
     ~BIPRP() {}
 
     /**
-     * Reset replacement data for a block. Used when a block is inserted.
-     * Sets the insertion tick, and update correspondent replacement data.
-     * Uses the bimodal throtle parameter to decide whether the new block
+     * Reset replacement data for an entry. Used when an entry is inserted.
+     * Uses the bimodal throtle parameter to decide whether the new entry
      * should be inserted as MRU, or LRU.
      *
-     * @param blk Cache block to be reset.
+     * @param replacement_data Replacement data to be reset.
      */
-    void reset(CacheBlk *blk) override;
+    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
 };
 
-#endif // __MEM_CACHE_REPLACEMENT_POLICIES_LIP_RP_HH__
+#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BIP_RP_HH__
diff --git a/src/mem/cache/replacement_policies/brrip_rp.cc b/src/mem/cache/replacement_policies/brrip_rp.cc
index 9185638d7..846b4fb9c 100644
--- a/src/mem/cache/replacement_policies/brrip_rp.cc
+++ b/src/mem/cache/replacement_policies/brrip_rp.cc
@@ -30,88 +30,110 @@
 
 #include "mem/cache/replacement_policies/brrip_rp.hh"
 
+#include <memory>
+
+#include "base/logging.hh" // For fatal_if
 #include "base/random.hh"
-#include "debug/CacheRepl.hh"
 
 BRRIPRP::BRRIPRP(const Params *p)
     : BaseReplacementPolicy(p),
       maxRRPV(p->max_RRPV), hitPriority(p->hit_priority), btp(p->btp)
 {
-    if (maxRRPV == 0){
-        fatal("max_RRPV should be greater than zero.\n");
-    }
+    fatal_if(maxRRPV <= 0, "max_RRPV should be greater than zero.\n");
+}
+
+void
+BRRIPRP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+const
+{
+    std::shared_ptr<BRRIPReplData> casted_replacement_data =
+        std::static_pointer_cast<BRRIPReplData>(replacement_data);
+
+    // Set RRPV to an invalid distance
+    casted_replacement_data->rrpv = maxRRPV + 1;
 }
 
 void
-BRRIPRP::touch(CacheBlk *blk)
+BRRIPRP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
 {
-    BaseReplacementPolicy::touch(blk);
+    std::shared_ptr<BRRIPReplData> casted_replacement_data =
+        std::static_pointer_cast<BRRIPReplData>(replacement_data);
 
     // Update RRPV if not 0 yet
-    // Every hit in HP mode makes the block the last to be evicted, while
-    // in FP mode a hit makes the block less likely to be evicted
+    // Every hit in HP mode makes the entry the last to be evicted, while
+    // in FP mode a hit makes the entry less likely to be evicted
     if (hitPriority) {
-        blk->rrpv = 0;
-    } else if (blk->rrpv > 0) {
-        blk->rrpv--;
+        casted_replacement_data->rrpv = 0;
+    } else if (casted_replacement_data->rrpv > 0) {
+        casted_replacement_data->rrpv--;
     }
 }
 
 void
-BRRIPRP::reset(CacheBlk *blk)
+BRRIPRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
 {
-    BaseReplacementPolicy::reset(blk);
+    std::shared_ptr<BRRIPReplData> casted_replacement_data =
+        std::static_pointer_cast<BRRIPReplData>(replacement_data);
 
     // Reset RRPV
-    // Blocks are inserted as "long re-reference" if lower than btp,
+    // Replacement data is inserted as "long re-reference" if lower than btp,
     // "distant re-reference" otherwise
     if (random_mt.random<unsigned>(1, 100) <= btp) {
-        blk->rrpv = maxRRPV-1;
+        casted_replacement_data->rrpv = maxRRPV-1;
     } else {
-        blk->rrpv = maxRRPV;
+        casted_replacement_data->rrpv = maxRRPV;
     }
 }
 
-CacheBlk*
-BRRIPRP::getVictim(const ReplacementCandidates& candidates)
+ReplaceableEntry*
+BRRIPRP::getVictim(const ReplacementCandidates& candidates) const
 {
     // There must be at least one replacement candidate
     assert(candidates.size() > 0);
 
-    // Use visitor to search for the victim
-    CacheBlk* blk = candidates[0];
+    // Use first candidate as dummy victim
+    ReplaceableEntry* victim = candidates[0];
+
+    // Store victim->rrpv in a variable to improve code readability
+    int victim_RRPV = std::static_pointer_cast<BRRIPReplData>(
+                        victim->replacementData)->rrpv;
+
+    // Visit all candidates to find victim
     for (const auto& candidate : candidates) {
-        // Stop iteration if found an invalid block
-        if (!candidate->isValid()) {
-            blk = candidate;
-            blk->rrpv = maxRRPV;
-            break;
-        // Update victim block if necessary
-        } else if (candidate->rrpv > blk->rrpv) {
-            blk = candidate;
+        // Get candidate's rrpv
+        int candidate_RRPV = std::static_pointer_cast<BRRIPReplData>(
+                                    candidate->replacementData)->rrpv;
+
+        // Stop searching for victims if an invalid entry is found
+        if (candidate_RRPV == maxRRPV + 1) {
+            return candidate;
+        // Update victim entry if necessary
+        } else if (candidate_RRPV > victim_RRPV) {
+            victim = candidate;
+            victim_RRPV = candidate_RRPV;
         }
     }
 
-    // Make sure we don't have an invalid rrpv
-    assert(blk->rrpv <= maxRRPV);
-
-    // Get difference of block's RRPV to the highest possible RRPV in
-    // order to update the RRPV of all the other blocks accordingly
-    unsigned diff = maxRRPV - blk->rrpv;
+    // Get difference of victim's RRPV to the highest possible RRPV in
+    // order to update the RRPV of all the other entries accordingly
+    int diff = maxRRPV - victim_RRPV;
 
     // No need to update RRPV if there is no difference
     if (diff > 0){
         // Update RRPV of all candidates
         for (const auto& candidate : candidates) {
-            // Update the block's RPPV with the new value
-            candidate->rrpv += diff;
+            std::static_pointer_cast<BRRIPReplData>(
+                candidate->replacementData)->rrpv += diff;
         }
     }
 
-    DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
-            blk->set, blk->way);
+    return victim;
+}
 
-    return blk;
+std::shared_ptr<ReplacementData>
+BRRIPRP::instantiateEntry()
+{
+    return std::shared_ptr<ReplacementData>(new BRRIPReplData(maxRRPV));
 }
 
 BRRIPRP*
diff --git a/src/mem/cache/replacement_policies/brrip_rp.hh b/src/mem/cache/replacement_policies/brrip_rp.hh
index 489b81ec0..e442d85ce 100644
--- a/src/mem/cache/replacement_policies/brrip_rp.hh
+++ b/src/mem/cache/replacement_policies/brrip_rp.hh
@@ -33,22 +33,22 @@
  * Declaration of a Re-Reference Interval Prediction replacement policy.
  *
  * Not-Recently Used (NRU) is an approximation of LRU that uses a single bit
- * to determine if a block is going to be re-referenced in the near or distant
+ * to determine if an entry is going to be re-referenced in the near or distant
  * future.
  *
  * Re-Reference Interval Prediction (RRIP) is an extension of NRU that uses a
- * re-reference prediction value to determine if blocks are going to be re-
+ * re-reference prediction value to determine if entries are going to be re-
  * used in the near future or not.
  *
- * The higher the value of the RRPV, the more distant the block is from
- * its next access.
+ * The higher the value of the RRPV, the more distant the entry is from its
+ * next access.
  *
  * Bimodal Re-Reference Interval Prediction (BRRIP) is an extension of RRIP
- * that has a probability of not inserting blocks as the LRU. This probability
+ * that has a probability of not inserting entries as the LRU. This probability
  * is controlled by the bimodal throtle parameter (btp).
  *
  * From the original paper, this implementation of RRIP is also called
- * Static RRIP (SRRIP), as it always inserts blocks with the same RRPV.
+ * Static RRIP (SRRIP), as it always inserts entries with the same RRPV.
  */
 
 #ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__
@@ -60,25 +60,40 @@
 class BRRIPRP : public BaseReplacementPolicy
 {
   protected:
+    /** BRRIP-specific implementation of replacement data. */
+    struct BRRIPReplData : ReplacementData
+    {
+        /**
+         * Re-Reference Interval Prediction Value.
+         * A value equal to max_RRPV + 1 indicates an invalid entry.
+         */
+        int rrpv;
+
+        /**
+         * Default constructor. Invalidate data.
+         */
+        BRRIPReplData(const int max_RRPV) : rrpv(max_RRPV + 1) {}
+    };
+
     /**
-     * Maximum Re-Reference Prediction Value possible. A block with this
+     * Maximum Re-Reference Prediction Value possible. An entry with this
      * value as the rrpv has the longest possible re-reference interval,
      * that is, it is likely not to be used in the near future, and is
      * among the best eviction candidates.
      * A maxRRPV of 1 implies in a NRU.
      */
-    const unsigned maxRRPV;
+    const int maxRRPV;
 
     /**
-     * The hit priority (HP) policy replaces blocks that do not receive cache
-     * hits over any cache block that receives a hit, while the frequency
-     * priority (FP) policy replaces infrequently re-referenced blocks.
+     * The hit priority (HP) policy replaces entries that do not receive cache
+     * hits over any cache entry that receives a hit, while the frequency
+     * priority (FP) policy replaces infrequently re-referenced entries.
      */
     const bool hitPriority;
 
     /**
      * Bimodal throtle parameter. Value in the range [0,100] used to decide
-     * if a new block is inserted with long or distant re-reference.
+     * if a new entry is inserted with long or distant re-reference.
      */
     const unsigned btp;
 
@@ -97,28 +112,46 @@ class BRRIPRP : public BaseReplacementPolicy
     ~BRRIPRP() {}
 
     /**
-     * Touch a block to update its replacement data.
+     * Invalidate replacement data to set it as the next probable victim.
+     * Set RRPV as the the most distant re-reference.
+     *
+     * @param replacement_data Replacement data to be invalidated.
+     */
+    void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+                                                              const override;
+
+    /**
+     * Touch an entry to update its replacement data.
      *
-     * @param blk Cache block to be touched.
+     * @param replacement_data Replacement data to be touched.
      */
-    void touch(CacheBlk *blk) override;
+    void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
 
     /**
-     * Reset replacement data for a block. Used when a block is inserted.
-     * Sets the insertion tick, and update correspondent replacement data.
+     * Reset replacement data. Used when an entry is inserted.
      * Set RRPV according to the insertion policy used.
      *
-     * @param blk Cache block to be reset.
+     * @param replacement_data Replacement data to be reset.
      */
-    void reset(CacheBlk *blk) override;
+    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
 
     /**
      * Find replacement victim using rrpv.
      *
      * @param cands Replacement candidates, selected by indexing policy.
-     * @return Cache block to be replaced.
+     * @return Replacement entry to be replaced.
+     */
+    ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
+                                                                     override;
+
+    /**
+     * Instantiate a replacement data entry.
+     *
+     * @return A shared pointer to the new replacement data.
      */
-    CacheBlk* getVictim(const ReplacementCandidates& candidates) override;
+    std::shared_ptr<ReplacementData> instantiateEntry() override;
 };
 
 #endif // __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__
diff --git a/src/mem/cache/replacement_policies/fifo_rp.cc b/src/mem/cache/replacement_policies/fifo_rp.cc
index fd320be83..731945a0a 100644
--- a/src/mem/cache/replacement_policies/fifo_rp.cc
+++ b/src/mem/cache/replacement_policies/fifo_rp.cc
@@ -30,36 +30,61 @@
 
 #include "mem/cache/replacement_policies/fifo_rp.hh"
 
-#include "debug/CacheRepl.hh"
+#include <memory>
 
 FIFORP::FIFORP(const Params *p)
     : BaseReplacementPolicy(p)
 {
 }
 
-CacheBlk*
-FIFORP::getVictim(const ReplacementCandidates& candidates)
+void
+FIFORP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+const
+{
+    // Reset insertion tick
+    std::static_pointer_cast<FIFOReplData>(
+        replacement_data)->tickInserted = Tick(0);
+}
+
+void
+FIFORP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+    // A touch does not modify the insertion tick
+}
+
+void
+FIFORP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+    // Set insertion tick
+    std::static_pointer_cast<FIFOReplData>(
+        replacement_data)->tickInserted = curTick();
+}
+
+ReplaceableEntry*
+FIFORP::getVictim(const ReplacementCandidates& candidates) const
 {
     // There must be at least one replacement candidate
     assert(candidates.size() > 0);
 
     // Visit all candidates to find victim
-    CacheBlk* blk = candidates[0];
+    ReplaceableEntry* victim = candidates[0];
     for (const auto& candidate : candidates) {
-        // Stop iteration if found an invalid block
-        if (!candidate->isValid()) {
-            blk = candidate;
-            break;
-        // Update victim block if necessary
-        } else if (candidate->tickInserted < blk->tickInserted) {
-            blk = candidate;
+        // Update victim entry if necessary
+        if (std::static_pointer_cast<FIFOReplData>(
+                    candidate->replacementData)->tickInserted <
+                std::static_pointer_cast<FIFOReplData>(
+                    victim->replacementData)->tickInserted) {
+            victim = candidate;
         }
     }
 
-    DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
-            blk->set, blk->way);
+    return victim;
+}
 
-    return blk;
+std::shared_ptr<ReplacementData>
+FIFORP::instantiateEntry()
+{
+    return std::shared_ptr<ReplacementData>(new FIFOReplData());
 }
 
 FIFORP*
diff --git a/src/mem/cache/replacement_policies/fifo_rp.hh b/src/mem/cache/replacement_policies/fifo_rp.hh
index 16493711c..a686b449b 100644
--- a/src/mem/cache/replacement_policies/fifo_rp.hh
+++ b/src/mem/cache/replacement_policies/fifo_rp.hh
@@ -31,7 +31,7 @@
 /**
  * @file
  * Declaration of a First In First Out replacement policy.
- * The victim is chosen using the timestamp. The oldest block is always chosen
+ * The victim is chosen using the timestamp. The oldest entry is always chosen
  * to be evicted, regardless of the amount of times it has been touched.
  */
 
@@ -43,6 +43,18 @@
 
 class FIFORP : public BaseReplacementPolicy
 {
+    /** FIFO-specific implementation of replacement data. */
+    struct FIFOReplData : ReplacementData
+    {
+        /** Tick on which the entry was inserted. */
+        Tick tickInserted;
+
+        /**
+         * Default constructor. Invalidate data.
+         */
+        FIFOReplData() : tickInserted(0) {}
+    };
+
   public:
     /** Convenience typedef. */
     typedef FIFORPParams Params;
@@ -58,12 +70,47 @@ class FIFORP : public BaseReplacementPolicy
     ~FIFORP() {}
 
     /**
+     * Invalidate replacement data to set it as the next probable victim.
+     * Reset insertion tick to 0.
+     *
+     * @param replacement_data Replacement data to be invalidated.
+     */
+    void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+                                                              const override;
+
+    /**
+     * Touch an entry to update its replacement data.
+     * Does not modify the replacement data.
+     *
+     * @param replacement_data Replacement data to be touched.
+     */
+    void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
+
+    /**
+     * Reset replacement data. Used when an entry is inserted.
+     * Sets its insertion tick.
+     *
+     * @param replacement_data Replacement data to be reset.
+     */
+    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
+
+    /**
      * Find replacement victim using insertion timestamps.
      *
      * @param cands Replacement candidates, selected by indexing policy.
-     * @return Cache block to be replaced.
+     * @return Replacement entry to be replaced.
+     */
+    ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
+                                                                     override;
+
+    /**
+     * Instantiate a replacement data entry.
+     *
+     * @return A shared pointer to the new replacement data.
      */
-    CacheBlk* getVictim(const ReplacementCandidates& cands) override;
+    std::shared_ptr<ReplacementData> instantiateEntry() override;
 };
 
 #endif // __MEM_CACHE_REPLACEMENT_POLICIES_FIFO_RP_HH__
diff --git a/src/mem/cache/replacement_policies/lfu_rp.cc b/src/mem/cache/replacement_policies/lfu_rp.cc
index 90a5ee227..ffa653e87 100644
--- a/src/mem/cache/replacement_policies/lfu_rp.cc
+++ b/src/mem/cache/replacement_policies/lfu_rp.cc
@@ -30,36 +30,60 @@
 
 #include "mem/cache/replacement_policies/lfu_rp.hh"
 
-#include "debug/CacheRepl.hh"
+#include <memory>
 
 LFURP::LFURP(const Params *p)
     : BaseReplacementPolicy(p)
 {
 }
 
-CacheBlk*
-LFURP::getVictim(const ReplacementCandidates& candidates)
+void
+LFURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+const
+{
+    // Reset reference count
+    std::static_pointer_cast<LFUReplData>(replacement_data)->refCount = 0;
+}
+
+void
+LFURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+    // Update reference count
+    std::static_pointer_cast<LFUReplData>(replacement_data)->refCount++;
+}
+
+void
+LFURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+    // Reset reference count
+    std::static_pointer_cast<LFUReplData>(replacement_data)->refCount = 1;
+}
+
+ReplaceableEntry*
+LFURP::getVictim(const ReplacementCandidates& candidates) const
 {
     // There must be at least one replacement candidate
     assert(candidates.size() > 0);
 
     // Visit all candidates to find victim
-    CacheBlk* blk = candidates[0];
+    ReplaceableEntry* victim = candidates[0];
     for (const auto& candidate : candidates) {
-        // Stop iteration if found an invalid block
-        if (!candidate->isValid()) {
-            blk = candidate;
-            break;
-        // Update victim block if necessary
-        } else if (candidate->refCount < blk->refCount) {
-            blk = candidate;
+        // Update victim entry if necessary
+        if (std::static_pointer_cast<LFUReplData>(
+                    candidate->replacementData)->refCount <
+                std::static_pointer_cast<LFUReplData>(
+                    victim->replacementData)->refCount) {
+            victim = candidate;
         }
     }
 
-    DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
-            blk->set, blk->way);
+    return victim;
+}
 
-    return blk;
+std::shared_ptr<ReplacementData>
+LFURP::instantiateEntry()
+{
+    return std::shared_ptr<ReplacementData>(new LFUReplData());
 }
 
 LFURP*
diff --git a/src/mem/cache/replacement_policies/lfu_rp.hh b/src/mem/cache/replacement_policies/lfu_rp.hh
index affc849a2..8709e35d4 100644
--- a/src/mem/cache/replacement_policies/lfu_rp.hh
+++ b/src/mem/cache/replacement_policies/lfu_rp.hh
@@ -32,7 +32,7 @@
  * @file
  * Declaration of a Least Frequently Used replacement policy.
  * The victim is chosen using the reference frequency. The least referenced
- * block is always chosen to be evicted, regardless of the amount of times
+ * entry is always chosen to be evicted, regardless of the amount of times
  * it has been touched, or how long has passed since its last touch.
  */
 
@@ -44,6 +44,19 @@
 
 class LFURP : public BaseReplacementPolicy
 {
+  protected:
+    /** LFU-specific implementation of replacement data. */
+    struct LFUReplData : ReplacementData
+    {
+        /** Number of references to this entry since it was reset. */
+        unsigned refCount;
+
+        /**
+         * Default constructor. Invalidate data.
+         */
+        LFUReplData() : refCount(0) {}
+    };
+
   public:
     /** Convenience typedef. */
     typedef LFURPParams Params;
@@ -59,12 +72,47 @@ class LFURP : public BaseReplacementPolicy
     ~LFURP() {}
 
     /**
+     * Invalidate replacement data to set it as the next probable victim.
+     * Clear the number of references.
+     *
+     * @param replacement_data Replacement data to be invalidated.
+     */
+    void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+                                                              const override;
+
+    /**
+     * Touch an entry to update its replacement data.
+     * Increase number of references.
+     *
+     * @param replacement_data Replacement data to be touched.
+     */
+    void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
+
+    /**
+     * Reset replacement data. Used when an entry is inserted.
+     * Reset number of references.
+     *
+     * @param replacement_data Replacement data to be reset.
+     */
+    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
+
+    /**
      * Find replacement victim using reference frequency.
      *
      * @param cands Replacement candidates, selected by indexing policy.
-     * @return Cache block to be replaced.
+     * @return Replacement entry to be replaced.
+     */
+    ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
+                                                                     override;
+
+    /**
+     * Instantiate a replacement data entry.
+     *
+     * @return A shared pointer to the new replacement data.
      */
-    CacheBlk* getVictim(const ReplacementCandidates& candidates) override;
+    std::shared_ptr<ReplacementData> instantiateEntry() override;
 };
 
 #endif // __MEM_CACHE_REPLACEMENT_POLICIES_LFU_RP_HH__
diff --git a/src/mem/cache/replacement_policies/lru_rp.cc b/src/mem/cache/replacement_policies/lru_rp.cc
index b2fa20b6f..99e35db19 100644
--- a/src/mem/cache/replacement_policies/lru_rp.cc
+++ b/src/mem/cache/replacement_policies/lru_rp.cc
@@ -30,7 +30,7 @@
 
 #include "mem/cache/replacement_policies/lru_rp.hh"
 
-#include "debug/CacheRepl.hh"
+#include <memory>
 
 LRURP::LRURP(const Params *p)
     : BaseReplacementPolicy(p)
@@ -38,46 +38,55 @@ LRURP::LRURP(const Params *p)
 }
 
 void
-LRURP::touch(CacheBlk *blk)
+LRURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+const
 {
-    BaseReplacementPolicy::touch(blk);
+    // Reset last touch timestamp
+    std::static_pointer_cast<LRUReplData>(
+        replacement_data)->lastTouchTick = Tick(0);
+}
 
+void
+LRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
     // Update last touch timestamp
-    blk->lastTouchTick = curTick();
+    std::static_pointer_cast<LRUReplData>(
+        replacement_data)->lastTouchTick = curTick();
 }
 
 void
-LRURP::reset(CacheBlk *blk)
+LRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
 {
-    BaseReplacementPolicy::reset(blk);
-
     // Set last touch timestamp
-    blk->lastTouchTick = blk->tickInserted;
+    std::static_pointer_cast<LRUReplData>(
+        replacement_data)->lastTouchTick = curTick();
 }
 
-CacheBlk*
-LRURP::getVictim(const ReplacementCandidates& candidates)
+ReplaceableEntry*
+LRURP::getVictim(const ReplacementCandidates& candidates) const
 {
     // There must be at least one replacement candidate
     assert(candidates.size() > 0);
 
     // Visit all candidates to find victim
-    CacheBlk* blk = candidates[0];
+    ReplaceableEntry* victim = candidates[0];
     for (const auto& candidate : candidates) {
-        // Stop iteration if found an invalid block
-        if (!candidate->isValid()) {
-            blk = candidate;
-            break;
-        // Update victim block if necessary
-        } else if (candidate->lastTouchTick < blk->lastTouchTick) {
-            blk = candidate;
+        // Update victim entry if necessary
+        if (std::static_pointer_cast<LRUReplData>(
+                    candidate->replacementData)->lastTouchTick <
+                std::static_pointer_cast<LRUReplData>(
+                    victim->replacementData)->lastTouchTick) {
+            victim = candidate;
         }
     }
 
-    DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
-            blk->set, blk->way);
+    return victim;
+}
 
-    return blk;
+std::shared_ptr<ReplacementData>
+LRURP::instantiateEntry()
+{
+    return std::shared_ptr<ReplacementData>(new LRUReplData());
 }
 
 LRURP*
diff --git a/src/mem/cache/replacement_policies/lru_rp.hh b/src/mem/cache/replacement_policies/lru_rp.hh
index 2dd7e86f0..e8e708f1c 100644
--- a/src/mem/cache/replacement_policies/lru_rp.hh
+++ b/src/mem/cache/replacement_policies/lru_rp.hh
@@ -43,6 +43,19 @@
 
 class LRURP : public BaseReplacementPolicy
 {
+  protected:
+    /** LRU-specific implementation of replacement data. */
+    struct LRUReplData : ReplacementData
+    {
+        /** Tick on which the entry was last touched. */
+        Tick lastTouchTick;
+
+        /**
+         * Default constructor. Invalidate data.
+         */
+        LRUReplData() : lastTouchTick(0) {}
+    };
+
   public:
     /** Convenience typedef. */
     typedef LRURPParams Params;
@@ -58,27 +71,47 @@ class LRURP : public BaseReplacementPolicy
     ~LRURP() {}
 
     /**
-     * Touch a block to update its last touch tick.
+     * Invalidate replacement data to set it as the next probable victim.
+     * Sets its last touch tick as the starting tick.
      *
-     * @param blk Cache block to be touched.
+     * @param replacement_data Replacement data to be invalidated.
      */
-    void touch(CacheBlk *blk) override;
+    void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+                                                              const override;
 
     /**
-     * Reset replacement data for a block. Used when a block is inserted.
+     * Touch an entry to update its replacement data.
      * Sets its last touch tick as the current tick.
      *
-     * @param blk Cache block to be reset.
+     * @param replacement_data Replacement data to be touched.
      */
-    void reset(CacheBlk *blk) override;
+    void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
+
+    /**
+     * Reset replacement data. Used when an entry is inserted.
+     * Sets its last touch tick as the current tick.
+     *
+     * @param replacement_data Replacement data to be reset.
+     */
+    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
 
     /**
      * Find replacement victim using LRU timestamps.
      *
      * @param candidates Replacement candidates, selected by indexing policy.
-     * @return Cache block to be replaced.
+     * @return Replacement entry to be replaced.
+     */
+    ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
+                                                                     override;
+
+    /**
+     * Instantiate a replacement data entry.
+     *
+     * @return A shared pointer to the new replacement data.
      */
-    CacheBlk* getVictim(const ReplacementCandidates& candidates) override;
+    std::shared_ptr<ReplacementData> instantiateEntry() override;
 };
 
 #endif // __MEM_CACHE_REPLACEMENT_POLICIES_LRU_RP_HH__
diff --git a/src/mem/cache/replacement_policies/mru_rp.cc b/src/mem/cache/replacement_policies/mru_rp.cc
index f4cf014ae..ff84fc368 100644
--- a/src/mem/cache/replacement_policies/mru_rp.cc
+++ b/src/mem/cache/replacement_policies/mru_rp.cc
@@ -30,7 +30,7 @@
 
 #include "mem/cache/replacement_policies/mru_rp.hh"
 
-#include "debug/CacheRepl.hh"
+#include <memory>
 
 MRURP::MRURP(const Params *p)
     : BaseReplacementPolicy(p)
@@ -38,46 +38,55 @@ MRURP::MRURP(const Params *p)
 }
 
 void
-MRURP::touch(CacheBlk *blk)
+MRURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+const
 {
-    BaseReplacementPolicy::touch(blk);
+    // Reset last touch timestamp
+    std::static_pointer_cast<MRUReplData>(
+        replacement_data)->lastTouchTick = Tick(0);
+}
 
+void
+MRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
     // Update last touch timestamp
-    blk->lastTouchTick = curTick();
+    std::static_pointer_cast<MRUReplData>(
+        replacement_data)->lastTouchTick = curTick();
 }
 
 void
-MRURP::reset(CacheBlk *blk)
+MRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
 {
-    BaseReplacementPolicy::reset(blk);
-
     // Set last touch timestamp
-    blk->lastTouchTick = blk->tickInserted;
+    std::static_pointer_cast<MRUReplData>(
+        replacement_data)->lastTouchTick = curTick();
 }
 
-CacheBlk*
-MRURP::getVictim(const ReplacementCandidates& candidates)
+ReplaceableEntry*
+MRURP::getVictim(const ReplacementCandidates& candidates) const
 {
     // There must be at least one replacement candidate
     assert(candidates.size() > 0);
 
     // Visit all candidates to find victim
-    CacheBlk* blk = candidates[0];
+    ReplaceableEntry* victim = candidates[0];
     for (const auto& candidate : candidates) {
-        // Stop iteration if found an invalid block
-        if (!candidate->isValid()) {
-            blk = candidate;
-            break;
-        // Update victim block if necessary
-        } else if (candidate->lastTouchTick > blk->lastTouchTick) {
-            blk = candidate;
+        // Update victim entry if necessary
+        if (std::static_pointer_cast<MRUReplData>(
+                    candidate->replacementData)->lastTouchTick >
+                std::static_pointer_cast<MRUReplData>(
+                    victim->replacementData)->lastTouchTick) {
+            victim = candidate;
         }
     }
 
-    DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
-            blk->set, blk->way);
+    return victim;
+}
 
-    return blk;
+std::shared_ptr<ReplacementData>
+MRURP::instantiateEntry()
+{
+    return std::shared_ptr<ReplacementData>(new MRUReplData());
 }
 
 MRURP*
diff --git a/src/mem/cache/replacement_policies/mru_rp.hh b/src/mem/cache/replacement_policies/mru_rp.hh
index fd9a29dff..11cc272a4 100644
--- a/src/mem/cache/replacement_policies/mru_rp.hh
+++ b/src/mem/cache/replacement_policies/mru_rp.hh
@@ -31,7 +31,7 @@
 /**
  * @file
  * Declaration of a Most Recently Used replacement policy.
- * The victim is chosen using the timestamp. The block that was accessed the
+ * The victim is chosen using the timestamp. The entry that was accessed the
  * last is the one chosen to be replaced.
  */
 
@@ -43,6 +43,19 @@
 
 class MRURP : public BaseReplacementPolicy
 {
+  protected:
+    /** MRU-specific implementation of replacement data. */
+    struct MRUReplData : ReplacementData
+    {
+        /** Tick on which the entry was last touched. */
+        Tick lastTouchTick;
+
+        /**
+         * Default constructor. Invalidate data.
+         */
+        MRUReplData() : lastTouchTick(0) {}
+    };
+
   public:
     /** Convenience typedef. */
     typedef MRURPParams Params;
@@ -58,26 +71,47 @@ class MRURP : public BaseReplacementPolicy
     ~MRURP() {}
 
     /**
-     * Touch a block to update its last touch tick.
+     * Invalidate replacement data to set it as the next probable victim.
+     * Sets its last touch tick as the starting tick.
+     *
+     * @param replacement_data Replacement data to be invalidated.
+     */
+    void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+                                                              const override;
+
+    /**
+     * Touch an entry to update its replacement data.
+     * Sets its last touch tick as the current tick.
      *
-     * @param blk Cache block to be touched.
+     * @param replacement_data Replacement data to be touched.
      */
-    void touch(CacheBlk *blk) override;
+    void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
 
     /**
-     * Reset replacement data for a block. Used when a block is inserted.
+     * Reset replacement data. Used when an entry is inserted.
      * Sets its last touch tick as the current tick.
      *
-     * @param blk Cache block to be reset.
+     * @param replacement_data Replacement data to be reset.
      */
-    void reset(CacheBlk *blk) override;
+    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
 
     /**
      * Find replacement victim using access timestamps.
+     *
      * @param cands Replacement candidates, selected by indexing policy.
-     * @return Cache block to be replaced.
+     * @return Replacement entry to be replaced.
+     */
+    ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
+                                                                     override;
+
+    /**
+     * Instantiate a replacement data entry.
+     *
+     * @return A shared pointer to the new replacement data.
      */
-    CacheBlk* getVictim(const ReplacementCandidates& candidates) override;
+    std::shared_ptr<ReplacementData> instantiateEntry() override;
 };
 
 #endif // __MEM_CACHE_REPLACEMENT_POLICIES_MRU_RP_HH__
diff --git a/src/mem/cache/replacement_policies/random_rp.cc b/src/mem/cache/replacement_policies/random_rp.cc
index 1c54bdac6..24e64fc90 100644
--- a/src/mem/cache/replacement_policies/random_rp.cc
+++ b/src/mem/cache/replacement_policies/random_rp.cc
@@ -31,37 +31,62 @@
 #include "mem/cache/replacement_policies/random_rp.hh"
 
 #include "base/random.hh"
-#include "debug/CacheRepl.hh"
+#include "mem/cache/blk.hh"
 
 RandomRP::RandomRP(const Params *p)
     : BaseReplacementPolicy(p)
 {
 }
 
-CacheBlk*
-RandomRP::getVictim(const ReplacementCandidates& candidates)
+void
+RandomRP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+const
+{
+    // Unprioritize replacement data victimization
+    std::static_pointer_cast<RandomReplData>(
+        replacement_data)->valid = false;
+}
+
+void
+RandomRP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+}
+
+void
+RandomRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+    // Unprioritize replacement data victimization
+    std::static_pointer_cast<RandomReplData>(
+        replacement_data)->valid = true;
+}
+
+ReplaceableEntry*
+RandomRP::getVictim(const ReplacementCandidates& candidates) const
 {
     // There must be at least one replacement candidate
     assert(candidates.size() > 0);
 
     // Choose one candidate at random
-    CacheBlk* blk = candidates[random_mt.random<unsigned>(0,
+    ReplaceableEntry* victim = candidates[random_mt.random<unsigned>(0,
                                     candidates.size() - 1)];
 
-    // Visit all candidates to find an invalid entry
+    // Visit all candidates to search for an invalid entry. If one is found,
+    // its eviction is prioritized
     for (const auto& candidate : candidates) {
-        // Give priority to victimise invalid entries
-        if (!candidate->isValid()){
-            blk = candidate;
+        if (!std::static_pointer_cast<RandomReplData>(
+                    candidate->replacementData)->valid) {
+            victim = candidate;
             break;
         }
     }
 
-    // If no invalid blocks were found, choose one of the candidates randomly
-    DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
-            blk->set, blk->way);
+    return victim;
+}
 
-    return blk;
+std::shared_ptr<ReplacementData>
+RandomRP::instantiateEntry()
+{
+    return std::shared_ptr<ReplacementData>(new ReplacementData());
 }
 
 RandomRP*
diff --git a/src/mem/cache/replacement_policies/random_rp.hh b/src/mem/cache/replacement_policies/random_rp.hh
index 338b26ff2..5514961b6 100644
--- a/src/mem/cache/replacement_policies/random_rp.hh
+++ b/src/mem/cache/replacement_policies/random_rp.hh
@@ -42,6 +42,22 @@
 
 class RandomRP : public BaseReplacementPolicy
 {
+  protected:
+    /** MRU-specific implementation of replacement data. */
+    struct RandomReplData : ReplacementData
+    {
+        /**
+         * Flag informing if the replacement data is valid or not.
+         * Invalid entries are prioritized to be evicted.
+         */
+        bool valid;
+
+        /**
+         * Default constructor. Invalidate data.
+         */
+        RandomReplData() : valid(false) {}
+    };
+
   public:
     /** Convenience typedef. */
     typedef RandomRPParams Params;
@@ -57,11 +73,47 @@ class RandomRP : public BaseReplacementPolicy
     ~RandomRP() {}
 
     /**
+     * Invalidate replacement data to set it as the next probable victim.
+     * Prioritize replacement data for victimization.
+     *
+     * @param replacement_data Replacement data to be invalidated.
+     */
+    void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+                                                               const override;
+
+    /**
+     * Touch an entry to update its replacement data.
+     * Does not do anything.
+     *
+     * @param replacement_data Replacement data to be touched.
+     */
+    void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
+
+    /**
+     * Reset replacement data. Used when an entry is inserted.
+     * Unprioritize replacement data for victimization.
+     *
+     * @param replacement_data Replacement data to be reset.
+     */
+    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+                                                                     override;
+
+    /**
      * Find replacement victim at random.
+     *
      * @param candidates Replacement candidates, selected by indexing policy.
-     * @return Cache block to be replaced.
+     * @return Replacement entry to be replaced.
+     */
+    ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
+                                                                     override;
+
+    /**
+     * Instantiate a replacement data entry.
+     *
+     * @return A shared pointer to the new replacement data.
      */
-    CacheBlk* getVictim(const ReplacementCandidates& candidates) override;
+    std::shared_ptr<ReplacementData> instantiateEntry() override;
 };
 
 #endif // __MEM_CACHE_REPLACEMENT_POLICIES_RANDOM_RP_HH__
diff --git a/src/mem/cache/tags/base.cc b/src/mem/cache/tags/base.cc
index d48acfbe1..2f8d428c7 100644
--- a/src/mem/cache/tags/base.cc
+++ b/src/mem/cache/tags/base.cc
@@ -100,6 +100,11 @@ BaseTags::insertBlock(PacketPtr pkt, CacheBlk *blk)
         blk->invalidate();
     }
 
+    // Touch block
+    blk->isTouched = true;
+    blk->refCount = 1;
+    blk->tickInserted = curTick();
+
     // Previous block, if existed, has been removed, and now we have
     // to insert the new one
     tagsInUse++;
diff --git a/src/mem/cache/tags/base_set_assoc.cc b/src/mem/cache/tags/base_set_assoc.cc
index f0ee2a5d8..5888d1f00 100644
--- a/src/mem/cache/tags/base_set_assoc.cc
+++ b/src/mem/cache/tags/base_set_assoc.cc
@@ -50,7 +50,6 @@
 #include <string>
 
 #include "base/intmath.hh"
-#include "sim/core.hh"
 
 BaseSetAssoc::BaseSetAssoc(const Params *p)
     :BaseTags(p), assoc(p->assoc), allocAssoc(p->assoc),
@@ -92,6 +91,9 @@ BaseSetAssoc::BaseSetAssoc(const Params *p)
             // Associate a data chunk to the block
             blk->data = &dataBlks[blkSize*blkIndex];
 
+            // Associate a replacement data entry to the block
+            blk->replacementData = replacementPolicy->instantiateEntry();
+
             // Setting the tag to j is just to prevent long chains in the
             // hash table; won't matter because the block is invalid
             blk->tag = j;
@@ -106,6 +108,15 @@ BaseSetAssoc::BaseSetAssoc(const Params *p)
     }
 }
 
+void
+BaseSetAssoc::invalidate(CacheBlk *blk)
+{
+    BaseTags::invalidate(blk);
+
+    // Invalidate replacement data
+    replacementPolicy->invalidate(blk->replacementData);
+}
+
 CacheBlk*
 BaseSetAssoc::findBlock(Addr addr, bool is_secure) const
 {
diff --git a/src/mem/cache/tags/base_set_assoc.hh b/src/mem/cache/tags/base_set_assoc.hh
index 024fda157..5a3e832c1 100644
--- a/src/mem/cache/tags/base_set_assoc.hh
+++ b/src/mem/cache/tags/base_set_assoc.hh
@@ -50,11 +50,12 @@
 
 #include <cassert>
 #include <cstring>
-#include <memory>
 #include <vector>
 
+#include "debug/CacheRepl.hh"
 #include "mem/cache/base.hh"
 #include "mem/cache/blk.hh"
+#include "mem/cache/replacement_policies/base.hh"
 #include "mem/cache/tags/base.hh"
 #include "mem/cache/tags/cacheset.hh"
 #include "mem/packet.hh"
@@ -105,7 +106,6 @@ class BaseSetAssoc : public BaseTags
     BaseReplacementPolicy *replacementPolicy;
 
   public:
-
     /** Convenience typedef. */
      typedef BaseSetAssocParams Params;
 
@@ -120,6 +120,14 @@ class BaseSetAssoc : public BaseTags
     virtual ~BaseSetAssoc() {};
 
     /**
+     * This function updates the tags when a block is invalidated but does
+     * not invalidate the block itself. It also updates the replacement data.
+     *
+     * @param blk The block to invalidate.
+     */
+    void invalidate(CacheBlk *blk) override;
+
+    /**
      * Find the cache block given set and way
      * @param set The set of the block.
      * @param way The way of the block.
@@ -165,8 +173,11 @@ class BaseSetAssoc : public BaseTags
                 accessLatency;
             }
 
+            // Update number of references to accessed block
+            blk->refCount++;
+
             // Update replacement data of accessed block
-            replacementPolicy->touch(blk);
+            replacementPolicy->touch(blk->replacementData);
         } else {
             // If a cache miss
             lat = lookupLatency;
@@ -193,8 +204,18 @@ class BaseSetAssoc : public BaseTags
      */
     CacheBlk* findVictim(Addr addr) override
     {
+        // Get possible locations for the victim block
+        std::vector<CacheBlk*> locations = getPossibleLocations(addr);
+
         // Choose replacement victim from replacement candidates
-        return replacementPolicy->getVictim(getPossibleLocations(addr));
+        CacheBlk* victim = static_cast<CacheBlk*>(replacementPolicy->getVictim(
+                               std::vector<ReplaceableEntry*>(
+                                   locations.begin(), locations.end())));
+
+        DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
+            victim->set, victim->way);
+
+        return victim;
     }
 
     /**
@@ -223,7 +244,7 @@ class BaseSetAssoc : public BaseTags
         BaseTags::insertBlock(pkt, blk);
 
         // Update replacement policy
-        replacementPolicy->reset(blk);
+        replacementPolicy->reset(blk->replacementData);
     }
 
     /**