← Back

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.

Side-by-side flow diagram comparing the default robust path and the proof-backed path for bounds elision
The safety check moves from repeated in-kernel clamps to one proof-backed dispatch precondition.

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.

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%)
Lead image from the Substack version of Zero cost GPU bounds elision with Lean 4 and Zig
Lead image from the Substack version of this post.
Grouped bar chart showing compile, native dispatch, and GPU timestamp reductions across three proof-backed shader cases
The measured benefit is front-loaded into compile time, with smaller but still real steady-state wins once the shader no longer carries clamp and size-buffer machinery.

Reproduction note: Build with -Dlean-verified=false and -Dlean-verified=true. See proof_metrics_summary.json.

Additional references from the original article