LLVM-Guided Optimization

Overview

Optimize Zig hot paths by emitting LLVM IR, hand-optimizing it, and shipping the optimized .ll files alongside the Zig source. Two output paths:

1. Keep the .ll file -- when the optimization can't be expressed in Zig (custom SIMD scheduling, register allocation hints, intrinsics Zig doesn't expose). The hand-optimized .ll is a shipping artifact, compiled via the build system.
2. Rewrite the Zig -- when studying the IR reveals that a Zig-level change (readInt, @Vector, slicing patterns) produces the same improved codegen. Simpler to maintain.

<when_to_use>

• A hot path has been identified and algorithmic improvements are exhausted
• You suspect the compiler is generating suboptimal code (redundant bounds checks, missed SIMD, poor branch layout)
• User says "LLVM optimization", "emit LLVM", "hand-optimize the LLVM"
• After microbenchmarks show a function is slower than expected given its algorithmic complexity </when_to_use>

<when_not_to_use>

• Before profiling -- don't optimize what isn't hot
• When algorithmic improvements are still available (fix O(n^2) before tweaking codegen)
• For code that runs infrequently (startup, config parsing, error paths) </when_not_to_use>

The Workflow

digraph llvm_opt {
  "Identify hot paths" -> "Baseline benchmarks";
  "Baseline benchmarks" -> "Emit LLVM IR for hot functions";
  "Emit LLVM IR for hot functions" -> "Hand-optimize the .ll code";
  "Hand-optimize the .ll code" -> "Expressible in Zig?";
  "Expressible in Zig?" -> "Rewrite Zig source" [label="yes, trivially"];
  "Expressible in Zig?" -> "Keep .ll file, wire into build" [label="no"];
  "Rewrite Zig source" -> "Benchmark again";
  "Keep .ll file, wire into build" -> "Benchmark again";
  "Benchmark again" -> "Regression?" [label="compare"];
  "Regression?" -> "Ship it" [label="faster"];
  "Regression?" -> "Revert or try differently" [label="slower"];
  "Regression?" -> "Check other arch" [label="mixed"];
  "Check other arch" -> "Surgical selection" -> "Final benchmark";
}

Step 1: Identify Hot Paths

Use static analysis to find the innermost loops -- functions called once per byte, per block, or per item in the main processing pipeline.

Typical hot paths by domain:

• Compression: match finder (BT4/HC), entropy coder, CRC/hash computation
• Validation: per-byte/per-block parsers, checksum loops
• Search/indexing: scoring functions, substring matching, inner ranking loops
• Archival: container expansion/contraction per-block, stream copy

Step 2: Baseline Benchmarks

# End-to-end (hyperfine)
hyperfine --warmup 3 './zig-out/bin/tool input_file'

# Microbenchmarks (under the performance-profiling skill's shared contract)
zig build microbench

Step 3: Emit LLVM IR

# Emit IR for the whole project
zig build -Doptimize=ReleaseFast -Demit-llvm-ir

# Or for a specific file
zig build-obj -OReleaseFast --emit llvm-ir src/hot_module.zig

This produces .ll files containing the LLVM IR. Open and study the functions you identified in Step 1.

Step 4: Study IR for Missed Optimizations

Common things to look for in the .ll output:

Step 5: Hand-Optimize and Integrate

Two paths depending on whether the optimization is expressible in Zig:

Path A: Keep the hand-optimized .ll file (default)

When the optimization involves custom SIMD scheduling, register hints, intrinsic sequences, or anything Zig can't express -- keep the .ll as a shipping artifact.

Directory structure:

src/
  lib.zig              # Zig core (hot function removed or stubbed)
  llvm/
    match_finder.ll    # Hand-optimized LLVM IR for aarch64
    match_finder_x86.ll  # Hand-optimized LLVM IR for x86_64 (if different)

Compiling .ll into the build:

For C/clang projects, compile with -flto so the hand-optimized IR participates in link-time optimization:

# Compile .ll to .o with LTO (enables cross-module inlining)
clang -O2 -flto -c chudnovsky.ll -o chudnovsky.o
# Link alongside C object files
clang -O2 -flto main.o chudnovsky.o sieve.o -lgmp -o binary

For Zig projects, use addObjectFile or a system command build step:

// For arch-specific variants: if (target.result.cpu.arch == .aarch64) { // use aarch64 .ll } else { // use x86_64 .ll or fall back to Zig implementation }

</template>

The original function (Zig or C) should be kept as a fallback (gated by architecture or a build option) so the code compiles on platforms without a hand-optimized `.ll`.

<example>
**Real-world example:** `llvm-pi/chudnovsky.ll` -- hand-optimized binary splitting for Chudnovsky pi computation. 8 optimizations the C compiler cannot do: direct GMP limb manipulation (0 GMP calls per base case, down from 14), branchless negation via `_mp_size` field flip, `@llvm.cttz.i64` replacing branch loops, cross-product precomputation as native i64/i128, addmul fusion (2 GMP calls per merge, down from 3), and a diff==2 special case eliminating ~352K recursive call pairs at 10M digits. Compiled with `clang -O2 -flto -c` and linked with LTO alongside C modules.
</example>

#### Path B: Rewrite the Zig (when optimization is trivially expressible)

When studying the IR reveals a simple Zig-level change produces equivalent codegen:

<example>
```zig
// BEFORE: multiple byte loads, compiler might not combine
const val = @as(u32, buf[i]) | (@as(u32, buf[i+1]) << 8) |
            (@as(u32, buf[i+2]) << 16) | (@as(u32, buf[i+3]) << 24);

// AFTER: single instruction on most architectures
const val = std.mem.readInt(u32, buf[i..][0..4], .little);

// AFTER: SIMD batch compare (16 bytes at a time) const V = @Vector(16, u8); const chunk_a: V = buf_a[i..][0..16].; const chunk_b: V = buf_b[i..][0..16].; const mask: V = @splat(0x20); const eq = (chunk_a | mask) == (chunk_b | mask);

</example>

#### Hardware intrinsics via C source files

For intrinsics not accessible from Zig or LLVM IR (e.g., ARM ACLE CRC), use a C source file:

```zig
// build.zig
if (target.result.cpu.arch == .aarch64) {
    lib_mod.addCSourceFile(.{
        .file = b.path("src/lib/crc32_arm.c"),
        .flags = &.{ "-march=armv8-a+crc", "-O3" },
    });
}

Step 6: Verify the Codegen

For Path B (Zig rewrite): re-emit IR and confirm the function now generates the expected improved code.

For Path A (.ll file): compile and verify the object links correctly and passes tests.

Step 7: Benchmark Again

Run the exact same benchmarks from Step 2. Compare:

Cross-Architecture Discipline

Proven Results (from this codebase)

The llvm-pi case is the canonical example of Path A: the optimizations (direct limb manipulation, branchless negation, i128 arithmetic, @llvm.cttz) cannot be expressed in C -- the .ll file IS the shipping artifact.

The z7z case demonstrates why benchmarking is non-negotiable: the "optimizations" collectively made things worse until the harmful ones were surgically reverted.

Common Optimizations Checklist

When studying LLVM IR for a Zig hot path, check these in order:

• Combined loads: Replace byte-at-a-time reads with readInt(u32/u64, ...)
• Bounds check elimination: Restructure slicing to help LLVM prove safety
• SIMD vectorization: Use explicit @Vector for bulk byte/int operations
• Hardware intrinsics: Use @ctz, @clz, @popCount, @byteSwap, or C files for ACLE/SSE intrinsics
• Comptime lookup tables: Replace runtime computation with comptime-generated tables (watch @setEvalBranchQuota for large tables)
• Branch hints: @branchHint(.unlikely) on error paths (benchmark on target arch)
• Loop hoisting: Move invariant struct field reads out of inner loop (benchmark on target arch)
• Allocation elimination: Arena/stack allocation instead of per-iteration heap alloc

Common Mistakes