Implement LRU as simple priority queue with linear insert sort.

Signed-off-by: Pavel Pisa <pisa@cmp.felk.cvut.cz>

2 files changed, 41 insertions, 33 deletions

diff --git a/qtmips_machine/cache.cpp b/qtmips_machine/cache.cpp
index 30771b0..231aa81 100644
--- a/qtmips_machine/cache.cpp
+++ b/qtmips_machine/cache.cpp
@@ -51,7 +51,7 @@ Cache::Cache(MemoryAccess  *m, const MachineConfigCache *cc, unsigned memory_acc
     dt = nullptr;
     replc.lfu = nullptr;
     replc.lru = nullptr;
-    p_change_counter = new std::uint32_t(0);
+    change_counter = 0;
 
     // Skip any other initialization if cache is disabled
     if (!cc->enabled())
@@ -82,7 +82,7 @@ Cache::Cache(MemoryAccess  *m, const MachineConfigCache *cc, unsigned memory_acc
         for (unsigned int row = 0; row < cnf.sets(); row++) {
             replc.lru[row] = new unsigned int[cnf.associativity()];
             for (unsigned int i = 0; i < cnf.associativity(); i++)
-                replc.lru[row][i] = 0;
+                replc.lru[row][i] = i;
         }
         break;
     case MachineConfigCache::RP_RAND:
@@ -92,7 +92,6 @@ Cache::Cache(MemoryAccess  *m, const MachineConfigCache *cc, unsigned memory_acc
 }
 
 Cache::~Cache(){
-    delete p_change_counter;
     if (dt != nullptr) {
         for (unsigned i = 0; i < cnf.associativity(); i++) {
 	    if (dt[i]) {
@@ -160,7 +159,7 @@ void Cache::flush() {
     if (!cnf.enabled())
         return;
 
-    for (unsigned as = 0; as < cnf.associativity(); as++)
+    for (unsigned as = cnf.associativity(); as-- > 0 ; )
         for (unsigned st = 0; st < cnf.sets(); st++)
             if (dt[as][st].valid)
                 kick(as, st);
@@ -268,6 +267,11 @@ bool Cache::access(std::uint32_t address, std::uint32_t *data, bool write, std::
         case MachineConfigCache::RP_RAND:
             indx = rand() % cnf.associativity();
             break;
+        case MachineConfigCache::RP_LRU:
+            {
+                indx = replc.lru[row][0];
+                break;
+            }
         case MachineConfigCache::RP_LFU:
             {
                 unsigned lowest = replc.lfu[row][0];
@@ -284,23 +288,6 @@ bool Cache::access(std::uint32_t address, std::uint32_t *data, bool write, std::
                 }
                 break;
             }
-        case MachineConfigCache::RP_LRU:
-            {
-                unsigned int least = 0xffff;
-                indx = 0;
-                for (unsigned i = 0; i < cnf.associativity(); i++) {
-                    if (!dt[i][row].valid) {
-                        // found free one, use it directly
-                        indx = i;
-                        break;
-                    }
-                    if (least < replc.lru[row][i]) {
-                        least = replc.lru[row][i];
-                        indx = i;
-                    }
-                }
-                break;
-            }
         }
     }
     SANITY_ASSERT(indx < cnf.associativity(), "Probably unimplemented replacement policy");
@@ -310,7 +297,7 @@ bool Cache::access(std::uint32_t address, std::uint32_t *data, bool write, std::
     // Verify if we are not replacing
     if (cd.valid && cd.tag != tag) {
         kick(indx, row);
-        (*p_change_counter)++;
+        change_counter++;
     }
 
     // Update statistics and otherwise read from memory
@@ -330,20 +317,27 @@ bool Cache::access(std::uint32_t address, std::uint32_t *data, bool write, std::
         update_statistics();
         for (unsigned i = 0; i < cnf.blocks(); i++) {
             cd.data[i] = mem->read_word(base_address(tag, row) + (4*i));
-            (*p_change_counter)++;
+            change_counter++;
         }
     }
 
     // Update replcement data
     switch (cnf.replacement_policy()) {
-    case MachineConfigCache::RP_LFU:
-        if (cd.valid && replc.lru[row][indx] == 0)
-            break;
-        for (unsigned i = 1; i < cnf.associativity(); i++)
-            replc.lru[row][i]++;
-        replc.lru[row][indx] = 0;
-        break;
     case MachineConfigCache::RP_LRU:
+    {
+        unsigned next_asi = indx;
+        int i = cnf.associativity() - 1;
+        unsigned tmp_asi = replc.lru[row][i];
+        while (tmp_asi != indx) {
+            SANITY_ASSERT(i >= 0, "LRU lost the way from priority queue - access");
+            tmp_asi = replc.lru[row][i];
+            replc.lru[row][i] = next_asi;
+            next_asi = tmp_asi;
+            i--;
+        }
+        break;
+    }
+    case MachineConfigCache::RP_LFU:
         replc.lfu[row][indx]++;
         break;
     default:
@@ -362,7 +356,7 @@ bool Cache::access(std::uint32_t address, std::uint32_t *data, bool write, std::
 
     emit cache_update(indx, row, cd.valid, cd.dirty, cd.tag, cd.data);
     if (changed)
-        (*p_change_counter)++;
+        change_counter++;
     return changed;
 }
 
@@ -375,6 +369,20 @@ void Cache::kick(unsigned associat_indx, unsigned row) const {
     cd.dirty = false;
 
     switch (cnf.replacement_policy()) {
+    case MachineConfigCache::RP_LRU:
+    {
+        unsigned next_asi = associat_indx;
+        unsigned tmp_asi = replc.lru[row][0];
+        int i = 1;
+        while (tmp_asi != associat_indx) {
+            SANITY_ASSERT(i < (int)cnf.associativity(), "LRU lost the way from priority queue - kick");
+            tmp_asi = replc.lru[row][i];
+            replc.lru[row][i] = next_asi;
+            next_asi = tmp_asi;
+            i++;
+        }
+        break;
+    }
     case MachineConfigCache::RP_LFU:
         break;
     default:
diff --git a/qtmips_machine/cache.h b/qtmips_machine/cache.h
index 200f3ce..827631b 100644
--- a/qtmips_machine/cache.h
+++ b/qtmips_machine/cache.h
@@ -67,7 +67,7 @@ public:
     enum LocationStatus location_status(std::uint32_t address) const;
 
     inline std::uint32_t get_change_counter() const {
-        return *p_change_counter;
+        return change_counter;
     }
 signals:
     void hit_update(unsigned) const;
@@ -76,7 +76,6 @@ signals:
     void cache_update(unsigned associat, unsigned set, bool valid, bool dirty, std::uint32_t tag, const std::uint32_t *data) const;
 
 private:
-    std::uint32_t* p_change_counter;
     MachineConfigCache cnf;
     MemoryAccess *mem;
     unsigned access_pen_r, access_pen_w;
@@ -96,6 +95,7 @@ private:
     } replc; // Data used for replacement policy
 
     mutable unsigned hit_read, miss_read, hit_write, miss_write; // Hit and miss counters
+    mutable std::uint32_t change_counter;
 
     std::uint32_t debug_rword(std::uint32_t address) const;
     bool access(std::uint32_t address, std::uint32_t *data, bool write, std::uint32_t value = 0) const;