mem-cache: Use SatCounter for RRPV

Use SatCounter in RRIP's RRPV. As such, move validation functionality
to a proper variable.

Change-Id: I142db2b7f6cd518ac3a2b68c9ed48005402b3464
Signed-off-by: Daniel R. Carvalho <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/20452
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>
Tested-by: kokoro <noreply+kokoro@google.com>

mem-cache: Fix non-virtual base destructor of Repl Entry

ReplaceableEntry contains a virtual method, yet its destructor
was not virtual, causing errors in some compilers.

Change-Id: I13deec843f4007d9deb924882a8d98ff6a89c84f
Signed-off-by: Daniel R. Carvalho <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/19808
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Tested-by: kokoro <noreply+kokoro@google.com>

mem-cache: Fix set and way of sub-entries

Set and way of sub-entries were not being set previously.
They must be set after the sub-blocks have been assigned
to the main block.

Change-Id: I7b6921b8437b29c472d691cd78cf20f2bb6c7e07
Signed-off-by: Daniel R. Carvalho <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/19669
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Tested-by: kokoro <noreply+kokoro@google.com>

mem-cache: Fix RRPV for RRIP

The RRPV values for RRIP and NRU replacment policies.
Long re-rereference interval was used instead of
distant re-rereference interval and vice-versa.
The btp value permit to choose beetwen distant and
long insertion ratio. A btp value of 0 force the
policy to always insert at a distant re-reference
interval and a btp value of 100 force the policy to
always insert at a long (intermediate) re-rereference
interval.

Change-Id: I516098f73942b769dcc31fe0edfe07c3e9c3effd
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/17851
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

mem-cache: Add missing includes in TreePLRU

Add missing includes to TreePLRU files.

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

mem-cache: Factor ReplaceableEntry out

ReplaceableEntry is referenced by many classes that do
not necessarily need access to the replacement policies.
Therefore, in order to allow better compilation units,
we factor it out to a new file.

Change-Id: I0823567bf1ca336ffcdf783682ef473e8878d7fd
Signed-off-by: Daniel R. Carvalho <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/13418
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

mem-cache: Create Tree-PLRU replacement policy

Implementation of a Tree-PLRU replacement policy. It is based on
the assumption that a set associative cache is used.

Change-Id: I74b227e88fd6c93aab5bb2cd0e8730376db28f52
Reviewed-on: https://gem5-review.googlesource.com/c/11106
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>

mem-cache: Use set and way for ReplaceableEntry

Replaceable entries belong to table-like structures, and therefore
they should be indexable by combining a row and a column. These,
using conventional cache nomenclature translate to sets and ways.

Make these entries aware of their sets and ways. The idea is to
make indexing policies usable by other table-like structures. In
order to do so we move sets and ways to ReplaceableEntry, which
will be the common base among table entries.

Change-Id: If0e3dacf9ea2f523af9cface067469ccecf82648
Reviewed-on: https://gem5-review.googlesource.com/c/12764
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>

mem-cache: Fix include directives in the cache related classes

Change-Id: I111b0f662897c43974aadb08da1ed85c7542585c
Reviewed-on: https://gem5-review.googlesource.com/10433
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

mem-cache: Fix RandomReplData

Random replacement policy's data was being instantiated with
the incorrect class.

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

mem-cache: Create Second-Chance replacement policy

Implementation of a Second-Chance replacement policy. Similar to FIFO,
but every block is given a second chance if it has been touched.

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

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>

mem-cache: Create NRU Replacement Policy

Implementation of a Not Recently Used replacement policy.

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

mem-cache: Create LIP Replacement Policy

Implementation of a LRU Insertion Policy replacement policy.

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

mem-cache: Create BIP Replacement Policy

Implementation of a Bimodal Insertion Policy replacement policy.

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

mem-cache: Create LFU replacement policy

Implementation of a Least Frequently Used replacement policy.

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

mem-cache: Create RRIP Replacement Policy

Implementation of a Re-Reference Interval Prediction replacement
policy.

Change-Id: Iba716eb5df2bf2be156e765f889d94f6ad00c91b
Reviewed-on: https://gem5-review.googlesource.com/8981
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>

mem-cache: Create BRRIP replacement policy

Implementation of a Bimodal Re-Reference Interval Prediction
replacement policy.

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

mem-cache: fix missing overrides in repl policies

Change-Id: I67759a4532e8a46c1643d4c3a9c546ad6b565b81
Signed-off-by: Jason Lowe-Power <jason@lowepower.com>
Reviewed-on: https://gem5-review.googlesource.com/9321
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

mem-cache: Create FIFO replacement policy

Implementation of a First-In, First-Out replacement policy.

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

mem-cache: Fix MRU rebase

Rebase of MRU missed a const qualifier, introducing a compilation
error.

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

mem-cache: Create MRU replacement policy

Implementation of a Most Recently Used replacement policy.

Change-Id: Id52cb247ca25d4523dcc53490d113695dac6a3f1
Reviewed-on: https://gem5-review.googlesource.com/8889
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

mem-cache: Split array indexing and replacement policies.

Replacement policies (LRU, Random) are currently considered as array
indexing methods, but have completely different functionalities:

- Array indexers determine the possible locations for block allocation.
This information is used to generate replacement candidates when
conflicts happen.
- Replacement policies determine which of the replacement candidates
should be evicted to make room for new allocations.

For this reason, they were split into different classes. Advantages:

- Easier and more straightforward to implement other replacement
policies (RRIP, LFU, ARC, ...)
- Allow easier future implementation of cache organization schemes

As now we can't assure the use of sets, the previous way to create a
true LRU is not viable. Now a timestamp_bits parameter controls how
many bits are dedicated for the timestamp, and a true LRU can be
achieved through an infinite number of bits (although a few bits suffice
in practice).

Change-Id: I23750db121f1474d17831137e6ff618beb2b3eda
Reviewed-on: https://gem5-review.googlesource.com/8501
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>