Paper deep dive
AutoLALA: Automatic Loop Algebraic Locality Analysis for AI and HPC Kernels
Yifan Zhu, Yekai Pan, Yanghui Wu, Chen Ding
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 99%
Last extracted: 4/10/2026, 3:00:35 AM
Summary
AutoLALA is an open-source Rust-based tool that performs automatic, symbolic data locality analysis for affine loop programs. By leveraging the polyhedral model and the Barvinok library, it computes closed-form symbolic formulas for reuse distance and Data Movement Distance (DMD), enabling performance analysis of HPC and AI workloads without requiring simulation.
Entities (5)
Relation Signals (3)
AutoLALA → analyzes → Affine Loop Programs
confidence 100% · The tool accepts programs written in a small domain-specific language (DSL), lowers them to polyhedral sets and maps
AutoLALA → implements → Data Movement Distance
confidence 100% · AutoLALA implements the fully symbolic locality analysis of Zhu et al. together with the data movement distance (DMD) framework of Smith et al.
AutoLALA → uses → Barvinok Library
confidence 100% · The system is implemented in Rust as a modular library spanning three crates, with safe bindings to the Barvinok library.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Data movement is the primary bottleneck in modern computing systems. For loop-based programs common in high-performance computing (HPC) and AI workloads, including matrix multiplication, tensor contraction, stencil computation, and einsum operations, the cost of moving data through the memory hierarchy often exceeds the cost of arithmetic. This paper presents AutoLALA, an open-source tool that analyzes data locality in affine loop programs. The tool accepts programs written in a small domain-specific language (DSL), lowers them to polyhedral sets and maps, and produces closed-form symbolic formulas for reuse distance and data movement complexity. AutoLALA implements the fully symbolic locality analysis of Zhu et al. together with the data movement distance (DMD) framework of Smith et al. In particular, it computes reuse distance as the image of the access space under the access map, avoiding both stack simulation and Denning's recursive working-set formulation. We describe the DSL syntax and its formal semantics, the polyhedral lowering pipeline that constructs timestamp spaces and access maps via affine transformations, and the sequence of Barvinok counting operations used to derive symbolic reuse-interval and reuse-distance distributions. The system is implemented in Rust as a modular library spanning three crates, with safe bindings to the Barvinok library. We provide both a command-line interface and an interactive web playground with LaTeX rendering of the output formulas. The tool handles arbitrary affine loop nests, covering workloads such as tensor contractions, einsum expressions, stencil computations, and general polyhedral programs.
Tags
Links
- Source: https://arxiv.org/abs/2604.05066v1
- Canonical: https://arxiv.org/abs/2604.05066v1
Trouble viewing inline? Open PDF directly →
Full Text
39,195 characters extracted from source content.
Expand or collapse full text
AutoLALA: Automatic Loop Algebraic Locality Analysis for AI and HPC Kernels Yifan Zhu 0009-0000-6718-7787 University of RochesterRochesterNYUSA yifanzhu@rochester.edu , Yekai Pan 0009-0001-7639-1488 University of RochesterRochesterNYUSA ypan34@u.rochester.edu , Yanghui Wu 0009-0005-2675-2811 University of RochesterRochesterNYUSA ywu86@ur.rochester.edu and Chen Ding 0000-0003-4968-6659 University of RochesterRochesterNew YorkUSA Abstract. Data movement is the main bottleneck in modern computing. For loop-based programs common in high-performance computing (HPC) and AI workloads—including matrix multiplication, tensor contraction, stencil computation, and einsum operations—the cost of moving data through the memory hierarchy often exceeds the cost of arithmetic. This paper presents AutoLALA, an open-source tool that takes a loop program written in a small domain-specific language (DSL), lowers it to polyhedral sets and maps, and produces closed-form symbolic formulas for reuse distance and data movement complexity. The tool implements the fully symbolic locality analysis of Zhu et al. and the data movement distance (DMD) framework of Smith et al., computing reuse distance as the image of the access space under the access map—without stack simulation or Denning’s recursive working-set formulation. We describe the DSL syntax, its formal semantics, the polyhedral lowering that constructs timestamp spaces and access maps via affine transformations, and the chain of Barvinok counting operations that yields symbolic reuse-interval and reuse-distance distributions. The system is implemented in Rust across three crates and integrates with the Barvinok library through safe bindings. We provide a command-line tool and a web playground with LaTeX rendering of the output formulas. The tool handles any affine loop nest, covering workloads such as tensor contractions, einsum expressions, stencil computations, and general polyhedral programs. 1. Introduction The gap between processor speed and memory latency has grown for decades. Data movement—the traffic between a processor and its memory hierarchy—is now the main cost in both time and energy for many workloads (Smith et al., 2022; Hong and Kung, 1981). This is true for dense linear algebra in HPC, for tensor operations in machine learning, and for stencil computations in scientific simulation. Time complexity counts operations while treating memory as free. It cannot distinguish algorithms with the same operation count but different data movement, e.g., naive vs. tiled matrix multiplication, both Θ(N3) (N^3) (Smith et al., 2022). Data Movement Distance (DMD) (Smith et al., 2022) is a framework that assigns each memory access a cost proportional to the square root of its reuse distance—the number of distinct data elements accessed between two consecutive accesses to the same element. The DMD of a program is the sum of these per-access costs. This framework can distinguish algorithms with identical time complexity but different memory behavior. Zhu et al. (Zhu et al., 2026) showed how to compute the reuse-distance distribution of an affine loop nest as a symbolic (quasi-)polynomial in the loop bounds. Their method uses the polyhedral model: loop iterations form an integer set, memory accesses form an affine map, and reuse distances are obtained by composing these maps and counting integer points with the Barvinok library (Verdoolaege and others, 2024; Verdoolaege et al., 2007). The result is a set of closed-form formulas that hold for all input sizes and cache configurations, removing the need for simulation or profiling. This paper describes AutoLALA (Automatic Loop Algebraic Locality Analysis), an open-source Rust implementation of this analysis pipeline. The contributions are: (1) A domain-specific language (DSL) for specifying affine loop programs with symbolic parameters, affine bounds, conditional guards, and typed memory accesses (§3). (2) A polyhedral lowering that translates DSL programs into timestamp spaces (integer sets) and access maps (affine relations), handling loop steps, statement interleaving, and conditional branches (§4). (3) A symbolic locality analysis that computes reuse-interval and reuse-distance distributions, assembles DMD formulas, and filters non-scaling branches—with reuse distance computed as the image of the access space under the access map (§5). (4) A Rust implementation organized as three crates—a core library, a CLI, and a web playground—with safe Barvinok bindings (§6). The DSL accepts any affine loop nest. This covers a broad class of HPC and AI workloads: dense matrix operations, tensor contractions and einsum expressions (Blacher et al., 2024; Kjolstad et al., 2017), stencil computations, image-processing pipelines (Ragan-Kelley et al., 2013), and the PolyBench suite (Pouchet, 2012). Any loop program whose bounds and subscripts are affine functions of the enclosing iterators and symbolic parameters can be analyzed. 2. Background 2.1. The Polyhedral Model The polyhedral model represents loop nests as integer polyhedra (Aho et al., 2006). A loop with affine bounds ℓ≤i<u ≤ i<u defines a set of integer points i∈ℤ∣ℓ≤i<u\i ≤ i<u\. Nesting d loops produces a d-dimensional polyhedron. Memory accesses with affine subscripts (e.g., A[i+1,2j]A[i+1,2j]) define affine maps from the iteration space to a data space. Tools such as ISL (Verdoolaege, 2010) manipulate these sets and maps symbolically: union, intersection, composition, inversion, lexicographic ordering, and counting. A quasi-polynomial is a polynomial whose coefficients may depend on the residues of the variables modulo fixed constants. The Barvinok library (Verdoolaege and others, 2024; Verdoolaege et al., 2007) computes the number of integer points in a parametric polytope as a quasi-polynomial in the parameters. This is the key operation that turns polyhedral relations into closed-form symbolic formulas. 2.2. Reuse Distance Reuse distance (also called LRU stack distance) (Mattson et al., 1970; Zhong et al., 2009) is the number of distinct data elements accessed between two consecutive accesses to the same element. Given an access trace a1,a2,…,ana_1,a_2,…,a_n, the reuse distance of access ata_t is the number of distinct elements in at′+1,…,at−1\a_t +1,…,a_t-1\ where t′<t <t is the most recent prior access to the same element. If ata_t is the first access to its element, the reuse distance is ∞ (a compulsory miss). The reuse distance fully characterizes LRU cache behavior: an access with reuse distance r hits in a fully associative LRU cache of size c if and only if r<cr<c (Mattson et al., 1970). 2.3. Data Movement Distance The DMD framework (Smith et al., 2022) assigns each access a cost based on its reuse distance. For a program with n total accesses, of which ncn_c are compulsory (first access to each element) and the remaining n−ncn-n_c have finite reuse distances, the DMD is: (1) DMD=nc+∑t:warmaccessrd(t)DMD=n_c+ _ subarrayct:warm\\ access subarray rd(t) where rd(t)rd(t) is the reuse distance of access t. The ⋅ · models the fact that data with smaller reuse distance is more likely to be cached, so its movement cost is lower. Empirical studies have observed that cache miss rates scale as a power of reuse distance (Hartstein et al., 2008), and the square root provides a robust approximation for modern hierarchies (Smith et al., 2022). When the reuse-distance distribution is given as a symbolic function—a set of regions DiD_i with multiplicity mim_i and reuse distance rir_i—the DMD becomes: (2) DMD=nc+∑imi⋅riDMD=n_c+ _im_i· r_i where each mim_i and rir_i are quasi-polynomials in the symbolic parameters. 3. The AutoLALA DSL AutoLALA accepts programs in a small DSL designed for specifying affine loop nests. We describe its syntax formally and illustrate it with examples. 3.1. Formal Syntax The grammar is given in BNF-like notation. Terminals are in typewriter font; nonterminals are in ⟨ brackets⟩ . ¡program¿ ::= ¡param-decl¿* ¡array-decl¿* ¡stmt¿* ¡param-decl¿ ::= ‘params’ ¡id-list¿ ‘;’ ¡array-decl¿ ::= ‘array’ ¡id¿ ‘[’ ¡expr-list¿ ‘]’ ‘;’ ¡stmt¿ ::= ¡for-stmt¿ | ¡if-stmt¿ | ¡access-stmt¿ ¡for-stmt¿ ::= ‘for’ ¡id¿ ‘in’ ¡expr¿ ‘..’ ¡expr¿ ¡step-spec¿? ¡block¿ ¡step-spec¿ ::= ‘step’ ¡integer¿ ¡if-stmt¿ ::= ‘if’ ¡cond-list¿ ¡block¿ (‘else’ ¡block¿)? ¡block¿ ::= ‘’ ¡stmt¿* ‘’ ¡access-stmt¿ ::= ¡access-kind¿ ¡id¿ ‘[’ ¡expr-list¿ ‘]’ ‘;’ ¡access-kind¿ ::= ‘read’ | ‘write’ | ‘update’ ¡cond-list¿ ::= ¡comparison¿ (‘&&’ ¡comparison¿)* ¡comparison¿ ::= ¡expr¿ ¡cmp-op¿ ¡expr¿ ¡cmp-op¿ ::= ‘<’ | ‘<=’ | ‘==’ | ‘>=’ | ‘>’ ¡expr¿ ::= ¡expr¿ (‘+’ | ‘-’) ¡mul-expr¿ | ¡mul-expr¿ ¡mul-expr¿ ::= ¡mul-expr¿ (‘*’ | ‘/’) ¡unary¿ | ¡unary¿ ¡unary¿ ::= ‘-’ ¡unary¿ | ‘(’ ¡expr¿ ‘)’ | ¡integer¿ | ¡id¿ A program consists of zero or more parameter declarations, zero or more array declarations, and a sequence of statements. Parameters are symbolic constants (e.g., matrix dimensions); arrays are declared with their extents as affine expressions of the parameters. 3.2. Affine Restriction All expressions in bounds, subscripts, conditions, and array extents must be affine: degree at most 1 in any variable. Concretely: – Multiplication requires at least one operand to be a compile-time constant. The product i⋅ji· j where both i and j are loop variables is rejected. – Division (/) computes integer floor division and requires a constant divisor. – Variables in an expression must be symbolic parameters or enclosing loop iterators. This restriction is necessary for the polyhedral model: the iteration domain must be an integer polyhedron and the access function must be an affine map. 3.3. Access Kinds Each memory access is tagged as read, write, or update. For the purpose of locality analysis, all three are treated uniformly: they contribute equally to the timestamp sequence and the access map. The distinction is retained in the AST for potential future use in cost models that distinguish reads from writes. 3.4. Example: Matrix Multiplication ⬇ 1params M, N, K; 2array A[M, K]; 3array B[K, N]; 4array C[M, N]; 5 6for i in 0 .. M 7 for j in 0 .. N 8 for k in 0 .. K 9 read C[i, j]; 10 read A[i, k]; 11 read B[k, j]; 12 write C[i, j]; 13 14 15 Listing 1: Matrix multiplication in the AutoLALA DSL. This program specifies a triply-nested loop with four memory accesses per iteration. The symbolic parameters M, N, K are the matrix dimensions. The tool produces symbolic formulas for the reuse-distance distribution and the DMD as functions of M, N, and K. 3.5. Example: 1D Jacobi Stencil ⬇ 1params N, T; 2array A[N]; 3array B[N]; 4 5for t in 0 .. T 6 for i in 1 .. N - 1 7 read A[i - 1]; 8 read A[i]; 9 read A[i + 1]; 10 write B[i]; 11 12 for i in 1 .. N - 1 13 read B[i]; 14 write A[i]; 15 16 Listing 2: 1D Jacobi stencil. The stencil accesses A[i-1], A[i], and A[i+1], all of which are affine. The tool computes the reuse distances between consecutive timesteps and across the i-loop. 3.6. Example: Einsum / Tensor Contraction Tensor contractions, frequently expressed as einsum operations in deep-learning frameworks, are naturally affine. A contraction Cij=∑kAikBkjC_ij= _kA_ikB_kj is exactly the matrix multiplication of Listing 1. Higher-order contractions such as Dij=∑k,lAiklBkljD_ij= _k,lA_iklB_klj add more loops but keep all subscripts affine. Similarly, batched operations like Cbij=∑kAbikBbkjC_bij= _kA_bikB_bkj simply add a batch loop. All of these fall within the scope of AutoLALA. 4. Polyhedral Lowering This section describes how the tool translates a DSL program into the polyhedral objects required for locality analysis: a timestamp space (an integer set) and an access map (an affine relation). 4.1. Timestamp Space The timestamp space encodes the execution order of all memory accesses in the program. Each access is assigned a point in a multi-dimensional integer space whose lexicographic order matches the execution order. Loop dimensions. A for loop with iterator i, lower bound ℓ , upper bound u, and step s contributes one dimension. Rather than storing the iterator value directly, the tool stores the ordinal iteration count oi∈0,1,…,⌈(u−ℓ)/s⌉−1o_i∈\0,1,…, (u- )/s -1\. The actual iterator value is recovered as i=oi⋅s+ℓi=o_i· s+ . The ordinal representation has two advantages: the lower bound is always 0, and the step is always 1. Formally, for a single loop, the contribution to the timestamp space is: (3) for=oi∈ℤ| 0≤oi∧oi<⌈(u−ℓ)/s⌉T_ for= \o_i \; \;0≤ o_i\; \;o_i< (u- )/s \ For nested loops, the timestamp space is the Cartesian product constrained by the conjunction of all loop bounds: (4) =(o1,…,od)∈ℤd|⋀k=1d0≤ok<⌈(uk−ℓk)/sk⌉T= \(o_1,…,o_d) ^d\; \; _k=1^d0≤ o_k< (u_k- _k)/s_k \ where the bounds ℓk _k and uku_k may depend on enclosing loop ordinals and symbolic parameters. Statement interleaving. When a block contains multiple statements, each statement j (numbered from 0) gets a dedicated ‘selector” dimension set to the constant j. For a block with m statements S0,…,Sm−1S_0,…,S_m-1, the timestamp space is: (5) block=⋃j=0m−1(j)×SjT_block= _j=0^m-1 \(j)×T_S_j \ where SjT_S_j is the timestamp space of statement SjS_j, padded with zero-constrained dimensions so that all branches have the same dimensionality. The selector dimension is placed at the depth of the enclosing block, and all sub-statements share the same parameter space. Conditional branches. An if statement with condition ϕφ is handled by intersecting the then-branch timestamp space with the condition set and the else-branch with its complement: (6) if=(then∩⟦ϕ⟧)∪(else∩⟦¬ϕ⟧)T_ if=(T_then∩ φ )\;∪\;(T_else∩ φ ) The condition ϕφ is a conjunction of affine comparisons, so ⟦ϕ⟧ φ is a polyhedron. 4.2. Access Map The access map :→A:T sends each timestamp to the memory location it accesses. The data space D is a tuple: (7) =(array_id,d1,…,dr,[b,s])D=(array\_id,\;d_1,…,d_r,\;[b,\;s]) where array_id is an integer identifying the array, d1,…,drd_1,…,d_r are the array subscript values padded to a uniform rank r=maxarraysrankr= _arraysrank, and the optional components b and s handle cache blocking and set-associativity. Affine subscript transformation. For an access read A[f1(i→,p→),…,fk(i→,p→)] read A[f_1( i, p),…,f_k( i, p)], each subscript fjf_j is an affine function of the enclosing loop iterators i→ i and the symbolic parameters p→ p. Since the iterators are stored in ordinal form, the tool converts back: if the q-th loop has lower bound ℓq _q and step sqs_q, and the ordinal dimension is oqo_q, then a reference to iterator iqi_q in the subscript is replaced by oq⋅sq+ℓqo_q· s_q+ _q. The resulting map component is: (8) fj(i→,p→)=fj(o1⋅s1+ℓ1,…,od⋅sd+ℓd,p→)f_j( i, p)=f_j(o_1· s_1+ _1,…,o_d· s_d+ _d, p) This is still affine in the ordinals oqo_q and parameters p→ p, so the access map is an affine relation. Cache blocking. When the tool is invoked with a block size B>1B>1, the last subscript dimension is replaced by ⌊dr/B⌋ d_r/B . This models the effect of cache-line granularity: two accesses to the same cache line map to the same data-space point. Set-associative tagging. When the number of sets S>1S>1, an extra dimension drmodSd_r S is appended. This models set-associative caches where the set index determines which cache set an address maps to. Construction. The access map for each statement is built by constructing an affine function list: (9) stmt=o→(id,f1(o→,p→),…,fr(o→,p→))A_stmt= \ o→(id,\;f_1( o, p),\;…,\;f_r( o, p)) \ Block-level maps are formed by unioning the maps of all sub-statements (after alignment, analogous to timestamp space construction). The final access map is intersected with the timestamp space to restrict it to reachable points: (10) =raw∩(×)A=A_raw∩(T×D) 5. Symbolic Locality Analysis Given the timestamp space T and the access map :→A:T , the tool computes the reuse-interval (RI) distribution, the reuse-distance (RD) distribution, and the DMD formula. All intermediate objects are polyhedral relations manipulated symbolically. 5.1. Lexicographic Ordering The execution order is the lexicographic order on T. The tool constructs two relations: (11) ≺ =(t→,t→′)∈2∣t→<lext→′ =\( t, t ) ^2 t<_lex t \ (12) ⪯ =(t→,t→′)∈2∣t→≤lext→′ =\( t, t ) ^2 t _lex t \ These are standard polyhedral operations provided by ISL (Verdoolaege, 2010) as lex_lt and lex_le, restricted to the timestamp space. 5.2. Same-Element Relation Two timestamps access the same data element if they map to the same point in D: (13) =∘−1=(t→,t→′)∣(t→)=(t→′)S=A ^-1=\( t, t ) ( t)=A( t )\ This is the composition of the access map with its inverse. Two timestamps (t→,t→′)( t, t ) are in S if and only if they access the same array element (or the same cache line, when blocking is enabled). 5.3. Immediate Predecessor Among all same-element pairs where t→′ t comes before t→ t, the immediate predecessor of t→ t is the latest such t→′ t : (14) =lexmin(∩≺)N=lexmin(S∩ ) Here lexminlexmin selects the lexicographically smallest image for each domain element, giving the immediate next same-element access. Its inverse =−1P=N^-1 gives the immediate predecessor. 5.4. Reuse Interval The reuse interval of a warm access t→ t is the set of timestamps between its immediate predecessor and itself. The tool computes this as: (15) ℐ=∘≺I=P This maps each warm-access timestamp t→ t to all timestamps strictly after its predecessor and (by further intersection) up to and including t→ t: (16) ℛℐ=ℐ∩⪰RI=I∩ where ⪰ is ⪯−1 ^-1. For a given t→ t, the set ℛℐ(t→)=t→′∣(t→)≺t→′⪯t→RI( t)=\ t ( t) t t\ contains all timestamps in the reuse window. The reuse-interval value (the number of accesses in the window) is the cardinality: (17) ri(t→)=|ℛℐ(t→)|ri( t)= ( t) Applying the Barvinok cardinality operation to the relation ℛℐRI yields riri as a piecewise quasi-polynomial in the loop iterators and symbolic parameters. 5.5. Reuse Distance as Image under Access Map The reuse distance counts the number of distinct data elements in the reuse window. Traditional approaches compute this via stack simulation or the inclusion-exclusion counting of Denning’s working-set recursion (Denning, 2021). AutoLALA takes a different route, following the approach of Zhu et al. (Zhu et al., 2026): it computes the reuse distance as the cardinality of the image of the reuse-interval window under the access map. Concretely, the tool composes the reuse-interval relation with the access map: (18) ℛ=ℛℐ∘RD=RI For a given warm-access timestamp t→ t, the set ℛ(t→)=(ℛℐ(t→))RD( t)=A(RI( t)) is the set of distinct data elements accessed in the reuse window. The reuse distance is: (19) rd(t→)=|ℛ(t→)|rd( t)= ( t) Applying Barvinok’s cardinality operation to ℛRD yields rdrd as a piecewise quasi-polynomial. This formulation avoids any recursive working-set computation. The reuse distance is obtained in a single composition followed by a cardinality count. The composition ℛℐ∘RI is a standard polyhedral operation: for each timestamp t→ t, it collects all data elements (t→′)A( t ) for t→′ t in the reuse window, then the cardinality counts the number of distinct such elements. 5.6. Distribution Processing The piecewise quasi-polynomials for RI and RD are organized by value: pieces with the same quasi-polynomial expression for ri(t→)ri( t) (or rd(t→)rd( t)) are grouped. Within each group, the domain (the set of timestamps with that reuse distance) is reported as a union of parametric polyhedra, and its cardinality gives the multiplicity—the number of accesses with that reuse distance. For each value group i, the tool extracts: – The reuse-distance value rir_i: a quasi-polynomial in the parameters. – A set of regions Di,1,Di,2,…D_i,1,D_i,2,…, each a parametric polyhedron. – The multiplicity mi,j=|Di,j|m_i,j= D_i,j : the number of timestamps in each region. 5.7. DMD Assembly The tool computes three access counts: (20) ntotal n_total =|| = (21) nwarm n_warm =∑i,jmi,j = _i,jm_i,j (22) nc n_c =ntotal−nwarm =n_total-n_warm where ncn_c is the number of compulsory (cold) accesses. The DMD formula is then: (23) DMD=nc+∑i,jmi,j⋅riDMD=n_c+ _i,jm_i,j· r_i Each mi,jm_i,j and rir_i is a quasi-polynomial in the symbolic parameters, so the entire DMD formula is symbolic. 5.8. Region Scaling Filter Not all regions in the reuse-distance distribution contribute to the asymptotic DMD. Some regions are ‘pinned”: they exist only for specific constant values of a parameter (e.g., K=2K=2) or are bounded from above (e.g., K≤512K≤ 512). These do not scale with the problem size and are irrelevant for asymptotic analysis. The tool filters a region D based on its constraints: – If any named parameter dimension is fixed by an equality constraint (e.g., N=5N=5), the region does not scale. – If any named parameter dimension has an upper-bound constraint (e.g., N≤cN≤ c), the region does not scale. Only regions that pass this filter contribute to the DMD formula. The full RI and RD distributions are still reported for diagnostic purposes. 6. System Architecture AutoLALA is implemented in Rust (edition 2024, minimum version 1.92) as a Cargo workspace with three crates. 6.1. Crate Organization dmd-core. The core library implements the full analysis pipeline. It contains six modules: – lexer: tokenization using the logos crate. Tokens include keywords (params, array, for, in, step, if, else, read, write, update), operators (+, -, *, /, &&, comparisons), delimiters, identifiers, and integer literals. – grammar / parser: an LALRPOP grammar that produces an AST. LALRPOP generates an LR(1) parser from the grammar specification at build time. – ast: type definitions for the abstract syntax tree (programs, loops, conditionals, accesses, affine expressions). – semantics: validates the AST. Checks include: unique parameter names, correct array ranks, no loop-variable shadowing, affine expressions only (rejects variable×variable products), and positive loop steps. – polyhedral: the lowering and analysis engine. Constructs timestamp spaces and access maps, computes RI/RD distributions and DMD formulas. All Barvinok calls are serialized under a global mutex because the library’s context initialization is not thread-safe. – formula: algebraic expression type with simplification (flattening, coefficient collection, constant folding, perfect-square extraction) and dual rendering to plain text and LaTeX. dmd-cli. A command-line tool built with clap. It reads a DSL file (or stdin), invokes dmd-core, and prints the analysis report as plain text or JSON. Options include --block-size, --num-sets, --max-operations, and --approximation-method. dmd-playground. A web application using axum (async Rust web framework) and tokio. The frontend uses the Monaco editor for DSL editing with custom syntax highlighting and KaTeX for LaTeX formula rendering. Analysis jobs are submitted via POST /api/tasks and polled via GET /api/tasks/id. Concurrency is bounded by a tokio semaphore (default: 4), and each job has a timeout (default: 30 seconds). 6.2. Barvinok Integration The tool uses barvinok-rs, a Rust binding to the Barvinok/ISL C libraries. The binding’s build script (barvinok-sys) bundles the C sources for Barvinok, ISL, and PolyLib and compiles them via autotools. Host dependencies are GMP, NTL, and libclang. Barvinok is invoked with the --approximation-method=scale flag, which uses the scale approximation for counting quasi-polynomials. All Barvinok operations (context creation, set/map construction, cardinality computation) happen inside a scoped context that bounds the maximum number of operations to prevent runaway computations on programs with high-dimensional iteration spaces. 6.3. Formula Rendering The FormulaExpr type represents symbolic expressions: ⬇ pub enum FormulaExpr Rational numerator: i64, denominator: i64 , Symbol(String), Raw plain: String, latex: String , Add(Vec<FormulaExpr>), Mul(Vec<FormulaExpr>), Div(Box<FormulaExpr>, Box<FormulaExpr>), Pow(Box<FormulaExpr>, u32), Sqrt(Box<FormulaExpr>), Listing 3: Core formula expression type. Each variant renders to both plain text (e.g., sqrt(N + M) * K) and LaTeX (e.g., N+M⋅K N+M· K). The FormulaFormatter converts Barvinok quasi-polynomials term-by-term into FormulaExpr values, which are then simplified. 6.4. Pipeline Summary The full pipeline is: DSL source → lexer (logos) → parser (LALRPOP) → AST → semantic validation → timestamp space T + access map A (ISL) → reuse analysis (ℛℐRI, ℛRD) → Barvinok counting → distribution processing → DMD assembly + region filter → formula rendering (plain text + LaTeX). 7. Walkthrough We trace the analysis of a program to show how polyhedral objects are built. Consider: ⬇ 1params N, M; 2array A[N, M]; 3array B[M]; 4 5for i in 0 .. N 6 for j in 0 .. M 7 read A[i, j]; 8 read B[j]; 9 10 Listing 4: Nested loop with reuse. Array B[j]B[j] is reused across outer iterations: within a fixed i, consecutive j-iterations access distinct elements of B, but across i-iterations the same B[j]B[j] is reused. Timestamp space. The loop nest has depth 2 (i, j) with two statements in the body, giving a selector t0∈0,1t_0∈\0,1\: =(i,j,t0)∣0≤i<N∧ 0≤j<M∧ 0≤t0≤1T=\(i,j,t_0) 0≤ i<N\; \;0≤ j<M\; \;0≤ t_0≤ 1\ Access map. Let A have ID 0, B have ID 1. The maximum rank is 2, so B’s subscript is padded: A=(i,j,0)→(0,i,j)A_A=\(i,j,0)→(0,i,j)\, B=(i,j,1)→(1,0,j)A_B=\(i,j,1)→(1,0,j)\. Reuse analysis. The same-element relation pairs timestamps accessing the same element. For B[j]B[j]: every (i,j,1)(i,j,1) for any i accesses it. The immediate predecessor of (i,j,1)(i,j,1) (when i>0i>0) is (i−1,j,1)(i-1,j,1), with a reuse interval spanning ∼2M 2M accesses. The reuse distance counts distinct elements in that window; since A and B have different IDs, the tool computes this symbolically as a quasi-polynomial in N and M. 8. Scope of Applicability The analysis applies to any loop nest where all bounds and subscripts are affine in the enclosing iterators and symbolic parameters. This covers several important classes of HPC and AI workloads: Dense linear algebra. Matrix multiplication, LU, Cholesky, QR, and other routines are affine. The PolyBench/C suite (Pouchet, 2012) contains 30 such benchmarks. Tensor contractions and einsum. A contraction Ci1…im=∑k1…knAi1…imk1…knBk1…knj1…jpC_i_1… i_m= _k_1… k_nA_i_1… i_mk_1… k_nB_k_1… k_nj_1… j_p is a multi-loop nest with affine subscripts. Einsum expressions (Blacher et al., 2024) in PyTorch, NumPy, and TensorFlow map directly to contractions. TACO (Kjolstad et al., 2017) generates code of this form. Prior analytical cache models for tensor contractions (Li et al., 2019; Cociorva et al., 2002) targeted specific patterns; AutoLALA handles the general case. Stencils and convolutions. Jacobi, Gauss-Seidel, and higher-dimensional stencils have affine access patterns, as do convolution layers expressed as nested loops. Image-processing pipelines (Ragan-Kelley et al., 2013) use stencils extensively. Limitations. Data-dependent control flow, indirect access (A[B[i]]A[B[i]]), and non-affine subscripts (A[i⋅j]A[i· j]) are outside the scope of the polyhedral model. 9. Related Work Cache miss equations. Ghosh et al. (Ghosh et al., 1999) derived symbolic cache miss counts via Diophantine equations. Bao et al. (Bao et al., 2018) built a polyhedral analytical cache model. Pitchanathan and Grosser (Pitchanathan et al., 2024) presented Falcon, a scalable analytical model. These target specific cache configurations; AutoLALA produces cache-independent reuse-distance distributions. Reuse distance analysis. Mattson et al. (Mattson et al., 1970) introduced stack-distance analysis. Zhong et al. (Zhong et al., 2009) developed compiler-based reuse-distance analysis; Beyls and D’Hollander (Beyls and D’Hollander, 2005) applied it to cache hints. The relational theory of locality (Yuan et al., 2019) unified reuse distance with higher-order theories (Xiang et al., 2013). AutoLALA builds on Zhu et al. (Zhu et al., 2026), computing reuse distance as parametric quasi-polynomials. Data movement complexity. Hong and Kung (Hong and Kung, 1981) introduced I/O complexity. Olivry et al. (Olivry et al., 2020) derived parametric lower bounds for affine programs. Smith et al. (Smith et al., 2022) proposed the DMD framework that AutoLALA implements. Polyhedral tools. ISL (Verdoolaege, 2010) and Barvinok (Verdoolaege and others, 2024; Verdoolaege et al., 2007) provide the underlying operations. MLIR (Lattner et al., 2021) and Polygeist (Moses et al., 2021) provide polyhedral compiler infrastructure. AutoLALA replaces an earlier MLIR-based path with a standalone DSL. Parallel locality. Liu et al. (Liu et al., 2024) extended symbolic locality analysis to parallel programs with a symbolic thread count. Extending AutoLALA to parallel loops using their techniques is a natural direction for future work. 10. Usage 10.1. Command-Line Interface The CLI reads a DSL file and prints the DMD formula, access counts, and RI/RD distributions: $ cargo run -p dmd-cli -- --input matmul.dsl Flags include --json for structured output, --block-size B for cache-line modeling, and --num-sets S for set-associative modeling. Input is read from a file (--input) or from stdin. 10.2. Web Playground Running cargo run -p dmd-playground -- --port 3000 starts an interactive web interface with a Monaco-based DSL editor (with syntax highlighting), server-side analysis, and KaTeX-rendered output formulas. The backend limits concurrency and enforces per-job timeouts. 11. Conclusion We presented AutoLALA, a tool for automatic symbolic locality analysis of affine loop programs. Given a program in a small DSL, the tool lowers it to polyhedral sets and maps, computes reuse-interval and reuse-distance distributions using Barvinok’s integer-point counting, and assembles a closed-form DMD formula. The reuse distance is computed as the image of the access space under the access map, avoiding stack simulation. The result is a set of symbolic quasi-polynomials that characterize the data movement behavior of the program for all input sizes. The tool covers a broad range of HPC and AI workloads—matrix operations, tensor contractions, einsum expressions, stencil computations—and is implemented in Rust with a CLI and a web playground. Future directions include extending the analysis to parallel programs following Liu et al. (Liu et al., 2024), supporting tiling transformations, and integrating with compiler frameworks such as MLIR (Lattner et al., 2021) to analyze programs extracted from production code. References A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman (2006) Compilers: principles, techniques, and tools. 2nd edition, Addison-Wesley. Cited by: §2.1. W. Bao, S. Krishnamoorthy, L. Pouchet, and P. Sadayappan (2018) Analytical modeling of cache behavior for affine programs. Proceedings of the ACM on Programming Languages 2 (POPL), p. 32:1–32:26. Cited by: §9. K. Beyls and E. H. D’Hollander (2005) Generating cache hints for improved program efficiency. Journal of Systems Architecture 51 (4), p. 223–250. Cited by: §9. M. Blacher, C. Staudt, J. Klaus, M. Wenig, N. Merk, A. Breuer, M. Engel, S. Laue, and J. Giesen (2024) Einsum benchmark: enabling the development of next-generation tensor execution engines. In The Thirty-eighth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, Cited by: §1, §8. D. Cociorva, G. Baumgartner, C. Lam, P. Sadayappan, J. Ramanujam, M. Nooijen, D. E. Bernholdt, and R. Harrison (2002) Space-time trade-off optimization for a class of electronic structure calculations. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, Berlin, Germany. Cited by: §8. P. J. Denning (2021) Working set analytics. ACM Computing Surveys 53 (6), p. 113:1–113:36. External Links: Document Cited by: §5.5. S. Ghosh, M. Martonosi, and S. Malik (1999) Cache miss equations: a compiler framework for analyzing and tuning memory behavior. ACM Transactions on Programming Languages and Systems 21 (4). Cited by: §9. A. Hartstein, V. Srinivasan, T. R. Puzak, and P. G. Emma (2008) On the nature of cache miss behavior: is it 2 2?. Journal of Instruction-Level Parallelism 10. Cited by: §2.3. J. Hong and H. T. Kung (1981) I/o complexity: the red-blue pebble game. In Proceedings of the ACM Symposium on Theory of Computing, Milwaukee, WI. Cited by: §1, §9. F. Kjolstad, S. Kamil, S. Chou, D. Lugato, and S. P. Amarasinghe (2017) The tensor algebra compiler. Proceedings of the ACM on Programming Languages 1 (OOPSLA), p. 77:1–77:29. Cited by: §1, §8. C. Lattner, M. Amini, U. Bondhugula, A. Cohen, A. Davis, J. Pienaar, R. Riddle, T. Shpeisman, N. Vasilache, and O. Zinenko (2021) MLIR: scaling compiler infrastructure for domain specific computation. In Proceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), p. 2–14. External Links: Document Cited by: §11, §9. R. Li, A. Sukumaran-Rajam, R. Veras, T. M. Low, F. Rastello, A. Rountev, and P. Sadayappan (2019) Analytical cache modeling and tilesize optimization for tensor contractions. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), p. 74:1–74:13. Cited by: §8. F. Liu, Y. Zhu, S. Sun, C. Ding, W. Smith, and K. Hosseini (2024) Parallel loop locality analysis for symbolic thread counts. In Proceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques (PACT), p. 219–232. External Links: Document Cited by: §11, §9. R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger (1970) Evaluation techniques for storage hierarchies. IBM Systems Journal 9 (2), p. 78–117. Cited by: §2.2, §2.2, §9. W. S. Moses, L. Chelini, R. Zhao, and O. Zinenko (2021) Polygeist: raising C to polyhedral MLIR. In Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques (PACT), Cited by: §9. A. Olivry, J. Langou, L. Pouchet, P. Sadayappan, and F. Rastello (2020) Automated derivation of parametric data movement lower bounds for affine programs. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), p. 808–822. External Links: Document Cited by: §9. A. Pitchanathan, K. Grover, and T. Grosser (2024) Falcon: a scalable analytical cache model. Proceedings of the ACM on Programming Languages 8 (PLDI), p. 222:1–222:25. External Links: Document Cited by: §9. L. Pouchet (2012) PolyBench/C 4.0. External Links: Link Cited by: §1, §8. J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Durand, and S. P. Amarasinghe (2013) Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, p. 519–530. External Links: Document Cited by: §1, §8. W. Smith, A. Goldfarb, and C. Ding (2022) Beyond time complexity: data movement complexity analysis for matrix multiplication. External Links: 2203.02536, Link Cited by: §1, §1, §1, §2.3, §2.3, §9. S. Verdoolaege et al. (2024) Barvinok: a library for counting the number of integer points in parametric and non-parametric polytopes. Note: Version 0.41.8 External Links: Link Cited by: §1, §2.1, §9. S. Verdoolaege, R. Seghir, K. Beyls, V. Loechner, and M. Bruynooghe (2007) Counting integer points in parametric polytopes using Barvinok’s rational functions. Algorithmica 48 (1), p. 37–66. External Links: Document Cited by: §1, §2.1, §9. S. Verdoolaege (2010) Isl: an integer set library for the polyhedral model. In Mathematical Software – ICMS 2010, K. Fukuda, J. Hoeven, M. Joswig, and N. Takayama (Eds.), Lecture Notes in Computer Science, Vol. 6327, p. 299–302. Cited by: §2.1, §5.1, §9. X. Xiang, C. Ding, H. Luo, and B. Bao (2013) HOTL: a higher order theory of locality. p. 343–356. Cited by: §9. L. Yuan, C. Ding, W. Smith, P. J. Denning, and Y. Zhang (2019) A relational theory of locality. ACM Transactions on Architecture and Code Optimization 16 (3), p. 33:1–33:26. Cited by: §9. Y. Zhong, X. Shen, and C. Ding (2009) Program locality analysis using reuse distance. ACM Transactions on Programming Languages and Systems 31 (6), p. 20:1–20:39. Cited by: §2.2, §9. Y. Zhu, Y. Pan, C. Ding, and Y. Wu (2026) Fully symbolic analysis of loop locality: using imaginary reuse to infer real performance. External Links: 2603.10196, Link Cited by: §1, §5.5, §9.