Merge pull request #1687 from riscv-software-src/flw-overlap

Separate RV32 and RV64 C instructions into separate files

13 files changed, 179 insertions, 124 deletions

diff --git a/riscv/check-opcode-overlap.t.cc b/riscv/check-opcode-overlap.t.cc
index 2922001..e1a3b06 100644
--- a/riscv/check-opcode-overlap.t.cc
+++ b/riscv/check-opcode-overlap.t.cc
@@ -1,6 +1,6 @@
 #include "decode.h"
 #include "common.h"
-#include <unordered_set>
+#include <unordered_map>
 #include <vector>
 #include <string>
 #include <cstdio>
@@ -11,13 +11,9 @@ struct opcode {
   std::string name;
 };
 
-static void check_overlap(const opcode& a, const opcode& b)
+static bool overlaps(const opcode& a, const opcode& b)
 {
-  if ((a.match & b.mask) == b.match) {
-    fprintf(stderr, "Instruction %s (%" PRIx64 ") overlaps instruction %s (%" PRIx64 ", mask %" PRIx64 ")\n",
-            a.name.c_str(), a.match, b.name.c_str(), b.match, b.mask);
-    exit(-1);
-  }
+  return (a.mask & b.mask & (a.match ^ b.match)) == 0;
 }
 
 int main()
@@ -34,24 +30,47 @@ int main()
     #undef DEFINE_INSN
   };
 
-  std::unordered_set<std::string> overlap_list;
+  std::unordered_map<std::string, bool> overlap_list;
   #define DECLARE_OVERLAP_INSN(name, ext) \
-    overlap_list.insert(std::string(#name));
+    overlap_list[std::string(#name)] = false;
     #include "overlap_list.h"
   #undef DECLARE_OVERLAP_INSN
 
   std::vector<const opcode*> list;
-  for (size_t i = 0; i < sizeof(static_list) / sizeof(static_list[0]); i++) {
+  for (size_t i = 0; i < std::size(static_list); i++) {
     if (!overlap_list.count(static_list[i].name))
       list.push_back(&static_list[i]);
   }
 
+  bool ok = true;
+
   for (size_t i = 1; i < list.size(); i++) {
     for (size_t j = 0; j < i; j++) {
-      check_overlap(*list[i], *list[j]);
-      check_overlap(*list[j], *list[i]);
+      if (overlaps(*list[i], *list[j])) {
+        fprintf(stderr, "Instruction %s (%" PRIx64 ") overlaps instruction %s (%" PRIx64 ", mask %" PRIx64 ")\n",
+                list[i]->name.c_str(), list[i]->match, list[j]->name.c_str(), list[j]->match, list[j]->mask);
+        ok = false;
+      }
+    }
+  }
+
+  // make sure nothing in the overlap list is unused
+  for (size_t i = 1; i < std::size(static_list); i++) {
+    for (size_t j = 0; j < i; j++) {
+      if (overlaps(static_list[i], static_list[j])) {
+        overlap_list[static_list[i].name] = true;
+        overlap_list[static_list[j].name] = true;
+      }
+    }
+  }
+
+  for (auto const& [name, used] : overlap_list) {
+    if (!used) {
+      fprintf(stderr, "Instruction %s overlaps nothing, so overlap list entry has no effect\n",
+              name.c_str());
+      ok = false;
     }
   }
 
-  return 0;
+  return ok ? 0 : -1;
 }
diff --git a/riscv/insns/c_flw.h b/riscv/insns/c_flw.h
index 95ae260..aa64bf1 100644
--- a/riscv/insns/c_flw.h
+++ b/riscv/insns/c_flw.h
@@ -1,8 +1,3 @@
-if (xlen == 32) {
-  require_extension(EXT_ZCF);
-  require_fp;
-  WRITE_RVC_FRS2S(f32(MMU.load<uint32_t>(RVC_RS1S + insn.rvc_lw_imm())));
-} else { // c.ld
-  require_extension(EXT_ZCA);
-  WRITE_RVC_RS2S(MMU.load<int64_t>(RVC_RS1S + insn.rvc_ld_imm()));
-}
+require_extension(EXT_ZCF);
+require_fp;
+WRITE_RVC_FRS2S(f32(MMU.load<uint32_t>(RVC_RS1S + insn.rvc_lw_imm())));
diff --git a/riscv/insns/c_flwsp.h b/riscv/insns/c_flwsp.h
index eea0ec5..caea77c 100644
--- a/riscv/insns/c_flwsp.h
+++ b/riscv/insns/c_flwsp.h
@@ -1,9 +1,3 @@
-if (xlen == 32) {
-  require_extension(EXT_ZCF);
-  require_fp;
-  WRITE_FRD(f32(MMU.load<uint32_t>(RVC_SP + insn.rvc_lwsp_imm())));
-} else { // c.ldsp
-  require_extension(EXT_ZCA);
-  require(insn.rvc_rd() != 0);
-  WRITE_RD(MMU.load<int64_t>(RVC_SP + insn.rvc_ldsp_imm()));
-}
+require_extension(EXT_ZCF);
+require_fp;
+WRITE_FRD(f32(MMU.load<uint32_t>(RVC_SP + insn.rvc_lwsp_imm())));
diff --git a/riscv/insns/c_fsw.h b/riscv/insns/c_fsw.h
index d7d6fed..dda411a 100644
--- a/riscv/insns/c_fsw.h
+++ b/riscv/insns/c_fsw.h
@@ -1,8 +1,3 @@
-if (xlen == 32) {
-  require_extension(EXT_ZCF);
-  require_fp;
-  MMU.store<uint32_t>(RVC_RS1S + insn.rvc_lw_imm(), RVC_FRS2S.v[0]);
-} else { // c.sd
-  require_extension(EXT_ZCA);
-  MMU.store<uint64_t>(RVC_RS1S + insn.rvc_ld_imm(), RVC_RS2S);
-}
+require_extension(EXT_ZCF);
+require_fp;
+MMU.store<uint32_t>(RVC_RS1S + insn.rvc_lw_imm(), RVC_FRS2S.v[0]);
diff --git a/riscv/insns/c_fswsp.h b/riscv/insns/c_fswsp.h
index 5952251..6ea5c05 100644
--- a/riscv/insns/c_fswsp.h
+++ b/riscv/insns/c_fswsp.h
@@ -1,8 +1,3 @@
-if (xlen == 32) {
-  require_extension(EXT_ZCF);
-  require_fp;
-  MMU.store<uint32_t>(RVC_SP + insn.rvc_swsp_imm(), RVC_FRS2.v[0]);
-} else { // c.sdsp
-  require_extension(EXT_ZCA);
-  MMU.store<uint64_t>(RVC_SP + insn.rvc_sdsp_imm(), RVC_RS2);
-}
+require_extension(EXT_ZCF);
+require_fp;
+MMU.store<uint32_t>(RVC_SP + insn.rvc_swsp_imm(), RVC_FRS2.v[0]);
diff --git a/riscv/insns/c_ld.h b/riscv/insns/c_ld.h
new file mode 100644
index 0000000..988ea98
--- /dev/null
+++ b/riscv/insns/c_ld.h
@@ -0,0 +1,2 @@
+require_extension(EXT_ZCA);
+WRITE_RVC_RS2S(MMU.load<int64_t>(RVC_RS1S + insn.rvc_ld_imm()));
diff --git a/riscv/insns/c_ldsp.h b/riscv/insns/c_ldsp.h
new file mode 100644
index 0000000..f196040
--- /dev/null
+++ b/riscv/insns/c_ldsp.h
@@ -0,0 +1,3 @@
+require_extension(EXT_ZCA);
+require(insn.rvc_rd() != 0);
+WRITE_RD(MMU.load<int64_t>(RVC_SP + insn.rvc_ldsp_imm()));
diff --git a/riscv/insns/c_sd.h b/riscv/insns/c_sd.h
new file mode 100644
index 0000000..ff8f77d
--- /dev/null
+++ b/riscv/insns/c_sd.h
@@ -0,0 +1,2 @@
+require_extension(EXT_ZCA);
+MMU.store<uint64_t>(RVC_RS1S + insn.rvc_ld_imm(), RVC_RS2S);
diff --git a/riscv/insns/c_sdsp.h b/riscv/insns/c_sdsp.h
new file mode 100644
index 0000000..f7b8a28
--- /dev/null
+++ b/riscv/insns/c_sdsp.h
@@ -0,0 +1,2 @@
+require_extension(EXT_ZCA);
+MMU.store<uint64_t>(RVC_SP + insn.rvc_sdsp_imm(), RVC_RS2);
diff --git a/riscv/overlap_list.h b/riscv/overlap_list.h
index 04ae443..253be45 100644
--- a/riscv/overlap_list.h
+++ b/riscv/overlap_list.h
@@ -1,6 +1,10 @@
-DECLARE_OVERLAP_INSN(c_fsdsp, EXT_ZCD)
-DECLARE_OVERLAP_INSN(c_fld, EXT_ZCD)
-DECLARE_OVERLAP_INSN(c_fldsp, EXT_ZCD)
+// these overlap c.ld[sp]/c.sd[sp]
+DECLARE_OVERLAP_INSN(c_flw, EXT_ZCF)
+DECLARE_OVERLAP_INSN(c_flwsp, EXT_ZCF)
+DECLARE_OVERLAP_INSN(c_fsw, EXT_ZCF)
+DECLARE_OVERLAP_INSN(c_fswsp, EXT_ZCF)
+
+// these overlap c.fsdsp
 DECLARE_OVERLAP_INSN(cm_push, EXT_ZCMP)
 DECLARE_OVERLAP_INSN(cm_pop, EXT_ZCMP)
 DECLARE_OVERLAP_INSN(cm_popret, EXT_ZCMP)
@@ -8,20 +12,23 @@ DECLARE_OVERLAP_INSN(cm_popretz, EXT_ZCMP)
 DECLARE_OVERLAP_INSN(cm_mva01s, EXT_ZCMP)
 DECLARE_OVERLAP_INSN(cm_mvsa01, EXT_ZCMP)
 DECLARE_OVERLAP_INSN(cm_jalt, EXT_ZCMT)
-DECLARE_OVERLAP_INSN(c_fsd, EXT_ZCD)
+
+// c.ebreak and c.jalr overlap c.add
 DECLARE_OVERLAP_INSN(c_ebreak, EXT_ZCA)
 DECLARE_OVERLAP_INSN(c_jalr, EXT_ZCA)
+
+// c.jr overlaps c.mv
 DECLARE_OVERLAP_INSN(c_jr, EXT_ZCA)
-DECLARE_OVERLAP_INSN(vaesdf_vv, EXT_ZVKNED)
-DECLARE_OVERLAP_INSN(vghsh_vv, EXT_ZVKG)
-DECLARE_OVERLAP_INSN(vsha2ms_vv, EXT_ZVKNHA)
-DECLARE_OVERLAP_INSN(vsha2ms_vv, EXT_ZVKNHB)
-DECLARE_OVERLAP_INSN(vsm3me_vv, EXT_ZVKSH)
+
+// lpad overlaps auipc
 DECLARE_OVERLAP_INSN(lpad, EXT_ZICFILP)
-DECLARE_OVERLAP_INSN(mop_r_28, EXT_ZIMOP)
-DECLARE_OVERLAP_INSN(mop_r_N, EXT_ZIMOP)
-DECLARE_OVERLAP_INSN(mop_rr_7, EXT_ZIMOP)
-DECLARE_OVERLAP_INSN(mop_rr_N, EXT_ZIMOP)
+
+// these overlap Zimop/Zcmop
+DECLARE_OVERLAP_INSN(ssrdp, EXT_ZICFISS)
+DECLARE_OVERLAP_INSN(sspush_x1, EXT_ZICFISS)
+DECLARE_OVERLAP_INSN(sspush_x5, EXT_ZICFISS)
+DECLARE_OVERLAP_INSN(sspopchk_x1, EXT_ZICFISS)
+DECLARE_OVERLAP_INSN(sspopchk_x5, EXT_ZICFISS)
 DECLARE_OVERLAP_INSN(c_sspush_x1, EXT_ZICFISS)
 DECLARE_OVERLAP_INSN(c_sspopchk_x5, EXT_ZICFISS)
 DECLARE_OVERLAP_INSN(c_mop_N, EXT_ZCMOP)
diff --git a/riscv/processor.cc b/riscv/processor.cc
index a1cec6c..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
@@ -1072,51 +1078,30 @@ reg_t illegal_instruction(processor_t UNUSED *p, insn_t insn, reg_t UNUSED pc)
   throw trap_illegal_instruction(insn.bits() & 0xffffffffULL);
 }
 
-static insn_desc_t
-propagate_instruction_in_vector(std::vector<insn_desc_t> &instructions,
-                                std::vector<insn_desc_t>::iterator it) {
-  assert(it != instructions.end());
-  insn_desc_t desc = *it;
-  if (it->mask != 0 && it != instructions.begin() &&
-      std::next(it) != instructions.end()) {
-    if (it->match != std::prev(it)->match &&
-        it->match != std::next(it)->match) {
-      // move to front of opcode list to reduce miss penalty
-      while (--it >= instructions.begin())
-        *std::next(it) = *it;
-      instructions[0] = desc;
-    }
-  }
-  return desc;
-}
-
 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;
     };
     auto p = std::find_if(custom_instructions.begin(),
                           custom_instructions.end(), matching);
-    if (p != custom_instructions.end()) {
-      desc = propagate_instruction_in_vector(custom_instructions, p);
-    } else {
+    if (p == custom_instructions.end()) {
       p = std::find_if(instructions.begin(), instructions.end(), matching);
       assert(p != instructions.end());
-      desc = propagate_instruction_in_vector(instructions, 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) {
@@ -1131,19 +1116,8 @@ void processor_t::register_insn(insn_desc_t desc, bool is_custom) {
 
 void processor_t::build_opcode_map()
 {
-  struct cmp {
-    bool operator()(const insn_desc_t& lhs, const insn_desc_t& rhs) {
-      if (lhs.match == rhs.match)
-        return lhs.mask > rhs.mask;
-      return lhs.match > rhs.match;
-    }
-  };
-
-  std::sort(instructions.begin(), instructions.end(), cmp());
-  std::sort(custom_instructions.begin(), custom_instructions.end(), cmp());
-
   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) {
@@ -1165,15 +1139,12 @@ void processor_t::register_base_instructions()
 {
   #define DECLARE_INSN(name, match, mask) \
     insn_bits_t name##_match = (match), name##_mask = (mask); \
-    bool name##_supported = true;
+    isa_extension_t name##_ext = NUM_ISA_EXTENSIONS; \
+    bool name##_overlapping = false;
 
   #include "encoding.h"
   #undef DECLARE_INSN
 
-  #define DECLARE_OVERLAP_INSN(name, ext) { name##_supported = isa->extension_enabled(ext); }
-  #include "overlap_list.h"
-  #undef DECLARE_OVERLAP_INSN
-
   #define DEFINE_INSN(name) \
     extern reg_t fast_rv32i_##name(processor_t*, insn_t, reg_t); \
     extern reg_t fast_rv64i_##name(processor_t*, insn_t, reg_t); \
@@ -1182,8 +1153,14 @@ void processor_t::register_base_instructions()
     extern reg_t logged_rv32i_##name(processor_t*, insn_t, reg_t); \
     extern reg_t logged_rv64i_##name(processor_t*, insn_t, reg_t); \
     extern reg_t logged_rv32e_##name(processor_t*, insn_t, reg_t); \
-    extern reg_t logged_rv64e_##name(processor_t*, insn_t, reg_t); \
-    if (name##_supported) { \
+    extern reg_t logged_rv64e_##name(processor_t*, insn_t, reg_t);
+  #include "insn_list.h"
+  #undef DEFINE_INSN
+
+  // add overlapping instructions first, in order
+  #define DECLARE_OVERLAP_INSN(name, ext) \
+    name##_overlapping = true; \
+    if (isa->extension_enabled(ext)) \
       register_base_insn((insn_desc_t) { \
         name##_match, \
         name##_mask, \
@@ -1194,11 +1171,31 @@ void processor_t::register_base_instructions()
         logged_rv32i_##name, \
         logged_rv64i_##name, \
         logged_rv32e_##name, \
-        logged_rv64e_##name}); \
-    }
+        logged_rv64e_##name});
+  #include "overlap_list.h"
+  #undef DECLARE_OVERLAP_INSN
+
+  // add all other instructions.  since they are non-overlapping, the order
+  // does not affect correctness, but more frequent instructions should
+  // appear earlier to improve search time on opcode_cache misses.
+  #define DEFINE_INSN(name) \
+    if (!name##_overlapping) \
+      register_base_insn((insn_desc_t) { \
+        name##_match, \
+        name##_mask, \
+        fast_rv32i_##name, \
+        fast_rv64i_##name, \
+        fast_rv32e_##name, \
+        fast_rv64e_##name, \
+        logged_rv32i_##name, \
+        logged_rv64i_##name, \
+        logged_rv32e_##name, \
+        logged_rv64e_##name});
   #include "insn_list.h"
+  #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
diff --git a/riscv/riscv.mk.in b/riscv/riscv.mk.in
index 469c48d..60723b5 100644
--- a/riscv/riscv.mk.in
+++ b/riscv/riscv.mk.in
@@ -182,6 +182,8 @@ riscv_insn_ext_c = \
 	c_jr \
 	c_li \
 	c_lui \
+	c_ld \
+	c_ldsp \
 	c_lw \
 	c_lwsp \
 	c_mv \
@@ -191,6 +193,8 @@ riscv_insn_ext_c = \
 	c_srli \
 	c_sub \
 	c_subw \
+	c_sd \
+	c_sdsp \
 	c_sw \
 	c_swsp \
 	c_xor \
@@ -1061,6 +1065,9 @@ riscv_insn_ext_zimop = \
 	mop_r_N \
 	mop_rr_N \
 
+riscv_insn_ext_zcmop = \
+	c_mop_N \
+
 riscv_insn_ext_zicfilp = \
 	lpad
 
@@ -1085,20 +1092,20 @@ riscv_insn_ext_zvk = \
 	$(riscv_insn_ext_zvksh) \
 
 riscv_insn_list = \
-	$(if $(HAVE_INT128),$(riscv_insn_ext_v),) \
-	$(riscv_insn_ext_a) \
+	$(riscv_insn_ext_i) \
+	$(riscv_insn_ext_c) \
+	$(riscv_insn_ext_f) \
+	$(riscv_insn_ext_d) \
+	$(riscv_insn_ext_m) \
 	$(riscv_insn_ext_b) \
+	$(riscv_insn_ext_a) \
+	$(if $(HAVE_INT128),$(riscv_insn_ext_v),) \
 	$(riscv_insn_ext_bf16) \
-	$(riscv_insn_ext_c) \
 	$(riscv_insn_ext_cmo) \
-	$(riscv_insn_ext_d) \
 	$(riscv_insn_ext_d_zfa) \
-	$(riscv_insn_ext_f) \
 	$(riscv_insn_ext_f_zfa) \
 	$(riscv_insn_ext_h) \
-	$(riscv_insn_ext_i) \
 	$(riscv_insn_ext_k) \
-	$(riscv_insn_ext_m) \
 	$(riscv_insn_ext_q) \
 	$(riscv_insn_ext_q_zfa) \
 	$(riscv_insn_ext_zacas) \
@@ -1114,6 +1121,7 @@ riscv_insn_list = \
 	$(riscv_insn_smrnmi) \
 	$(riscv_insn_svinval) \
 	$(riscv_insn_ext_zimop) \
+	$(riscv_insn_ext_zcmop) \
 	$(riscv_insn_ext_zicfilp) \
 	$(riscv_insn_ext_zicfiss) \