Zero-cost GPU bounds elision with Lean 4 and Zig
A GPU shader can repeat the same safety work millions of times. Before using a calculated index, it may need to keep that index inside a buffer whose size is only known at runtime. Those checks are there for a reason. Removing them because the programmer expects the index to fit would be a bad optimization.
The implementation linked here asks whether we can establish that fact before launching the shader. If every index a dispatch can produce fits in the buffer, we can check the dispatch once and leave the repeated accesses alone.
Take this small loop. The location written depends on the invocation ID and the loop variable:
@group(0) @binding(0) var<storage, read_write> data: array<u32>;
@compute @workgroup_size(8)
fn main(@builtin(global_invocation_id) gid: vec3u) {
for (var i: u32 = 1u; i <= 4u; i = i + 2u) {
data[gid.x * 2u + i * 3u + 1u] = 1u;
}
}
The compiler has to account for both. It cannot infer from one successful run that every future launch will be safe. In the default robust path, the access keeps a clamp that uses the buffer length.
Lean lets us state the relationship for a whole family of indices. The proof says that, under its conditions, the largest possible access remains in bounds. It does not know which buffer the application will supply later. The runtime still has to check that the actual launch satisfies those conditions.
Zig connects the two. At build time it checks that the extracted proof information matches the expected theorem inventory and source provenance. When the shader is compiled, a matcher looks for an index expression covered by that proof. If it recognizes the expression, it produces a condition to check before dispatch. If it cannot establish the match, the clamp stays.
For this loop, the recorded match includes the invocation multiplier, the loop bound and stride, the element size, and the offset. The host uses them to calculate how much buffer storage the dispatch requires, with checked arithmetic. The shader then no longer needs to ask for the buffer length on every access.
The recorded comparison shows the trade in three small shader cases. The largest reported improvement was in compilation, roughly a quarter of the time. GPU timestamps changed much less. That is a reason to keep the measurements separate, rather than describing every reduction in generated code as a large execution speedup.
What I like about this is that the proof has a job after someone reads it. It controls a specific compiler transformation, and the build rejects a mismatch instead of quietly trusting an old proof file. The check has moved to a place where it can cover the whole dispatch; it has not disappeared.
Proof, implementation and recorded measurements
The code and measurements below are retained from the linked repository revision. They are not a new benchmark run.
- ComputeBounds.lean: the Lean theorem family itself, including the affine loop case this article uses.
- Extract.lean: the Lean extraction step that turns proved conditions into a machine-readable artifact.
- proven-conditions.json: the extracted proof manifest Zig actually consumes at build time.
- build.zig: where the build reads the Lean artifact, provenance, and proof options into
build_options. - lean-proof-patterns.json: the map from stable runtime pattern names to exact theorem names and callsites.
- lean_proof.zig: the comptime gate that rejects missing theorems or provenance drift with
@compileError. - affine_loop_storage.wgsl: the exact motivating affine-loop shader used in the proof metrics pass.
- dispatch_proof_match.zig: the matcher that recognizes affine WGSL index shapes and emits one dispatch precondition.
- ir_transform_robustness.zig: the rewrite pass where the fallback clamp stays or disappears.
- dispatch_preconditions.zig: the byte-count check that validates a matched precondition before launch.
- doe_compute_preconditions_native.zig: the host-side launch check that replaces per-access shader guards.
Default clamp, Lean theorem and runtime checks
gid.x * 2u + i * 3u + 1u
if (config.elide_proven_bounds) {
if (dispatch_proof_match.try_elide_storage_index(module, function, function_id, i, index_data)) |precondition| {
module.dispatch_preconditions.append(module.allocator, precondition) catch return error.OutOfMemory;
continue;
}
}
try clamp_runtime_sized(allocator, module, function, i);
const al_args = try function.append_expr_args(allocator, &.{base_ref});
const array_length_id = try function.append_expr(allocator, .{
.ty = u32_ty,
.category = .value,
.data = .{ .call = .{
.name = try ir.dup_string(allocator, "arrayLength"),
.kind = .builtin,
.args = al_args,
} },
});
const one_id = try function.append_expr(allocator, .{
.ty = u32_ty,
.category = .value,
.data = .{ .int_lit = 1 },
});
const sub_id = try function.append_expr(allocator, .{
.ty = u32_ty,
.category = .value,
.data = .{ .binary = .{
.op = .sub,
.lhs = array_length_id,
.rhs = one_id,
} },
});
const min_args = try function.append_expr_args(allocator, &.{ original_index, sub_id });
const min_id = try function.append_expr(allocator, .{
.ty = u32_ty,
.category = .value,
.data = .{ .call = .{
.name = try ir.dup_string(allocator, "min"),
.kind = .builtin,
.args = min_args,
} },
});
theorem gid_affine_plus_scaled_loop_index_inbounds_when_dispatch_fits
(workgroup_id_x local_id_x workgroup_size_x num_workgroups_x array_length : Nat)
(gid_stride limit i loop_stride offset : Nat)
(h_gid_stride : 0 < gid_stride)
(h_loop_stride : 0 < loop_stride)
(h_i : i < limit)
(h_wid : workgroup_id_x < num_workgroups_x)
(h_lid : local_id_x < workgroup_size_x)
(h_fit : workgroup_size_x * num_workgroups_x * gid_stride + limit * loop_stride + offset ≤ array_length) :
globalInvocationId workgroup_id_x local_id_x workgroup_size_x * gid_stride + i * loop_stride + offset < array_length := by
let gid := globalInvocationId workgroup_id_x local_id_x workgroup_size_x
let total := workgroup_size_x * num_workgroups_x
have h_gid_lt_total : gid < total := by
dsimp [gid, total]
exact gid_component_lt_total
workgroup_id_x local_id_x workgroup_size_x num_workgroups_x
(workgroup_size_x * num_workgroups_x)
h_wid h_lid (Nat.le_refl _)
have h_gid_scaled_lt :
gid * gid_stride < total * gid_stride := by
exact Nat.mul_lt_mul_of_pos_right h_gid_lt_total h_gid_stride
have h_loop_scaled_lt :
i * loop_stride < limit * loop_stride := by
exact Nat.mul_lt_mul_of_pos_right h_i h_loop_stride
have h_sum_lt :
gid * gid_stride + i * loop_stride <
total * gid_stride + limit * loop_stride := by
exact Nat.add_lt_add h_gid_scaled_lt h_loop_scaled_lt
have h_offset_lt :
gid * gid_stride + i * loop_stride + offset <
(total * gid_stride + limit * loop_stride) + offset := by
exact Nat.add_lt_add_right h_sum_lt offset
calc
gid * gid_stride + i * loop_stride + offset <
(total * gid_stride + limit * loop_stride) + offset := h_offset_lt
_ ≤ array_length := h_fit
if (match_gid_component_loop_affine_plus_offset(function, index_data.index, .global_invocation_id)) |match| {
if (loop_match.find_bounded_loop_limit(function, expr_id, match.local_idx)) |loop_limit| {
return .{
.kind = .gid_component,
.gid_axis = match.axis,
.storage_binding = binding,
.element_multiplier = match.gid_multiplier,
.loop_limit = loop_limit,
.loop_limit_multiplier = match.loop_multiplier,
.element_stride_bytes = element_stride_bytes,
.element_offset = match.offset,
};
}
}
.gid_component => blk: {
const axis = precondition.gid_axis;
if (axis >= dispatch_workgroups.len or axis >= workgroup_size.len) {
return error.DispatchPreconditionFailed;
}
const total_invocations = try invocation_extent(dispatch_workgroups[axis], workgroup_size[axis]);
const scaled_invocations = try std.math.mul(u64, total_invocations, precondition.element_multiplier);
const loop_elements = try std.math.mul(u64, precondition.loop_limit, precondition.loop_limit_multiplier);
const affine_elements = try std.math.add(u64, scaled_invocations, loop_elements);
const total_elements = try std.math.add(u64, affine_elements, precondition.element_offset);
break :blk try std.math.mul(u64, total_elements, precondition.element_stride_bytes);
},
The motivating match uses axis 0, binding (0, 0), invocation multiplier 2, exclusive loop limit 5, loop multiplier 3, four-byte elements, and offset 1. The exclusive bound comes from normalizing i <= 4 to i < 5.
Recorded shader measurements
| Shader | Size | min(...) |
_doe_sizes |
needs_sizes_buf |
Dispatch preconditions | Compile p50 |
Native Vulkan p50/dispatch |
GPU timestamp |
|---|---|---|---|---|---|---|---|---|
affine_loop_storage |
356 B -> 267 B |
1 -> 0 |
true -> false |
true -> false |
0 -> 1 |
77,997 -> 56,967 ns (-27.0%) |
31,666.7 -> 28,135.4 ns (-11.2%) |
515.9 -> 507.5 ns (-1.6%) |
tiled_storage |
322 B -> 233 B |
1 -> 0 |
true -> false |
true -> false |
0 -> 1 |
61,306 -> 46,959 ns (-23.4%) |
28,000.6 -> 27,571.3 ns (-1.5%) |
510.3 -> 502.3 ns (-1.6%) |
flat_2d_storage |
387 B -> 298 B |
1 -> 0 |
true -> false |
true -> false |
0 -> 1 |
69,471 -> 51,657 ns (-25.6%) |
28,465.2 -> 28,248.2 ns (-0.8%) |
547.6 -> 531.4 ns (-3.0%) |
Reproduction note: Build with -Dlean-verified=false and -Dlean-verified=true. See proof_metrics_summary.json.