RISC-V: OS-independent implication logic

This commit adds the OS-independent extension implication logic for RISC-V.
It implements:

1.  Regular implication (A → B)
    a.  "the extension A implies the extension B"
    b.  "the extension A requires the extension B"
    c.  "the extension A depends on the extension B"
2.  Extension group or shorthand (A == B1 & B2...)
    a.  "the extension A is shorthand for other extensions: B1, B2..."
    b.  "the extension A comprises instructions provided by B1, B2..."
    This is implemented as (A → B1 & B2... + B1 & B2... → A)
    where the former is a regular implication as required by specifications
    and the latter is a "reverse" implication to improve usability.

and prepares for:

3.  Implication with multiple requirements (A1 & A2... → B)
    a.  "A1 + A2 implies B"
    b.  (implicitly used to implement reverse implication of case 2)

Although it uses macros and iterators, good optimizers turn the series of
implications into fast bit-manipulation operations.

In the case 2 (extension group or shorthand; where a superset extension
is just a collection of other subextensions and provides no features by
a superset itself), specifications do specify that an extension group
implies its members but not vice versa.  However, implying an extension
group from its members would improve usability on the feature detection
(especially when the feature provider does not provide existence of such
extension group but provides existence of its members).

Similar "reverse implication" on RISC-V is implemented on LLVM.

Case 3 is implicitly used to implement reverse implication of case 2 but
there's another use case: implication with multiple requirements like
"Zcf" and "Zcd" extensions (not yet implemented in this crate for now).

To handle extension groups perfectly, we need to loop implication several
times (until they converge; normally 2 times and up to 4 times when we add
most of `riscv_hwprobe`-based features).
To make implementation of that loop possible, `cache::Initializer` is
modified to implement `PartialEq` and `Eq`.

4 files changed, 158 insertions, 12 deletions

diff --git a/library/stdarch/crates/std_detect/src/detect/cache.rs b/library/stdarch/crates/std_detect/src/detect/cache.rs
index 3056c28a806..83bcedea612 100644
--- a/library/stdarch/crates/std_detect/src/detect/cache.rs
+++ b/library/stdarch/crates/std_detect/src/detect/cache.rs
@@ -31,7 +31,7 @@ const CACHE_CAPACITY: u32 = 93;
 /// This type is used to initialize the cache
 // The derived `Default` implementation will initialize the field to zero,
 // which is what we want.
-#[derive(Copy, Clone, Default)]
+#[derive(Copy, Clone, Default, PartialEq, Eq)]
 pub(crate) struct Initializer(u128);
 
 // NOTE: the `debug_assert!` would catch that we do not add more Features than
diff --git a/library/stdarch/crates/std_detect/src/detect/mod.rs b/library/stdarch/crates/std_detect/src/detect/mod.rs
index a61400a5553..8fd3d957932 100644
--- a/library/stdarch/crates/std_detect/src/detect/mod.rs
+++ b/library/stdarch/crates/std_detect/src/detect/mod.rs
@@ -49,6 +49,9 @@ cfg_if! {
         #[path = "os/x86.rs"]
         mod os;
     } else if #[cfg(all(any(target_os = "linux", target_os = "android"), feature = "libc"))] {
+        #[cfg(any(target_arch = "riscv32", target_arch = "riscv64"))]
+        #[path = "os/riscv.rs"]
+        mod riscv;
         #[path = "os/linux/mod.rs"]
         mod os;
     } else if #[cfg(all(target_os = "freebsd", feature = "libc"))] {
diff --git a/library/stdarch/crates/std_detect/src/detect/os/linux/riscv.rs b/library/stdarch/crates/std_detect/src/detect/os/linux/riscv.rs
index 33deba93355..6cdc72dff5a 100644
--- a/library/stdarch/crates/std_detect/src/detect/os/linux/riscv.rs
+++ b/library/stdarch/crates/std_detect/src/detect/os/linux/riscv.rs
@@ -1,5 +1,6 @@
 //! Run-time feature detection for RISC-V on Linux.
 
+use super::super::riscv::imply_features;
 use super::auxvec;
 use crate::detect::{Feature, bit, cache};
 
@@ -12,22 +13,16 @@ pub(crate) fn detect_features() -> cache::Initializer {
         }
     };
 
-    // Use auxiliary vector to enable single-letter ISA extensions and Zicsr.
+    // Use auxiliary vector to enable single-letter ISA extensions.
     // The values are part of the platform-specific [asm/hwcap.h][hwcap]
     //
     // [hwcap]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/riscv/include/uapi/asm/hwcap.h?h=v6.14
     let auxv = auxvec::auxv().expect("read auxvec"); // should not fail on RISC-V platform
     #[allow(clippy::eq_op)]
-    let has_a = bit::test(auxv.hwcap, (b'a' - b'a').into());
-    enable_feature(Feature::a, has_a);
-    enable_feature(Feature::zalrsc, has_a);
-    enable_feature(Feature::zaamo, has_a);
+    enable_feature(Feature::a, bit::test(auxv.hwcap, (b'a' - b'a').into()));
     enable_feature(Feature::c, bit::test(auxv.hwcap, (b'c' - b'a').into()));
-    let has_d = bit::test(auxv.hwcap, (b'd' - b'a').into());
-    let has_f = bit::test(auxv.hwcap, (b'f' - b'a').into());
-    enable_feature(Feature::d, has_d);
-    enable_feature(Feature::f, has_d | has_f);
-    enable_feature(Feature::zicsr, has_d | has_f);
+    enable_feature(Feature::d, bit::test(auxv.hwcap, (b'd' - b'a').into()));
+    enable_feature(Feature::f, bit::test(auxv.hwcap, (b'f' - b'a').into()));
     enable_feature(Feature::h, bit::test(auxv.hwcap, (b'h' - b'a').into()));
     enable_feature(Feature::m, bit::test(auxv.hwcap, (b'm' - b'a').into()));
 
@@ -48,5 +43,5 @@ pub(crate) fn detect_features() -> cache::Initializer {
     // to detect when Rust is used to write Linux kernel modules.
     // These should be more than Auxvec way to detect supervisor features.
 
-    value
+    imply_features(value)
 }
diff --git a/library/stdarch/crates/std_detect/src/detect/os/riscv.rs b/library/stdarch/crates/std_detect/src/detect/os/riscv.rs
new file mode 100644
index 00000000000..b268eff8a14
--- /dev/null
+++ b/library/stdarch/crates/std_detect/src/detect/os/riscv.rs
@@ -0,0 +1,148 @@
+//! Run-time feature detection utility for RISC-V.
+//!
+//! On RISC-V, full feature detection needs a help of one or more
+//! feature detection mechanisms (usually provided by the operating system).
+//!
+//! RISC-V architecture defines many extensions and some have dependency to others.
+//! More importantly, some of them cannot be enabled without resolving such
+//! dependencies due to limited set of features that such mechanisms provide.
+//!
+//! This module provides an OS-independent utility to process such relations
+//! between RISC-V extensions.
+
+use crate::detect::{Feature, cache};
+
+/// Imply features by the given set of enabled features.
+///
+/// Note that it does not perform any consistency checks including existence of
+/// conflicting extensions and/or complicated requirements.  Eliminating such
+/// inconsistencies is the responsibility of the feature detection logic and
+/// its provider(s).
+pub(crate) fn imply_features(mut value: cache::Initializer) -> cache::Initializer {
+    loop {
+        // Check convergence of the feature flags later.
+        let prev = value;
+
+        // Expect that the optimizer turns repeated operations into
+        // a fewer number of bit-manipulation operations.
+        macro_rules! imply {
+            // Regular implication:
+            // A1 => (B1[, B2...]), A2 => (B1[, B2...]) and so on.
+            ($($from: ident)|+ => $($to: ident)&+) => {
+                if [$(Feature::$from as u32),+].iter().any(|&x| value.test(x)) {
+                    $(
+                        value.set(Feature::$to as u32);
+                    )+
+                }
+            };
+            // Implication with multiple requirements:
+            // A1 && A2 ... => (B1[, B2...]).
+            ($($from: ident)&+ => $($to: ident)&+) => {
+                if [$(Feature::$from as u32),+].iter().all(|&x| value.test(x)) {
+                    $(
+                        value.set(Feature::$to as u32);
+                    )+
+                }
+            };
+        }
+        macro_rules! group {
+            ($group: ident == $($member: ident)&+) => {
+                // Forward implication as defined in the specifications.
+                imply!($group => $($member)&+);
+                // Reverse implication to "group extension" from its members.
+                // This is not a part of specifications but convenient for
+                // feature detection and implemented in e.g. LLVM.
+                imply!($($member)&+ => $group);
+            };
+        }
+
+        /*
+            If a dependency/implication is not explicitly stated in the
+            specification, it is denoted as a comment as follows:
+            "defined as subset":
+                The latter extension is described as a subset of the former
+                (but the evidence is weak).
+        */
+
+        imply!(zbc => zbkc); // defined as subset
+        group!(zkn == zbkb & zbkc & zbkx & zkne & zknd & zknh);
+        group!(zks == zbkb & zbkc & zbkx & zksed & zksh);
+        group!(zk == zkn & zkr & zkt);
+
+        group!(a == zalrsc & zaamo);
+
+        group!(b == zba & zbb & zbs);
+
+        imply!(zhinx => zhinxmin);
+        imply!(zdinx | zhinxmin => zfinx);
+
+        imply!(zfh => zfhmin);
+        imply!(q => d);
+        imply!(d | zfhmin => f);
+
+        imply!(zicntr | zihpm | f | zfinx => zicsr);
+        imply!(s | h => zicsr);
+
+        // Loop until the feature flags converge.
+        if prev == value {
+            return value;
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn simple_direct() {
+        let mut value = cache::Initializer::default();
+        value.set(Feature::f as u32);
+        // F (and other extensions with CSRs) -> Zicsr
+        assert!(imply_features(value).test(Feature::zicsr as u32));
+    }
+
+    #[test]
+    fn simple_indirect() {
+        let mut value = cache::Initializer::default();
+        value.set(Feature::q as u32);
+        // Q -> D, D -> F, F -> Zicsr
+        assert!(imply_features(value).test(Feature::zicsr as u32));
+    }
+
+    #[test]
+    fn group_simple_forward() {
+        let mut value = cache::Initializer::default();
+        // A -> Zalrsc & Zaamo (forward implication)
+        value.set(Feature::a as u32);
+        let value = imply_features(value);
+        assert!(value.test(Feature::zalrsc as u32));
+        assert!(value.test(Feature::zaamo as u32));
+    }
+
+    #[test]
+    fn group_simple_backward() {
+        let mut value = cache::Initializer::default();
+        // Zalrsc & Zaamo -> A (reverse implication)
+        value.set(Feature::zalrsc as u32);
+        value.set(Feature::zaamo as u32);
+        assert!(imply_features(value).test(Feature::a as u32));
+    }
+
+    #[test]
+    fn group_complex_convergence() {
+        let mut value = cache::Initializer::default();
+        // Needs 2 iterations to converge
+        // (and 3rd iteration for convergence checking):
+        // 1.  [Zk] -> Zkn & Zkr & Zkt
+        // 2.  Zkn -> {Zbkb} & {Zbkc} & {Zbkx} & {Zkne} & {Zknd} & {Zknh}
+        value.set(Feature::zk as u32);
+        let value = imply_features(value);
+        assert!(value.test(Feature::zbkb as u32));
+        assert!(value.test(Feature::zbkc as u32));
+        assert!(value.test(Feature::zbkx as u32));
+        assert!(value.test(Feature::zkne as u32));
+        assert!(value.test(Feature::zknd as u32));
+        assert!(value.test(Feature::zknh as u32));
+    }
+}