Lesson 18.6 — Dependence analysis: GCD, Banerjee, SIV tests, the Omega test, runtime checks¶
Techniques: the GCD test, Banerjee's inequalities, exact single-index (SIV) tests and the Delta test (Goff–Kennedy–Tseng), the Omega test (Pugh), runtime-checked dependences (LLVM's LoopAccessAnalysis) · Pebble implements: — · Lab: GCD and Banerjee (
labs/ch18-loops, Part C) against the exact answer by enumeration · Prerequisites: Lesson 18.3 (add recurrences), Lesson 18.5 (versioning) · Time: 6–7 hours
Every transformation that reorders loop iterations — interchange, tiling, fusion, distribution (Lesson 18.7) and vectorization (Lesson 18.8) — is legal only if it does not reorder two accesses to the same memory location when at least one of them writes. In
iteration \(i\) writes A[i+1], which iteration \(i + 1\) reads: running the iterations in parallel would read stale values. In A[2*i] = A[2*i + 1] + 1 no iteration ever reads what another writes (even vs odd elements). Dependence analysis decides which case holds — for affine subscripts, by asking whether a system of linear equations has an integer solution inside the loop bounds.
1. Problem and motivation¶
The problem. Given two references to the same array in a loop nest, at least one a write, with subscripts that are affine functions of the loop indices, decide whether some pair of iterations accesses the same element and, if so, in which directions and at which distances (in iterations) the dependences go. The exact problem is integer linear programming — NP-complete in general [Pug91] — so compilers use a hierarchy: cheap tests that can prove independence (GCD, Banerjee), exact tests for the common simple subscripts (SIV), an exact but more expensive integer test (Omega), and, when all else fails, a check at run time (LoopAccessAnalysis). LLVM's DependenceAnalysis (used by loop interchange, unroll-and-jam, fusion) implements the practical tests; LoopAccessAnalysis (used by the vectorizer, distribution and versioning) implements the runtime-checked variant.
GCD test¶
The oldest test, from the vectorizing and parallelizing FORTRAN compilers of the 1970s: the dependence equation \(\sum_k a_k i_k - \sum_k b_k i'_k = c\) has an integer solution only if \(\gcd\) of all coefficients divides \(c\) [Ban88; Wol96]. It ignores the loop bounds, so it proves independence only through divisibility, but it is fast and exact about integrality.
Banerjee test¶
Banerjee's inequalities bound the left-hand side of the dependence equation over the loop bounds (and a given direction per loop): if \(0\) lies outside the bounds, there is not even a real solution, hence no dependence [Ban88]. It is the dual of the GCD test — it uses the bounds but ignores integrality — and with direction vectors it computes which orderings of iterations can carry a dependence, which is what transformations need. Wolfe calls it the extreme-value test [Wol96].
SIV tests and the Delta test¶
Goff, Kennedy and Tseng measured real Fortran programs and found that most subscripts involve zero or one loop index ("ZIV", "SIV"), for which exact tests are simple formulas: the strong SIV test (\(a i + c_1\) vs \(a i' + c_2\) gives the distance \((c_1 - c_2)/a\)), weak-zero and weak-crossing SIV, and an exact SIV test via the extended Euclid algorithm. Their Delta test propagates constraints from SIV subscripts into coupled ones [GKT91]. LLVM's DependenceAnalysis.cpp states in its header comment that it implements that paper [LLVM-DA].
Omega test¶
Pugh's Omega test decides integer feasibility of a conjunction of linear constraints exactly, by Fourier–Motzkin elimination extended to integers ("exact shadow", "dark shadow" and "splintering"), and showed that it is fast enough for production use [Pug91; Pug92]. Its descendants are integer-set libraries such as isl [Ver10], which the polyhedral model builds on (Lesson 18.7). GCC shipped an Omega solver for dependence analysis until GCC 5.
Runtime checks (LoopAccessAnalysis)¶
A compiler often cannot know whether two pointer arguments overlap. LLVM's LoopAccessAnalysis (LAA) classifies the dependences between the memory accesses of an innermost loop by the byte distance of their add recurrences (Lesson 18.3), decides whether vectorization is safe, and — when the only obstacle is possible aliasing between different base pointers — produces the minimal set of runtime pointer checks that versioning (Lesson 18.5) turns into a fast path [LLVM-LAA]. It is dependence analysis with the "unknown" case deferred to run time.
2. Definitions and algorithms¶
Definition 18.6.1 (Loop nest, iteration vector, affine reference)
A perfect loop nest of depth \(d\) is for \(i_1 = L_1\) to \(U_1\) … for \(i_d = L_d\) to \(U_d\) (inclusive bounds, step 1) around a body. An iteration is an iteration vector \(\mathbf{i} = (i_1, \dots, i_d)\) in the iteration space \(\mathcal{I} = \prod_k [L_k, U_k] \cap \mathbb{Z}^d\); iterations execute in lexicographic order: \(\mathbf{i} \prec \mathbf{i}'\) iff at the first position \(k\) where they differ, \(i_k < i'_k\). A reference \(A[f_1(\mathbf{i})] \dots [f_m(\mathbf{i})]\) is affine if each subscript is \(f_r(\mathbf{i}) = \sum_k a_{rk}\, i_k + a_{r0}\) with integer constants.
Definition 18.6.2 (Dependence)
Let \(S\) and \(T\) be references to the same array, at least one a write. There is a dependence from the instance \(S(\mathbf{i})\) to the instance \(T(\mathbf{i}')\) if they access the same element and \(S(\mathbf{i})\) executes before \(T(\mathbf{i}')\) (in the same iteration: \(S\) textually precedes \(T\), or \(S\) is the read and \(T\) the write of one statement). It is a flow (true) dependence if \(S\) writes and \(T\) reads, anti if \(S\) reads and \(T\) writes, output if both write (and input if both read, harmless for correctness).
Definition 18.6.3 (Distance and direction vectors)
For a dependence from \(S(\mathbf{i})\) to \(T(\mathbf{i}')\), the distance vector is \(\mathbf{d} = \mathbf{i}' - \mathbf{i}\) and the direction vector \(\psi = (\psi_1, \dots, \psi_d)\) has \(\psi_k\) = < if \(d_k > 0\), = if \(d_k = 0\), > if \(d_k < 0\). Since the source executes first, \(\mathbf{d}\) is lexicographically non-negative (Theorem 18.7.4 uses this). For a pair of references regardless of order, the direction of a pair of instances \((\mathbf{x}, \mathbf{y})\) (instance \(\mathbf{x}\) of the write, \(\mathbf{y}\) of the read) is computed the same way from \(\mathbf{y} - \mathbf{x}\); * means "any".
Distances of A[i + 1] = A[i] + 1
Iteration \(i\) writes element \(i + 1\); iteration \(i + 1\) reads it: a flow dependence with distance \((1)\), direction \((<)\) — a loop-carried dependence. A[i] = A[i] + 1 has only an anti dependence of distance \((0)\) within each iteration — loop-independent.
Definition 18.6.4 (Dependence system)
For write \(A[f(\mathbf{x})]\) and read \(A[g(\mathbf{y})]\) in a nest with bounds \(L, U\), the dependence system is: for every subscript \(r\), \(f_r(\mathbf{x}) = g_r(\mathbf{y})\), i.e. \(\sum_k a_{rk} x_k - \sum_k b_{rk} y_k = b_{r0} - a_{r0}\); with \(\mathbf{x}, \mathbf{y} \in \mathcal{I}\) (integer) and, for a direction vector \(\psi\), \(x_k < y_k\), \(x_k = y_k\) or \(x_k > y_k\) per \(\psi_k\). A dependence with direction \(\psi\) exists iff this system has an integer solution.
GCD test¶
Theorem 18.6.5 (GCD test)
Let \(g = \gcd(a_1, \dots, a_d, b_1, \dots, b_d)\) for one subscript equation \(\sum_k a_k x_k - \sum_k b_k y_k = c\) (with \(\gcd(0, \dots, 0) = 0\)). The equation has an integer solution (ignoring bounds) iff \(g \mid c\) (for \(g = 0\): iff \(c = 0\)). Hence if \(g \nmid c\) for some subscript, the references are independent.
Proof
If \((\mathbf{x}, \mathbf{y})\) is an integer solution, \(g\) divides every term on the left, hence the sum \(c\). Conversely, by Bézout's identity (induction on the number of coefficients: \(\gcd(u, v) = s u + t v\) for integers \(s, t\)), there are integers \(z_k\) with \(\sum_k a_k z_k - \sum_k b_k z'_k = g\); multiplying by \(c/g\) gives a solution. For \(g = 0\) the left side is identically 0. Independence follows because a dependence would be an integer solution of every subscript equation.
Algorithm 18.6.6 (GCD test for a pair of references)
- Input: the affine subscripts \(f_r\), \(g_r\) of the two references.
- Output: "independent" or "maybe dependent".
- Precondition: integer coefficients.
- Postcondition: "independent" only if no integer solution exists (Theorem 18.6.5).
- Invariant: \(g\) divides every coefficient seen so far.
LLVM's DependenceAnalysis with only its GCD test enabled
Reproduce (clang 23.1.2, opt 23.1.2):
cat > gcd.c <<'X'
void gcd(long *A) {
for (long i = 0; i < 100; i++)
for (long j = 0; j < 100; j++)
A[2 * i + 4 * j] = A[2 * i + 4 * j + 1] + 1;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm gcd.c -o - |
opt -passes='mem2reg,loop-simplify,loop-rotate' -S -o gcd.ll
for t in gcd-miv banerjee-miv; do
echo "== only $t"
opt -passes='print<da>' -da-enable-dependence-test=$t -disable-output gcd.ll 2>&1 | grep -A1 'load.*--> Dst: store'
done
Output (complete):
== only gcd-miv
Src: %0 = load i64, ptr %arrayidx, align 8 --> Dst: store i64 %add6, ptr %arrayidx10, align 8
da analyze - none!
== only banerjee-miv
Src: %0 = load i64, ptr %arrayidx, align 8 --> Dst: store i64 %add6, ptr %arrayidx10, align 8
da analyze - anti [<> <>]!
What to notice: the subscripts \(2i + 4j\) and \(2i' + 4j' + 1\) give the equation \(2i + 4j - 2i' - 4j' = 1\); \(\gcd(2, 4, 2, 4) = 2 \nmid 1\), so the GCD test alone proves the load and the store independent (none!). Banerjee's test, which ignores integrality, cannot: over the reals \(2(i - i') + 4(j - j') = 1\) has solutions, so it only removes the = directions (DA prints the direction vector from the load, its source, to the store). -da-enable-dependence-test is a hidden option that isolates one of DA's tests.
Banerjee test¶
Lemma 18.6.7 (Bounds of \(a x - b y\) under a direction)
For integers \(L \le U\) and \(N = U - L - 1\), write \(t^+ = \max(t, 0)\) and \(t^- = \max(-t, 0)\). Over the region \(L \le x, y \le U\) intersected with the direction constraint, \(a x - b y\) has the minimum and maximum
(for < and >, when \(U > L\); if \(U = L\) the direction is infeasible). The extremes are attained at integer points.
Proof
Each region is a polygon with integer vertices, and a linear function attains its extremes over a polygon at vertices. *: the box \([L, U]^2\), and \(a x\) and \(- b y\) are extremized independently: \(\min_x a x = a^+ L - a^- U\), \(\max_x a x = a^+ U - a^- L\), and similarly for \(-by\). =: the segment \(x = y \in [L, U]\), the function \((a - b) x\). <: the triangle with vertices \((L, L+1)\), \((L, U)\), \((U - 1, U)\); its values there are \(v_1 = (a - b)L - b\), \(v_2 = v_1 - bN\), \(v_3 = v_1 + (a - b) N\). So the minimum is \(v_1 + N \min(0, -b, a - b) = v_1 - N \max(0, b, b - a) = v_1 - N (b + a^-)^+\) and the maximum is \(v_1 + N \max(0, -b, a - b) = v_1 + N (a^+ - b)^+\). >: exchange the roles of \(x\) and \(y\) — the region \(y \le x - 1\) is the < triangle for \((y, x)\) and \(a x - b y = (-b) y - (-a) x\), so apply the < formula with \((a, b) \mapsto (-b, -a)\). (The course oracle checks these formulas against the vertex evaluation on thousands of random instances: tools/course/tests/test_ch18.py, test_banerjee_formulas_equal_vertices.)
Theorem 18.6.8 (Banerjee's inequalities)
For one subscript equation \(\sum_k (a_k x_k - b_k y_k) = c\) and a direction vector \(\psi\) with a constraint per loop, let \([\mathit{LB}_k, \mathit{UB}_k]\) be the bounds of Lemma 18.6.7 for loop \(k\). If \(\sum_k \mathit{LB}_k > c\) or \(\sum_k \mathit{UB}_k < c\), no dependence with direction \(\psi\) exists. If \(\sum_k \mathit{LB}_k \le c \le \sum_k \mathit{UB}_k\), the equation has a real solution in the region (not necessarily an integer one).
Proof
The constraints of different loops involve disjoint variables \((x_k, y_k)\), so the region is a product of the per-loop polygons and the sum's extremes are the sums of the per-loop extremes. Any integer solution with direction \(\psi\) lies in the region, so its left-hand side lies in \([\sum \mathit{LB}_k, \sum \mathit{UB}_k]\); if \(c\) is outside, there is none. Conversely the region is convex and connected, so the continuous function takes every value between its minimum and maximum (intermediate value theorem): \(c\) is attained by a real point.
Algorithm 18.6.9 (Banerjee test with hierarchical direction refinement)
- Input: the subscripts of two references in a nest of depth \(d\), constant bounds.
- Output: the set of direction vectors that the test cannot rule out.
- Precondition: constant (or known) loop bounds; affine subscripts.
- Postcondition: every direction vector of an actual dependence is in the output (Theorem 18.6.8).
- Invariant: a partial vector \(\psi\) (with
*in the unrefined positions) is refined only if it passed the test; if \(\psi\) fails, every refinement of it fails too (the refined region is a subset).
function Banerjee(f, g, bounds):
result ← {}
Refine((*, *, …, *), 1)
return result
function Refine(ψ, k):
for each subscript r:
LB ← f_r0 - g_r0; UB ← LB # move the constants left: test 0 ∈ [LB, UB]
for each loop m: (lo, hi) ← Lemma 18.6.7(a_rm, b_rm, L_m, U_m, ψ_m); LB += lo; UB += hi
if 0 < LB or UB < 0: return # ψ (and all its refinements) excluded
if k > d: add ψ to result; return
for s in {<, =, >}: Refine(ψ with ψ_k = s, k + 1)
LLVM's DependenceAnalysis: the GCD test vs Banerjee's inequalities
Reproduce (clang 23.1.2, opt 23.1.2):
cat > ban.c <<'X'
void ban(long *A) {
for (long i = 0; i < 10; i++)
for (long j = 0; j < 10; j++)
A[i + 10 * j] = A[i + 10 * j + 5] + 1;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm ban.c -o - |
opt -passes='mem2reg,loop-simplify,loop-rotate' -S -o ban.ll
for t in gcd-miv banerjee-miv; do
echo "== only $t"
opt -passes='print<da>' -da-enable-dependence-test=$t -disable-output ban.ll 2>&1 | grep -A1 'load.*--> Dst: store'
done
Output (complete):
== only gcd-miv
Src: %0 = load i64, ptr %arrayidx, align 8 --> Dst: store i64 %add5, ptr %arrayidx8, align 8
da analyze - anti [<> *]!
== only banerjee-miv
Src: %0 = load i64, ptr %arrayidx, align 8 --> Dst: store i64 %add5, ptr %arrayidx8, align 8
da analyze - anti [<> <=]!
What to notice: a real dependence exists (\(i + 10j + 5 = i' + 10j'\): \(i' = i + 5, j' = j\), or \(i' = i - 5, j' = j + 1\)), so neither test can say none. The GCD test (\(\gcd = 1\)) learns nothing beyond LLVM's extension that removes = at the \(i\) level (\(i = i'\) would need \(10(j - j') = -5\)); Banerjee's bounds also exclude > at the \(j\) level (the load's \(j\) cannot be later than the store's), leaving [<> <=], which covers exactly the two actual solutions.
SIV tests and the Delta test¶
Definition 18.6.10 (ZIV, SIV, MIV subscripts)
A subscript pair \((f_r, g_r)\) is ZIV (zero index variable) if neither depends on a loop index, SIV (single index variable) if both depend on at most the same one index \(i_k\), and MIV otherwise. An SIV pair \(a\,i_k + c_1\), \(b\,i'_k + c_2\) is strong if \(a = b \ne 0\), weak-zero if exactly one of \(a, b\) is 0, weak-crossing if \(a = -b \ne 0\). Subscripts that share an index are coupled.
Algorithm 18.6.11 (Practical dependence testing — Goff, Kennedy, Tseng)
- Input: the subscript pairs of two references, the loop bounds.
- Output: "independent", or a direction/distance vector per loop (possibly
*). - Precondition: affine subscripts; bounds known or symbolic.
- Postcondition: "independent" only if no dependence exists; the reported vector covers every dependence (Theorem 18.6.12 for the exact SIV cases).
- Invariant: the constraint vector (distance, direction or "any" per loop) only gets tighter as subscripts are processed.
function PracticalTest(pairs):
partition the subscripts into separable ones and groups of coupled ones
for each separable pair (f, g):
ZIV: if f0 ≠ g0: return independent # constants differ
strong SIV (a·i + c1 vs a·i' + c2):
d ← (c1 - c2) / a # i' - i = d
if d ∉ ℤ or |d| > U - L: return independent
record distance d (direction from its sign) at loop k
weak-zero SIV (a·i + c1 vs c2):
i ← (c2 - c1) / a; if i ∉ ℤ or i ∉ [L, U]: return independent
record "i' = that iteration" (a candidate for peeling)
weak-crossing SIV (a·i + c1 vs -a·i' + c2):
i + i' = (c2 - c1)/a: dependences cross at (c2 - c1)/(2a);
if 2·crossing ∉ ℤ or crossing ∉ [L, U]: return independent
other SIV (exact SIV): solve a·i - b·i' = c2 - c1 with extended Euclid,
intersect the parametric solution with the bounds; empty → independent
MIV: GCD test, then Banerjee (Algorithms 18.6.6, 18.6.9)
for each coupled group (the Delta test):
test its SIV subscripts first; substitute each resulting distance/constraint
into the other subscripts of the group (reducing MIV to SIV or ZIV); repeat
combine the constraints of all loops into the result vector
Theorem 18.6.12 (The strong SIV test is exact)
For the pair \(a\,i + c_1\) (write) and \(a\,i' + c_2\) (read), \(a \ne 0\), in a loop \(i \in [L, U]\), a dependence between iterations \(i\) and \(i'\) exists iff \(d = (c_1 - c_2)/a\) is an integer with \(|d| \le U - L\), and then exactly the pairs \((i, i + d)\) with both in \([L, U]\) touch the same element.
Proof
\(a i + c_1 = a i' + c_2\) iff \(i' - i = (c_1 - c_2)/a\). If this is not an integer, no integer pair satisfies it. If it is, say \(d\), the solutions are \(i' = i + d\), and some pair lies in \([L, U]^2\) iff there is \(i\) with \(L \le i \le U\) and \(L \le i + d \le U\), i.e. iff \(|d| \le U - L\). Every such pair is a solution, so the distance \(d\) is exact.
LLVM's DependenceAnalysis reports distances; GCC's vectorizer uses them
Reproduce (clang 23.1.2, opt 23.1.2):
cat > siv.c <<'X'
void shift(long *A) {
for (long i = 1; i < 100; i++)
A[i + 1] = A[i] + 1;
}
void far(long *A) {
for (long i = 0; i < 10; i++)
A[i] = A[i + 20] + 1;
}
void stencil(long A[100][100]) {
for (long i = 1; i < 100; i++)
for (long j = 1; j < 99; j++)
A[i][j] = A[i - 1][j + 1] + 1;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm siv.c -o - |
opt -passes='mem2reg,loop-simplify,loop-rotate' -S -o siv.ll
opt -passes='print<da>' -disable-output siv.ll 2>&1 | grep -E '^Printing|load.*--> Dst: store' -A1 | grep -E 'Printing|analyze'
Output (complete):
Printing analysis 'Dependence Analysis' for function 'shift':
da analyze - anti [-1]!
Printing analysis 'Dependence Analysis' for function 'far':
da analyze - none!
Printing analysis 'Dependence Analysis' for function 'stencil':
da analyze - anti [-1 1]!
What to notice: each result is for the pair (load = source in program order, store = destination). In shift, strong SIV gives \(d = (0 - 1)/1 = -1\): the store of iteration \(i\) writes what the load of iteration \(i + 1\) reads — a flow dependence of distance \(+1\) from the store, printed as \(-1\) from the load. In far, strong SIV gives \(d = 20 > U - L = 9\): independent (Theorem 18.6.12). In stencil (delinearized to two subscripts, each strong SIV) the distances are \((-1, 1)\) from the load, i.e. flow \((1, -1)\) from the store — the vector that makes interchange illegal (Lesson 18.7).
Omega test¶
Definition 18.6.13 (Integer feasibility; Fourier–Motzkin shadows)
A Presburger conjunction is a finite set of linear equalities and inequalities over integer variables. Eliminating a variable \(z\) from inequalities \(\alpha_p \le a_p z\) (lower bounds, \(a_p > 0\)) and \(b_q z \le \beta_q\) (upper bounds, \(b_q > 0\)) by Fourier–Motzkin gives the real shadow \(\{ b_q \alpha_p \le a_p \beta_q \}\) for all pairs \((p, q)\); the dark shadow is \(\{ a_p \beta_q - b_q \alpha_p \ge (a_p - 1)(b_q - 1) \}\).
Algorithm 18.6.14 (The Omega test — Pugh)
- Input: a Presburger conjunction (the dependence system of Definition 18.6.4, with direction constraints).
- Output: "feasible" (an integer solution exists) or "infeasible".
- Precondition: integer coefficients.
- Postcondition: exact answer (Theorem 18.6.15).
- Invariant: the current problem has an integer solution iff the original does.
function Omega(C):
normalize: divide each constraint by the gcd of its coefficients (tighten
inequality constants by rounding; an equality with a gcd that does
not divide its constant → infeasible)
while C has an equality: # eliminate it exactly
if some variable has coefficient ±1: solve for it and substitute
else: Pugh's "mod-hat" substitution introduces a new variable σ that
reduces the coefficients; repeat
if C has no variables: return feasible iff all constant constraints hold
choose a variable z to eliminate
if every pair of bounds on z has a_p = 1 or b_q = 1: # exact elimination
return Omega(real shadow of z)
if Omega(dark shadow of z) is feasible: return feasible
if Omega(real shadow of z) is infeasible: return infeasible
# splinter: an integer solution outside the dark shadow lies close to a lower bound
for each lower bound α_p ≤ a_p z and each k in 0 .. ⌊(a_p·b_max - a_p - b_max)/b_max⌋:
if Omega(C ∪ {a_p z = α_p + k}) is feasible: return feasible
return infeasible
Theorem 18.6.15 (Shadows)
Eliminating \(z\): (a) if the original conjunction has an integer (or real) solution, its real shadow has one; (b) if the dark shadow has an integer solution, the original has one; (c) if all \(a_p = 1\) or all \(b_q = 1\) for the pairs, the real shadow is exact for integers.
Proof sketch (full proof: [Pug91, §2–3])
(a) If \(z\) satisfies \(\alpha_p \le a_p z\) and \(b_q z \le \beta_q\), multiply and combine: \(b_q \alpha_p \le a_p b_q z \le a_p \beta_q\). (b) For fixed values of the other variables the admissible \(z\) form the real interval \([\max_p \alpha_p/a_p, \min_q \beta_q/b_q]\); the dark-shadow inequality says every pair of bounds leaves a gap of length at least \((a_p - 1)(b_q - 1)/(a_p b_q)\) plus one step, which Pugh shows guarantees an integer inside. (c) With a unit coefficient on one side, the bound \(\lceil \alpha_p/a_p \rceil \le \lfloor \beta_q / b_q \rfloor\) follows from \(b_q \alpha_p \le a_p \beta_q\) directly. Splintering covers the integer solutions not in the dark shadow: they must satisfy some lower bound nearly with equality.
An exact integer test (isl, the Omega test's successor) refutes what GCD and Banerjee cannot
Reproduce (islpy 2026.2.2, which bundles isl; Python via uv):
cat > omega.py <<'X'
import islpy as isl
# for i in [1,10], j in [1,10]: A[i + 2j][2i + j] = A[i + 2j + 1][2i + j] + 1
# write at (i, j), read at (i2, j2): can they touch the same element?
space = ("{ [i, j, i2, j2] : 1 <= i <= 10 and 1 <= j <= 10"
" and 1 <= i2 <= 10 and 1 <= j2 <= 10")
sub0 = isl.Set(space + " and i + 2j = i2 + 2j2 + 1 }")
sub1 = isl.Set(space + " and 2i + j = 2i2 + j2 }")
both = sub0.intersect(sub1)
print("subscript 0 alone:", "dependence" if not sub0.is_empty() else "independent")
print("subscript 1 alone:", "dependence" if not sub1.is_empty() else "independent")
print("both (exact, integer):", "dependence" if not both.is_empty() else "independent")
# eliminate j2 and i2 as the Omega test does: what is left is a statement about i, j
print("projected onto (i, j):", both.project_out(isl.dim_type.set, 2, 2))
X
uv run --quiet --no-project --with islpy==2026.2.2 python omega.py
Output (complete):
subscript 0 alone: dependence
subscript 1 alone: dependence
both (exact, integer): independent
projected onto (i, j): { [i, j] : false }
What to notice: each subscript alone has integer solutions (GCD 1 in both), and Banerjee's test run subscript by subscript cannot exclude the directions <> and >< (§3). Together the two equations force \(\Delta i + 2\Delta j = -1\) and \(2 \Delta i + \Delta j = 0\), whose only real solution \(\Delta i = 1/3\) is not an integer — an exact integer test (isl uses Presburger arithmetic like the Omega test) proves independence. Neither GCC nor LLVM ships the Omega test today; this is the class of question that isl answers for Polly and GCC's Graphite (Lesson 18.7).
Runtime checks (LoopAccessAnalysis)¶
Definition 18.6.16 (Byte distance; safe dependence for vectorization)
For two accesses in an innermost loop with add-recurrence addresses \(\{p, +, s\}\) and \(\{p + \delta, +, s\}\) over the same base pointer \(p\) (Lesson 18.3), the dependence distance is \(\delta\) bytes, i.e. \(\delta / s\) iterations. A dependence of distance \(\delta > 0\) from an earlier write to a later read ("backward" in LAA's terms when the sink precedes the source in the body) is safe for vectorization factor \(VF\) if \(\delta \ge VF \cdot\) (element size): no vector iteration reads what the same vector iteration writes. Accesses through different base pointers whose relation is unknown are grouped by base, each group summarized by the range \([\mathit{Low}, \mathit{High})\) it touches over the whole loop.
Algorithm 18.6.17 (LoopAccessAnalysis, simplified)
- Input: an innermost loop with its loads and stores, SCEV, alias analysis.
- Output: "safe", "safe with runtime checks" (and the checks), or "unsafe"; the maximum safe VF.
- Precondition: the loop's trip count is computable (for the ranges); addresses are add recurrences.
- Postcondition: executing the loop with any VF ≤ the maximum safe VF, under the runtime checks, gives the same results as the scalar loop (Theorem 18.6.18).
- Invariant: —
function LAA(L):
partition accesses into alias sets (alias analysis); inside each set, by base pointer
for each pair of accesses with the same base and at least one store:
δ ← SCEV(addr2) - SCEV(addr1)
if δ is not a constant: unknown → unsafe unless a runtime check can cover it
classify: forward (no loop-carried reordering), backward with δ ≥ VF·size (safe
up to VF = δ / size), backward with small δ → unsafe; record MaxSafeVF
(LLVM also rejects a backward δ that would defeat store-to-load forwarding)
for pairs with different bases that alias analysis cannot separate:
group accesses by base; Low/High of each group ← min/max of its recurrences over
the trip count; emit one overlap check per pair of groups (Algorithm 18.5.12)
return the classification, the checks, MaxSafeVF
Theorem 18.6.18 (Runtime checks cover all cross-base dependences)
If for every pair of groups the ranges \([\mathit{Low}_A, \mathit{High}_A)\) and \([\mathit{Low}_B, \mathit{High}_B)\) contain every byte the loop accesses through the group, and the check \(\neg(\mathit{Low}_A < \mathit{High}_B \wedge \mathit{Low}_B < \mathit{High}_A)\) succeeds, then no access through \(A\) and no access through \(B\) touch the same byte during the loop.
Proof
Two accesses touching the same byte would put that byte in both ranges, so the ranges would intersect; half-open intervals \([l_1, h_1)\) and \([l_2, h_2)\) intersect iff \(l_1 < h_2 \wedge l_2 < h_1\). The check is its negation.
LLVM's LoopAccessAnalysis: runtime checks for a/b, and a distance that limits vectorization
Reproduce (clang 23.1.2, opt 23.1.2):
cat > laa.c <<'X'
void add(long *a, long *b, long n) {
for (long i = 0; i < n; i++)
a[i] = a[i] + b[i];
}
void rec(long *a, long n) {
for (long i = 0; i < n; i++)
a[i + 3] = a[i] + 1;
}
X
clang-23 -O1 -fno-vectorize -fno-unroll-loops -fno-discard-value-names -S -emit-llvm laa.c -o laa.ll
opt -passes='print<access-info>' -disable-output laa.ll 2>&1
Output (complete):
Printing analysis 'Loop Access Analysis' for function 'add':
for.body:
Memory dependences are safe with run-time checks
Dependences:
Run-time memory checks:
Check 0:
Comparing group GRP0:
%arrayidx = getelementptr inbounds nuw [8 x i8], ptr %a, i64 %i.09
%arrayidx = getelementptr inbounds nuw [8 x i8], ptr %a, i64 %i.09
Against group GRP1:
%arrayidx1 = getelementptr inbounds nuw [8 x i8], ptr %b, i64 %i.09
Grouped accesses:
Group GRP0:
(Low: %a High: ((8 * %n) + %a))
Member: {%a,+,8}<nuw><%for.body>
Member: {%a,+,8}<nuw><%for.body>
Group GRP1:
(Low: %b High: ((8 * %n) + %b))
Member: {%b,+,8}<nuw><%for.body>
Non vectorizable stores to invariant address were not found in loop.
SCEV assumptions:
Expressions re-written:
Printing analysis 'Loop Access Analysis' for function 'rec':
for.body:
Report: unsafe dependent memory operations in loop. Use #pragma clang loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
Backward loop carried data dependence that prevents store-to-load forwarding.
Dependences:
BackwardVectorizableButPreventsForwarding:
%0 = load i64, ptr %arrayidx, align 8, !tbaa !9 ->
store i64 %add, ptr %arrayidx2, align 8, !tbaa !9
Run-time memory checks:
Grouped accesses:
Non vectorizable stores to invariant address were not found in loop.
SCEV assumptions:
Expressions re-written:
What to notice: for add, the dependences are "safe with run-time checks": one check between group GRP0 (the load and store of a, range \([a, a + 8n)\)) and GRP1 (b) — exactly the check loop-versioning emitted in Lesson 18.5. For rec, a[i+3] and a[i] share a base: the distance is 24 bytes, 3 elements. By Definition 18.6.16 alone it is safe for \(VF \le 3\) (in practice 2), and LAA's type name says as much: BackwardVectorizableButPreventsForwarding. But LLVM 23 treats that type as unsafe (Dependence::isSafeForVectorization returns Unsafe): a vector store of a[i+3..] followed two or three iterations later by an overlapping vector load of a[i..] would stall on store-to-load forwarding, and LAA judges the scalar loop faster. The report line is the consequence. That is a cost heuristic inside a legality analysis; GCC, without it, vectorizes the same loop with VF 2 — see below.
GCC's vectorizer: dependence distance 3 allows vectors of 2
Reproduce (gcc 14.2.0):
cat > rec.c <<'X'
void rec(long *a, long n) {
for (long i = 0; i < n; i++)
a[i + 3] = a[i] + 1;
}
X
gcc-14 -O2 -ftree-vectorize -fdump-tree-vect-details -c rec.c -o /dev/null
grep -E 'dependence distance|optimized: loop vectorized' rec.c.*.vect | sort -u
Output (complete):
rec.c:2:22: note: dependence distance = 3.
rec.c:2:22: note: dependence distance >= VF.
rec.c:2:22: optimized: loop vectorized using 16 byte vectors
What to notice: GCC computes the same distance (3 iterations) with its own data-dependence analysis (gcc/tree-data-ref.cc) and vectorizes with 16-byte vectors — two longs, \(VF = 2 \le 3\) (Definition 18.6.16).
3. Worked example¶
Two problems from the lab corpus (labs/ch18-loops/corpus/deps.dep), traced with the course oracle (./course drill dependence-test uses the same code).
GCD test on the running example¶
reverse: for i = 1 to 10: A[i] = A[11 - i] + 1. Write subscript \(i\) (\(a = 1\), \(a_0 = 0\)), read subscript \(11 - i'\) (\(b = -1\), \(b_0 = 11\)). Equation \(x + y = 11\). \(\gcd(1, -1) = 1\) divides \(11 - 0\): maybe dependent.
coupled: for i, j = 1 to 10: A[i + 2j][2i + j] = A[i + 2j + 1][2i + j] + 1. Subscript 0: \(\gcd(1, 2, 1, 2) = 1 \mid 1\); subscript 1: \(\gcd(2, 1, 2, 1) = 1 \mid 0\): maybe dependent.
Banerjee test on the running example¶
reverse, with \(L = 1\), \(U = 10\), \(N = 8\), constant \(f_0 - g_0 = -11\), \(a = 1\), \(b = -1\) (\(a^+ = 1, a^- = 0, b^+ = 0, b^- = 1\)):
| direction | bounds of \(x - (-1)y\) (Lemma 18.6.7) | \(+ (f_0 - g_0)\) | 0 inside? |
|---|---|---|---|
* |
\([1 \cdot 1 - 0 - 0 + 1 \cdot 1,\ 10 - 0 - 0 + 10] = [2, 20]\) | \([-9, 9]\) | yes |
< |
\([-(0 - 1)^+ \cdot 8 + 2 \cdot 1 + 1,\ (1 + 1)^+ \cdot 8 + 2 + 1] = [3, 19]\) | \([-8, 8]\) | yes |
= |
\([2 \cdot 1, 2 \cdot 10] = [2, 20]\) | \([-9, 9]\) | yes |
> |
\([-(0 - 1)^+ \cdot 8 + 2 \cdot 1 + 1,\ (1 + 1)^+ \cdot 8 + 2 + 1] = [3, 19]\) | \([-8, 8]\) | yes |
Banerjee rules out nothing. The exact answer (enumeration): directions \(\{<, >\}\) with distances \(1, 3, 5, 7, 9\) — never =, because \(2i = 11\) has no integer solution: the real solution \(i = 5.5\) is what Banerjee "sees".
coupled, subscript by subscript (bounds \([1, 10]\); computed by the course oracle banerjee_test in tools/course/lib/loops.py; "—" means the test already failed at subscript 0):
| direction | subscript 0: range of \(f_0(x) - g_0(y)\) | subscript 1 | survives? |
|---|---|---|---|
<< |
\([-28, -4]\) | — | no |
<= |
\([-10, -2]\) | — | no |
<> |
\([-8, 16]\) | \([-17, 7]\) | yes |
=< |
\([-19, -3]\) | — | no |
== |
\([-1, -1]\) | — | no |
=> |
\([1, 17]\) | — | no |
>< |
\([-18, 6]\) | \([-7, 17]\) | yes |
>= |
\([0, 8]\) | \([2, 18]\) | no |
>> |
\([2, 26]\) | — | no |
Two directions survive although no dependence exists: the Omega test (or isl, the real-world box above) is needed.
SIV tests and the Delta test on the running example¶
stencil: A[i][j] = A[i-1][j+1] + 1 has two separable strong-SIV subscripts: \(d_i = (0 - (-1))/1 = 1\) and \(d_j = (0 - 1)/1 = -1\), both within \(U - L\). Distance vector \((1, -1)\), direction \((<, >)\) — exact, matching DA's [-1 1] from the load. For reverse the subscript pair \(i\) vs \(11 - i'\) is weak-crossing (\(a = 1\), \(b = -1\)): the dependences cross at \((11 - 0)/2 = 5.5\); since \(2 \cdot 5.5 = 11 \in \mathbb{Z}\) and \(5.5 \in [1, 10]\), dependences exist, and the crossing point says every write \(i \le 5\) is read by iteration \(11 - i > i\) — exactly the directions \(\{<, >\}\) with no =, the precision Banerjee lacked.
Omega test on the running example¶
For coupled with direction <> (\(x_i < y_i\), \(x_j > y_j\)), the Omega test eliminates the equalities: from subscript 1, \(2x_i + x_j = 2y_i + y_j\) gives \(x_j = 2y_i + y_j - 2x_i\) (unit coefficient). Substituting into subscript 0: \(x_i + 2(2y_i + y_j - 2x_i) = y_i + 2y_j + 1\), i.e. \(-3x_i + 3y_i = 1\) — an equality whose coefficients have \(\gcd = 3 \nmid 1\): infeasible at the normalization step, for every direction. Exact answer: independent.
Runtime checks (LoopAccessAnalysis) on the running example¶
add(a, b, n): accesses \(\{a,+,8\}\) (load and store) and \(\{b,+,8\}\) (load); different bases, unknown relation → two groups: \([a, a + 8n)\) and \([b, b + 8n)\), one check (Theorem 18.6.18). rec(a, n): same base, \(\delta = 24\) bytes \(= 3\) elements \(\Rightarrow\) MaxSafeVF \(= 3\) by Definition 18.6.16 — legal for VF 2 — although LLVM's forwarding heuristic then declines it (box above).
Try it
./course drill dependence-test --seed 2 --difficulty medium --solution (a 2-deep nest with flow distances), then --difficulty hard for coupled two-dimensional subscripts.
4. Invariants and correctness¶
GCD test¶
Theorem 18.6.5 is the correctness statement: the test is sound (it never reports "independent" when an integer solution exists) and exact for integrality without bounds.
Banerjee test¶
Theorem 18.6.19 (Soundness of subscript-by-subscript testing with refinement)
Algorithm 18.6.9 outputs every direction vector \(\psi\) for which a dependence exists. Testing subscripts separately is sound but not exact for coupled subscripts.
Proof
A dependence with direction \(\psi\) is an integer solution of all subscript equations with the direction constraints; in particular each single equation has one, so by Theorem 18.6.8 each subscript's bounds contain 0 for \(\psi\) and for every coarser vector (the region grows when a position becomes *). Hence the refinement never prunes an ancestor of \(\psi\), and \(\psi\) is reached and output. Non-exactness: the coupled example of §3 has solutions for each equation separately (with directions <> and ><) but none for both.
SIV tests and the Delta test¶
Theorem 18.6.12 proves the strong SIV case. Weak-zero SIV is exact by the same argument (\(i = (c_2 - c_1)/a\) must be an integer in range), weak-crossing SIV by substituting \(i' = (c_2 - c_1)/a - i\), and the exact SIV test by the parametric solution of a two-variable linear Diophantine equation [GKT91, §4]. The Delta test's propagation substitutes exact SIV facts into coupled subscripts — each substitution preserves the solution set, so soundness is preserved and precision can only improve [GKT91, §5].
Omega test¶
Theorem 18.6.15 gives the shadow facts; with them, each step of Algorithm 18.6.14 preserves integer feasibility: equality elimination is an exact change of variables, the dark shadow is sufficient, the real shadow necessary, and splintering enumerates the remaining cases. The algorithm terminates because every step removes a variable or reduces a coefficient [Pug91].
Runtime checks (LoopAccessAnalysis)¶
Theorem 18.6.18 covers the cross-base accesses; for same-base pairs, the classification by constant distance is exact (a constant \(\delta\) means the two accesses of iterations \(k\) and \(k'\) collide iff \(s(k' - k) = \delta\)). "Unknown" distances are never classified safe without a check.
5. Complexity¶
\(d\) = loop depth, \(m\) = number of subscripts, \(B\) = bit width of coefficients; \(n_c\) = number of constraints, \(n_v\) = variables in the Omega problem; \(g\) = pointer groups.
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| GCD test | \(O(m\,d)\) gcd computations, each \(O(B^2)\) bit operations | microseconds | \(O(1)\) | \(m\), \(d\), \(B\) |
| Banerjee test | \(O(m\,d \cdot 3^d)\) with refinement | small \(d\): tens of evaluations | \(O(d)\) stack | |
| SIV tests and the Delta test | \(O(m\,d)\) for separable subscripts; exact SIV \(O(B^2)\) (extended Euclid) | constant per subscript | \(O(m)\) | |
| Omega test | worst case exponential (integer programming is NP-complete) | "a few milliseconds" per problem [Pug91] | \(O(n_c^2)\) per FM step | \(n_c\), \(n_v\) |
| Runtime checks (LAA) | \(O(a^2)\) pairs of accesses; \(O(g^2)\) checks | linear in accesses with alias sets | \(O(a)\) | \(a\) accesses |
Proposition 18.6.20 (Cost of direction refinement; Fourier–Motzkin growth)
Algorithm 18.6.9 performs at most \(1 + 3 + \dots + 3^d = (3^{d+1} - 1)/2\) tests of \(O(m\,d)\) each. One Fourier–Motzkin step on \(p\) lower and \(q\) upper bounds produces \(p\,q\) constraints; \(k\) steps can grow \(n_c\) constraints to \(O((n_c/2)^{2^k})\).
Proof
The refinement tree has \(3^j\) nodes at depth \(j\) (three directions per level), each testing all \(m\) subscripts over \(d\) loops. For FM, each pair (lower, upper) yields one new constraint; with \(n_c/2\) of each, the new count is \((n_c/2)^2\), and squaring repeats with every eliminated variable.
Pathological input. A \(d\)-deep nest where no direction can be excluded makes Banerjee explore all \(3^d\) leaves (LLVM caps the recursion depth with da-miv-max-level-threshold = 7 [LLVM-DA]). For the Omega test, constraints with large non-unit coefficients force splintering, whose number of subproblems grows with the coefficients; Pugh reports that such cases are rare in dependence problems [Pug91].
At scale. Goff, Kennedy and Tseng measured that in their Fortran corpus the overwhelming majority of subscript pairs are ZIV or SIV and are decided by the cheap exact tests [GKT91, §6]; that measurement is why LLVM's DA implements their design.
6. Variants and refinements¶
GCD test¶
- GCD with equality constraints per level (Wolfe [Wol96]; LLVM's
gcdMIVtestsecond half): assume \(x_k = y_k\) for one loop and re-run GCD on the reduced equation to remove the=direction — trade-off: \(d\) more gcds, finer directions (the real-world box's[<> *]). - Symbolic coefficients: treat \(N \cdot i\) with invariant \(N\) as coefficient \(N\) and use "a common divisor" — trade-off: handles linearized subscripts, weaker.
Banerjee test¶
- Trapezoidal bounds (loop bounds depending on outer indices) [Ban88; Wol96] — trade-off: more complex bound formulas, needed for triangular nests.
- The I-test (Kong, Klappholz, Psarris): combines GCD and Banerjee into an interval equation test that is exact more often — trade-off: more work per subscript.
SIV tests and the Delta test¶
- Delinearization (LLVM
tryDelinearize): recover the separate subscripts of a linearizedA[i*N + j]so that SIV tests apply — trade-off: needs runtime or static checks that indices stay in bounds (da-disable-delinearization-checks). - RDIV (restricted double index variable) tests (
exactRDIVtest,symbolicRDIVtest): subscripts with different indices of different loops — trade-off: more special cases.
Omega test¶
- Polyhedral dependence analysis [Fea91; Ver10]: compute the whole dependence relation (a Presburger map) instead of a yes/no answer — trade-off: heavier, but gives exact dataflow (Lesson 18.7).
- Parametric integer programming (PIP) [Fea91]: lexicographic minima of parametric polyhedra, for exact last-writer (value-based) dependences — trade-off: more expensive, eliminates false dependences through overwritten values.
Runtime checks (LoopAccessAnalysis)¶
- Predicated SCEV assumptions (Lesson 18.3): add checks that make unknown strides or wrap-around analyzable — trade-off: more runtime checks.
- Check merging and limits (
runtime-memory-check-threshold, check grouping by base) — trade-off: fewer checks, coarser ranges.
7. In real compilers¶
GCD test¶
LLVM
llvm/lib/Analysis/DependenceAnalysis.cpp — DependenceInfo::gcdMIVtest (with the per-level = refinement), called from testMIV [LLVM-DA] (LLVM 23.1.2).
- GCC
gcc/tree-data-ref.cc—analyze_miv_subscriptapplies a GCD test to multi-index subscripts (GCC 15) [GCC-DataRef].
The real-world box for this technique is in §2.
Banerjee test¶
LLVM
llvm/lib/Analysis/DependenceAnalysis.cpp — DependenceInfo::banerjeeMIVtest with findBoundsALL, findBoundsEQ, findBoundsLT, findBoundsGT (the four cases of Lemma 18.6.7, in Wolfe's normalized form); disabled by default in LLVM 23 (-da-enable-dependence-test=banerjee-miv or all turns it on) [LLVM-DA].
Find where LLVM does it. Open DependenceAnalysis.cpp and find which test the Default value of DependenceTestType excludes. Question: which one? (Quiz da-find-default.)
The real-world box for this technique is in §2.
SIV tests and the Delta test¶
LLVM
llvm/lib/Analysis/DependenceAnalysis.cpp — testZIV, testSIV dispatching to strongSIVtest, weakCrossingSIVtest, weakZeroSrcSIVtest, weakZeroDstSIVtest, exactSIVtest; tryDelinearize; DependenceInfo::depends is the entry point [LLVM-DA] (LLVM 23.1.2).
- GCC
gcc/tree-data-ref.cc—analyze_siv_subscript,analyze_ziv_subscript, andcompute_affine_dependence(GCC 15) [GCC-DataRef].
The real-world boxes for this technique are in §2 (DA's distances and GCC's vectorizer).
Omega test¶
Libraries
The Omega library (Pugh's group, University of Maryland) was the reference implementation [Pug91]; GCC used an Omega solver (omega.c) until GCC 5 removed it. Today exact integer dependence analysis is done with isl [Ver10] in Polly (polly/lib/Analysis/DependenceInfo.cpp) and GCC's Graphite (gcc/graphite-dependences.cc) (Lesson 18.7) [Polly-Docs].
The real-world box for this technique is in §2 (isl).
Runtime checks (LoopAccessAnalysis)¶
LLVM
llvm/lib/Analysis/LoopAccessAnalysis.cpp — LoopAccessInfo::analyzeLoop, MemoryDepChecker::isDependent (distance classification: Forward, Backward, BackwardVectorizable, BackwardVectorizableButPreventsForwarding, Unknown), RuntimePointerChecking::generateChecks [LLVM-LAA] (LLVM 23.1.2).
- GCC
gcc/tree-vect-data-refs.cc—vect_analyze_data_ref_dependencesandvect_prune_runtime_alias_test_list(GCC 15).
Find where LLVM does it. In LoopAccessAnalysis.cpp, find the enum of dependence kinds. Question: which kind did LAA print for rec? (Quiz laa-find-kind.)
The real-world box for this technique is in §2.
8. Comparison¶
| Technique | Power / precision | Speed | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| GCD test | Exact for integrality, ignores bounds; proves independence only by divisibility | \(O(md)\) gcds | Yes/no (+ per-level = removal) |
Very low | First filter; MIV subscripts (LLVM gcdMIVtest) |
| Banerjee test | Uses bounds and directions, ignores integrality; subscript by subscript | \(O(md\,3^d)\) with refinement | Direction vectors | Low | MIV subscripts, direction vectors for interchange |
| SIV tests and the Delta test | Exact for ZIV and SIV (the common case); coupled subscripts via propagation | \(O(md)\) | Exact distances | Medium (many cases) | LLVM DependenceAnalysis, GCC tree-data-ref.cc |
| Omega test | Exact integer feasibility for any affine system | Exponential worst, fast in practice | Yes/no, or exact dependence relations (with isl) | High | Polyhedral compilers (via isl) |
| Runtime checks (LAA) | Constant distances exact; unknown aliasing deferred to a run-time check | Linear-ish | Safe / safe with checks / unsafe, MaxSafeVF | Medium | LLVM vectorizer, distribution, versioning |
On the lab corpus (ch18-loops dep labs/ch18-loops/corpus/deps.dep): of 67 problems, 16 are exactly independent; the GCD test proves 4, Banerjee 11 — neither ever wrongly (the --check mode verifies soundness against enumeration).
Choose GCD then Banerjee as cheap filters. Choose the SIV tests for single-index subscripts (most real code). Choose an exact integer test (Omega, isl) when precision pays — polyhedral optimization, parallelization. Choose runtime checks when the obstacle is unknown aliasing rather than a real dependence.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch18.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| GCD test | gcd-verdict, gcd-ignores-bounds |
./course drill dependence-test |
gcd-test |
Lab Part C (C1) |
| Banerjee test | banerjee-bounds, banerjee-directions, da-find-default |
./course drill dependence-test --difficulty hard |
banerjee |
Lab Part C (C2) |
| SIV tests and the Delta test | siv-distance, siv-weak-crossing |
./course drill dependence-test (exact distances in the worked solution) |
siv-tests |
— |
| Omega test | omega-coupled, omega-shadow |
./course drill dependence-test --difficulty hard (coupled problems where only an exact test decides) |
omega |
— |
| Runtime checks (LAA) | laa-maxvf, laa-find-kind |
./course drill dependence-test (distances) |
runtime-checks |
— |
Pitfall
A test that "passes" (cannot prove independence) does not prove a dependence. GCD and Banerjee are independence tests: "maybe dependent" is their only other answer. Only exact tests (SIV, Omega, enumeration) establish that a dependence exists and at which distance.
References¶
See the chapter references.