TriCheck: Memory Model Verification at the Trisection of Software, Hardware, and ISA

Abstract

Memory Consistency Models (MCMs) are typically verified in isolation across the hardware-software stack, leading to unverified interactions between compilers, ISA, and hardware implementations. TriCheck is a novel toolflow designed for full-stack MCM verification, ensuring that the High-Level Language, compiler, ISA, and microarchitecture collectively uphold required consistency guarantees. Application of TriCheck to the RISC-V ISA uncovered significant under-specifications and instances where a RISC-V-compliant microarchitecture allowed 144 memory outcomes forbidden by C11 to be observed.

Report

Key Highlights

• Full-Stack Verification: TriCheck introduces a comprehensive toolflow designed to perform full-stack Memory Consistency Model (MCM) verification, bridging the gaps between software, hardware, and the ISA layer.
• Addressing Isolation: The tool solves the problem inherent in traditional methods, which only verify segments (e.g., compiler mapping to ISA or ISA implementation in hardware) and fail to verify collective consistency.
• RISC-V Case Study: The tool was applied to the open-source RISC-V ISA, focusing on verifying accurate, efficient, and legal compilations originating from the C11 memory model.
• Critical Findings: The analysis revealed significant under-specifications and potential inefficiencies within the documented RISC-V ISA.
• Observed Errors: Verification using litmus tests demonstrated that a RISC-V-compliant microarchitecture permitted 144 outcomes forbidden by the C11 model, out of 1,701 tests examined.

Technical Details

• Tool Name: TriCheck.
• Verification Scope (Trisection): High-Level Language (HLL) model (e.g., C11), Compiler mapping, Instruction Set Architecture (ISA) definition, and Microarchitectural Implementation.
• Target HLL: C11 (used as the high-level consistency specification).
• Target ISA: RISC-V (open-source ISA).
• Methodology: The tool utilizes litmus tests to evaluate execution outcomes and ensure compliance between the compiled code's behavior on the hardware and the original HLL MCM requirements.
• Specific Deficiency Example: Testing showed 144 outcomes forbidden by C11 were possible under the examined RISC-V microarchitecture implementation.

Implications

• ISA Maturity and Adoption: For ISAs like RISC-V, which rely heavily on open-source implementation and rapid iteration, TriCheck is crucial for ensuring foundational correctness and guaranteeing that memory operations behave predictably across the stack.
• Necessity of Full-Stack View: The work demonstrates that verifying layers in isolation is insufficient; full-stack verification is necessary to catch subtle, yet critical, MCM-related bugs that arise at the layer interfaces.
• Compiler and Hardware Design Correction: The findings provide actionable intelligence to the RISC-V ecosystem, pointing toward necessary modifications in both the ISA documentation (to eliminate under-specifications) and future hardware implementations (to ensure compliance with C11 semantics).
• Reduced Design Risk: TriCheck offers a mechanism to evaluate proposed ISA MCM changes rigorously, ensuring new consistency models are correct and complete before extensive hardware implementation resources are committed.