💻 computer science

Separation Logic for Memory Conflict Detection in High-Level Synthesis

This paper presents a spatial verification framework at the LLVM IR level that utilizes Separation Logic and SMT solvers to detect and prevent memory conflicts in High-Level Synthesis by modeling non-affine array accesses as polymorphic spatial predicates, thereby enabling safe parallelization without the performance-degrading over-approximations of conventional polyhedral methods.

Original authors: Yeonseok Lee

Published 2026-07-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yeonseok Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the director of a busy factory (the High-Level Synthesis or HLS process). Your goal is to build a super-fast machine that can do many tasks at the exact same time. To do this, you tell your workers to stop doing things one by one and start doing them all together in a single "clock cycle."

However, there's a major problem: The Memory Bottleneck.

The Problem: The Single-Door Warehouse

In your factory, all the workers need to grab parts from a giant warehouse (the Memory Bank). But this warehouse only has one door.

If Worker A and Worker B both try to walk through that single door at the exact same second, they will crash into each other. This is a Memory Conflict.
To prevent this, your old safety rules (called Polyhedral Frameworks) are very cautious. They look at the workers' instructions. If the instructions involve complex math (like dividing or multiplying numbers that change on the fly, known as non-affine arithmetic), the old rules get confused.
Because they can't prove the workers won't crash, the old rules say: "Better safe than sorry. Let's make everyone wait in line." This turns your super-fast parallel factory back into a slow, single-file line, destroying your speed gains.

The Solution: The "Separation Logic" Map

This paper introduces a new, smarter way to check for crashes using a concept called Separation Logic. Think of this not as a math equation, but as a spatial map of the factory floor.

1. The "Getelementptr" Translator
First, the system translates the complex code into simple, flat instructions (like a GPS giving a single street address instead of a complex set of directions). It looks at the raw instructions the computer understands (LLVM IR) to see exactly where a worker is trying to go.

2. The "Exclusive Ownership" Rule
Separation Logic has a golden rule: You cannot own the same piece of land twice.

Imagine the warehouse is divided into 4 smaller rooms (Memory Banks).
The system asks: "Does Worker A own Room 1, and does Worker B own Room 2?"
If the answer is yes, they are safe. They can go in simultaneously because they are in different rooms.
The magic happens if they both try to claim Room 1. In this logic, trying to say "I own Room 1" AND "I also own Room 1" at the same time creates a logical contradiction (a crash in the logic itself). The system instantly sees this as "Impossible" and flags a conflict.

3. The "Math Detective" (SMT Solver)
The system uses a powerful math detective (an SMT Oracle) to check the workers' paths.

If the math is simple: The detective quickly proves, "Yes, Worker A goes to Room 1, Worker B goes to Room 2. No crash!" The factory runs in parallel.
If the math is too weird (undecidable): Sometimes the workers' paths involve math so complex the detective can't solve it in time.
- Old System: Would guess "Maybe they crash" and force a line.
- This System: Admits, "I can't prove they are safe." It then triggers a Safe Fallback. It says, "Since I can't prove it's safe, I will make them take turns." This ensures the machine never actually crashes, even if it's slightly slower than it could have been.

The Result: A Safer, Faster Factory

By using this "Spatial Map" approach, the paper claims to:

Stop guessing: It doesn't just assume everything is dangerous because the math is hard. It tries to prove exactly which rooms are safe to use together.
Catch the invisible crashes: It catches conflicts that the old "line-up" rules would have missed, allowing more workers to run in parallel.
Guarantee Safety: If the math is too hard to solve, it defaults to a safe, slow mode. It promises that the final machine (the hardware) will never have two workers trying to walk through the same door at the same time.

In short: This paper replaces a cautious, "assume the worst" safety rule with a smart, map-based system that tries to prove workers can work together safely. If it can't prove it, it forces them to wait, ensuring the final hardware is perfectly collision-free.

Technical Summary: Separation Logic for Memory Conflict Detection in High-Level Synthesis

Problem Statement

High-Level Synthesis (HLS) accelerates hardware development by translating C/C++ code into Register Transfer Level (RTL) designs, leveraging loop unrolling and array partitioning to maximize parallelism. However, a critical bottleneck arises when scheduling concurrent memory accesses involving non-affine arithmetic (e.g., symbolic multiplication, division, or modulo operations).

Traditional HLS frameworks rely on the polyhedral model for dependency analysis. This geometric approach requires loop bounds and array access functions to be affine (linear combinations of loop variables). When faced with non-affine indices, polyhedral solvers systematically over-approximate dependencies to ensure safety. This forces a conservative fallback: assuming all memory statements depend on one another, resulting in monolithic heap allocation and the serialization of operations that could otherwise run in parallel. This artificial serialization degrades hardware throughput and efficiency. Furthermore, existing dynamic techniques often require runtime checks or specialized controllers, adding overhead.

Methodology

The paper proposes a spatial verification framework operating directly on the LLVM Intermediate Representation (IR) to detect memory conflicts without relying on affine geometric constraints. The core methodology integrates Separation Logic (SL) with Satisfiability Modulo Theories (SMT) solving.

1. Spatial Modeling at the LLVM IR Level

Unlike previous approaches that analyze C/C++ Abstract Syntax Trees (ASTs), this framework operates on LLVM IR. It leverages the getelementptr (GEP) instruction, which the compiler uses to mechanically flatten multi-dimensional array indices into 1D arithmetic expressions.

Dual-State Architecture: The framework models the system state using two distinct components:
- Monotonic Store ( $s$ ): Maps immutable Static Single Assignment (SSA) virtual registers to values. Due to SSA, registers are never overwritten, simplifying state tracking.
- Spatial Heap ( $h$ ): Maps physical memory addresses (subset of values) to data, representing on-chip SRAM banks.
Polymorphic Bank Predicates: The framework defines spatial predicates bank(k, A, N) that assert exclusive ownership of the $k$ -th memory bank for array $A$ partitioned into $N$ banks. These predicates adapt dynamically based on the partitioning strategy (Cyclic, Block, or Complete) extracted from LLVM metadata.

2. The Conflict-Free Unrolling (CFU) Condition

To verify that $U$ unrolled loop iterations can execute concurrently without structural hazards, the framework formulates the Conflict-Free Unrolling (CFU) condition.

Separating Conjunction ( $\ast$ ): The core of the verification is the iterated separating conjunction:
$cfu(E, A, N) \triangleq \ast_{i=1}^{U} bank(B(expr_i, N), A, N)$
This asserts that the $U$ concurrent memory accesses must own $U$ strictly disjoint physical memory regions.
Spatial Collapse: A fundamental axiom of Separation Logic is that a resource cannot be disjointly owned by itself ( $P \ast P \implies \bot$ ). If two concurrent iterations target the same physical bank $k$ , the spatial formula attempts to evaluate $bank(k) \ast bank(k)$ , which logically collapses to contradiction ( $\bot$ ). This collapse serves as the mathematical detection of a memory conflict.

3. Translation to SMT and Fallback

To make the spatial logic computable, the framework employs a translation function $T$ that reduces the spatial disjointness requirement into a matrix of pairwise inequalities over SSA variables.

Verification Condition (VC): The spatial requirement is translated into a first-order logic formula:
$\pi \implies \bigwedge_{1 \le i < j \le U} (k_i \neq k_j)$
where $\pi$ is the path condition and $k_i$ are the symbolic bank indices.
SMT Oracle: An SMT solver (e.g., Z3) attempts to prove the VC.
- Sat (Satisfiable): The indices are provably distinct; parallel synthesis proceeds.
- Unsat/Unknown/Timeout: If the solver cannot prove disjointness (due to undecidable non-linear arithmetic), the framework triggers a deterministic sequential fallback. It assumes a hazard exists, serializing the operations via multiplexer-driven stall logic to guarantee physical safety.

Key Contributions

Formal Hardware Memory Model: The paper establishes a static memory framework over LLVM IR, abstracting multi-dimensional array indices via GEP instructions and binding them to polymorphic spatial predicates that handle cyclic, block, and complete partitioning.
Conflict-Free Unrolling (CFU) Condition: A definitive spatial execution requirement is formulated using iterated separating conjunction. It detects physical bank hazards through automatic spatial logic collapse ( $cfu \implies \bot$ ) rather than geometric over-approximation.
Automated SMT Translation and Fallback: A mathematically sound translation function reduces spatial propositions to pairwise inequalities over immutable SSA registers. Crucially, it includes a conservative sequential fallback model to ensure absolute safety when non-linear integer arithmetic is undecidable.
Theorem of Soundness: The paper proves that if the algebraic Verification Condition is validated by the SMT solver, the resulting synthesized RTL is structurally immune to memory bank collisions.

Results and Significance

The paper claims to bridge the gap between formal separation logic theory and practical hardware synthesis. By shifting the verification burden from geometric polyhedral models to algebraic SMT solving over LLVM IR, the framework:

Minimizes Conservative Serialization: It avoids the "safe but slow" fallback of traditional tools when encountering non-affine indices, provided the SMT solver can resolve the algebraic constraints.
Ensures Structural Safety: Through the "Spatial Collapse" mechanism and the conservative fallback, the framework guarantees that no synthesized hardware will suffer from structural memory collisions, even in the presence of undecidable arithmetic.
Bypasses Affine Limitations: It resolves complex bank mapping dependencies without requiring linear geometric bounds or generating additional runtime state-machine overhead.

The significance lies in providing a rigorous, algebraic alternative to the polyhedral model for HLS scheduling, enabling higher parallelism in designs with non-affine memory access patterns while maintaining the absolute safety guarantees required for hardware generation. The authors note that future work will involve implementing this as a custom LLVM pass and exploring fractional permissions to optimize read-only concurrent accesses.