Improve hit rate of opcode cache to compensate for not mutating insn list

2 files changed, 58 insertions, 17 deletions

diff --git a/riscv/processor.cc b/riscv/processor.cc
index c8cb5be..a813068 100644
--- a/riscv/processor.cc
+++ b/riscv/processor.cc
@@ -1064,6 +1064,12 @@ reg_t processor_t::get_csr(int which, insn_t insn, bool write, bool peek)
   throw trap_illegal_instruction(insn.bits());
 }
 
+const insn_desc_t insn_desc_t::illegal_instruction = {
+  0, 0,
+  &::illegal_instruction, &::illegal_instruction, &::illegal_instruction, &::illegal_instruction,
+  &::illegal_instruction, &::illegal_instruction, &::illegal_instruction, &::illegal_instruction
+};
+
 reg_t illegal_instruction(processor_t UNUSED *p, insn_t insn, reg_t UNUSED pc)
 {
   // The illegal instruction can be longer than ILEN bits, where the tval will
@@ -1076,11 +1082,11 @@ insn_func_t processor_t::decode_insn(insn_t insn)
 {
   // look up opcode in hash table
   size_t idx = insn.bits() % OPCODE_CACHE_SIZE;
-  insn_desc_t desc = opcode_cache[idx];
+  auto [hit, desc] = opcode_cache[idx].lookup(insn.bits());
 
   bool rve = extension_enabled('E');
 
-  if (unlikely(insn.bits() != desc.match)) {
+  if (unlikely(!hit)) {
     // fall back to linear search
     auto matching = [insn_bits = insn.bits()](const insn_desc_t &d) {
       return (insn_bits & d.mask) == d.match;
@@ -1091,12 +1097,11 @@ insn_func_t processor_t::decode_insn(insn_t insn)
       p = std::find_if(instructions.begin(), instructions.end(), matching);
       assert(p != instructions.end());
     }
-    desc = *p;
-    opcode_cache[idx] = desc;
-    opcode_cache[idx].match = insn.bits();
+    desc = &*p;
+    opcode_cache[idx].replace(insn.bits(), desc);
   }
 
-  return desc.func(xlen, rve, log_commits_enabled);
+  return desc->func(xlen, rve, log_commits_enabled);
 }
 
 void processor_t::register_insn(insn_desc_t desc, bool is_custom) {
@@ -1112,7 +1117,7 @@ void processor_t::register_insn(insn_desc_t desc, bool is_custom) {
 void processor_t::build_opcode_map()
 {
   for (size_t i = 0; i < OPCODE_CACHE_SIZE; i++)
-    opcode_cache[i] = insn_desc_t::illegal();
+    opcode_cache[i].reset();
 }
 
 void processor_t::register_extension(extension_t *x) {
@@ -1190,7 +1195,7 @@ void processor_t::register_base_instructions()
   #undef DEFINE_INSN
 
   // terminate instruction list with a catch-all
-  register_base_insn(insn_desc_t::illegal());
+  register_base_insn(insn_desc_t::illegal_instruction);
 
   build_opcode_map();
 }
diff --git a/riscv/processor.h b/riscv/processor.h
index c03c3ef..9b776e2 100644
--- a/riscv/processor.h
+++ b/riscv/processor.h
@@ -43,7 +43,7 @@ struct insn_desc_t
   insn_func_t logged_rv32e;
   insn_func_t logged_rv64e;
 
-  insn_func_t func(int xlen, bool rve, bool logged)
+  insn_func_t func(int xlen, bool rve, bool logged) const
   {
     if (logged)
       if (rve)
@@ -57,12 +57,7 @@ struct insn_desc_t
         return xlen == 64 ? fast_rv64i : fast_rv32i;
   }
 
-  static insn_desc_t illegal()
-  {
-    return {0, 0,
-            &illegal_instruction, &illegal_instruction, &illegal_instruction, &illegal_instruction,
-            &illegal_instruction, &illegal_instruction, &illegal_instruction, &illegal_instruction};
-  }
+  static const insn_desc_t illegal_instruction;
 };
 
 // regnum, data
@@ -196,6 +191,47 @@ struct state_t
   elp_t elp;
 };
 
+class opcode_cache_entry_t {
+ public:
+  opcode_cache_entry_t()
+  {
+    reset();
+  }
+
+  void reset()
+  {
+    for (size_t i = 0; i < associativity; i++) {
+      tag[i] = 0;
+      contents[i] = &insn_desc_t::illegal_instruction;
+    }
+  }
+
+  void replace(insn_bits_t opcode, const insn_desc_t* desc)
+  {
+    for (size_t i = associativity - 1; i > 0; i--) {
+      tag[i] = tag[i-1];
+      contents[i] = contents[i-1];
+    }
+
+    tag[0] = opcode;
+    contents[0] = desc;
+  }
+
+  std::tuple<bool, const insn_desc_t*> lookup(insn_bits_t opcode)
+  {
+    for (size_t i = 0; i < associativity; i++)
+      if (tag[i] == opcode)
+        return std::tuple(true, contents[i]);
+
+    return std::tuple(false, nullptr);
+  }
+
+ private:
+  static const size_t associativity = 4;
+  insn_bits_t tag[associativity];
+  const insn_desc_t* contents[associativity];
+};
+
 // this class represents one processor in a RISC-V machine.
 class processor_t : public abstract_device_t
 {
@@ -351,8 +387,8 @@ private:
   std::vector<insn_desc_t> custom_instructions;
   std::unordered_map<reg_t,uint64_t> pc_histogram;
 
-  static const size_t OPCODE_CACHE_SIZE = 8191;
-  insn_desc_t opcode_cache[OPCODE_CACHE_SIZE];
+  static const size_t OPCODE_CACHE_SIZE = 4095;
+  opcode_cache_entry_t opcode_cache[OPCODE_CACHE_SIZE];
 
   void take_pending_interrupt() { take_interrupt(state.mip->read() & state.mie->read()); }
   void take_interrupt(reg_t mask); // take first enabled interrupt in mask