Skip to content

37. Inside the LLVM Stage: Reading the IR, and Why a Loop Does or Does Not Vectorize

Mountain goats in space helmets on Titania, a moon of Uranus

What you will understand: what happens to a Mountain Goat program after MLIR hands it to LLVM. Every chapter since Chapter 5 has ended with "lowered to LLVM IR, then clang makes the executable", and none has opened that stage. This chapter opens it. You will read the LLVM IR that mgc writes; watch LLVM's optimizer, opt, change a matrix product pass by pass; ask the loop vectorizer why it did or did not vectorize a loop (Chapter 23 counted vector instructions and Chapter 24 got a 3× to 11× speedup from a loop-order change, and neither said why); read the assembly of the two inner loops; and ask llvm-mca, a model of the CPU's pipeline, what it predicts. The chapter ends with two corrections to its own first experiments and one place where the model predicts a speedup that the measurement refuses to show.

What you need to know first: Chapter 5 (the lowering to the LLVM dialect and IR), Chapter 23 (the benchmark, -O3 -march=native) and Chapter 24 (the ikj loop order). No new compiler operation is needed and the compiler is unchanged: the programs run on Chapter 32's mgc, and the tools are LLVM 18's own: opt-18, clang-18, llvm-mca-18.

Compile and run

cd docs/part32/code && ./build.sh                 # once: the newest compiler (this chapter adds nothing to it)
cd ../../part37/code
./stages.sh > stages_out.txt                      # the files mgc writes on the way to machine code, for the smallest program and for the matrix product
./walk.sh > walk_out.txt                          # opt, pass by pass, on the matrix product's IR
./remarks.sh > remarks_out.txt                    # the loop vectorizer's decisions and reasons
./ops_table.sh > ops_table_out.txt                # which of Mountain Goat's operations vectorize (instruction counts)
./mca.py > mca_out.txt; ./mca.py --loops > loops_out.txt   # llvm-mca's prediction, and the assembly of the two inner loops
./cpu_dependence.py > cpu_dependence_out.txt      # the same IR compiled for four different CPUs (compile only)
./variants.sh > variants_out.txt; ./summarize_variants.py > variants_summary.txt   # the measurement: 3 passes of the Chapter 24 benchmark (about 2 minutes)
./check_llvm.py > check_llvm_out.txt              # every claim on this page, tested for the pinned CPU (about 3 seconds)
./claims_mutation.py > claims_mutation_out.txt    # six WRONG inputs the checker must catch (about 20 seconds)
cd ../../part15/code && ./run_lit.sh              # the whole test suite
Every listing and output on this page comes from these commands.

Why this page shows FAIL lines and 'not vectorized' remarks, and why that is good

"Loop not vectorized" is not an error: it is LLVM explaining a decision, and the explanation is the subject of the chapter. The claims_mutation.py output is a negative control: deliberately wrong inputs fed to the checker, where "caught" is the wanted result and "NOT CAUGHT" would be a gap.

Where LLVM sits in mgc

mgc is a chain of real tools (its header says so). With MGC_KEEP=dir it keeps the file each stage writes. For the smallest program (examples/01_add2x2.mg, a + b on 2 × 2 matrices) and for the 64 × 64 matrix product (examples/02_matmul64.mg), the stages and their sizes are:

== add2: lines per stage
   01_add2x2.mlir            4 lines
   01_add2x2.affine.mlir    15 lines
   01_add2x2.llvm.mlir      77 lines
   01_add2x2.ll             73 lines
== mm_ijk: lines per stage
   02_matmul64.mlir          4 lines
   02_matmul64.affine.mlir   29 lines
   02_matmul64.llvm.mlir   113 lines
   02_matmul64.ll          118 lines
== mm_ikj: lines per stage
   02_matmul64.mlir          4 lines
   02_matmul64.affine.mlir   29 lines
   02_matmul64.llvm.mlir   113 lines
   02_matmul64.ll          118 lines

mgfront.py writes the .mlir (the mg dialect), mg-opt --convert-mg-to-affine writes the .affine.mlir (loops, loads, stores), mg-opt with the lowering passes writes the .llvm.mlir (the LLVM dialect: MLIR's own copy of LLVM's instructions), and mlir-translate writes the .ll, which is LLVM IR: the text format LLVM's tools read. From here on nothing is MLIR: opt optimizes the .ll, and clang turns it into assembly and an executable. (The two loop orders have the same line counts: only the order of the three loops inside differs.)

Reading the IR

Here is the whole LLVM IR of the 2 × 2 add. Take it in four parts:

---- add2/01_add2x2.ll (the whole file, the LLVM IR of the small program)
; ModuleID = 'LLVMDialectModule'
source_filename = "LLVMDialectModule"

declare ptr @malloc(i64)

define { ptr, ptr, i64, [2 x i64], [2 x i64] } @add2(ptr %0, ptr %1, i64 %2, i64 %3, i64 %4, i64 %5, i64 %6, ptr %7, ptr %8, i64 %9, i64 %10, i64 %11, i64 %12, i64 %13) {
  %15 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } undef, ptr %0, 0
  %16 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %15, ptr %1, 1
  %17 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %16, i64 %2, 2
  %18 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %17, i64 %3, 3, 0
  %19 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %18, i64 %5, 4, 0
  %20 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %19, i64 %4, 3, 1
  %21 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %20, i64 %6, 4, 1
  %22 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } undef, ptr %7, 0
  %23 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %22, ptr %8, 1
  %24 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %23, i64 %9, 2
  %25 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %24, i64 %10, 3, 0
  %26 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %25, i64 %12, 4, 0
  %27 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %26, i64 %11, 3, 1
  %28 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %27, i64 %13, 4, 1
  %29 = call ptr @malloc(i64 ptrtoint (ptr getelementptr (double, ptr null, i32 4) to i64))
  %30 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } undef, ptr %29, 0
  %31 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %30, ptr %29, 1
  %32 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %31, i64 0, 2
  %33 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %32, i64 2, 3, 0
  %34 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %33, i64 2, 3, 1
  %35 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %34, i64 2, 4, 0
  %36 = insertvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %35, i64 1, 4, 1
  br label %37

37:                                               ; preds = %60, %14
  %38 = phi i64 [ %61, %60 ], [ 0, %14 ]
  %39 = icmp slt i64 %38, 2
  br i1 %39, label %40, label %62

40:                                               ; preds = %37
  br label %41

41:                                               ; preds = %44, %40
  %42 = phi i64 [ %59, %44 ], [ 0, %40 ]
  %43 = icmp slt i64 %42, 2
  br i1 %43, label %44, label %60

44:                                               ; preds = %41
  %45 = extractvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %21, 1
  %46 = mul i64 %38, 2
  %47 = add i64 %46, %42
  %48 = getelementptr double, ptr %45, i64 %47
  %49 = load double, ptr %48, align 8
  %50 = extractvalue { ptr, ptr, i64, [2 x i64], [2 x i64] } %28, 1
  %51 = mul i64 %38, 2
  %52 = add i64 %51, %42
  %53 = getelementptr double, ptr %50, i64 %52
  %54 = load double, ptr %53, align 8
  %55 = fadd double %49, %54
  %56 = mul i64 %38, 2
  %57 = add i64 %56, %42
  %58 = getelementptr double, ptr %29, i64 %57
  store double %55, ptr %58, align 8
  %59 = add i64 %42, 1
  br label %41

60:                                               ; preds = %41
  %61 = add i64 %38, 1
  br label %37

62:                                               ; preds = %37
  ret { ptr, ptr, i64, [2 x i64], [2 x i64] } %36
}

!llvm.module.flags = !{!0}

!0 = !{i32 2, !"Debug Info Version", i32 3}
  1. The descriptors (the long run of insertvalue). Each matrix arrives as seven separate arguments (ptr %0, ptr %1, i64 %2, …: allocated pointer, aligned pointer, offset, two sizes, two strides, Chapter 1's memref calling convention), and the first 14 instructions pack them into two { ptr, ptr, i64, [2 x i64], [2 x i64] } values, the memref descriptors (seven more build the result's). Almost all of this is dead weight: only each argument's aligned pointer is read later (extractvalue … 1). It is the first thing the optimizer will delete.
  2. The allocation: call ptr @malloc(i64 ptrtoint (ptr getelementptr (double, ptr null, i32 4) to i64)), that is malloc(4 * sizeof(double)) for the 2 × 2 result (the getelementptr … null is the idiom for sizeof). The generated code never frees what it allocates.
  3. The loops (phi, icmp, br). LLVM IR is in static single assignment form: every name is assigned once. A loop counter that changes is therefore a phi: %38 = phi i64 [ %61, %60 ], [ 0, %14 ] means "if control came from block %60, take %61 (the incremented value), if from %14, take 0". The two nested loops are the two phis, icmp slt the bound test, br i1 the conditional branch.
  4. The body: mul/add compute the flat index i * 2 + j, getelementptr double, ptr %45, i64 %47 is the address of that element (LLVM's pointer arithmetic: it never reads memory), load double, fadd double %49, %54, store double. The fadd carries no flags: that detail matters twice below.

The 64 × 64 matrix product (02_matmul64.mg) has the same pieces plus a second loop nest for the zero fill and a three-deep nest whose body is load the running sum from the result, load a, load b, fmul, fadd, store the sum back (every iteration goes through memory).

What opt does, pass by pass

opt runs passes over the IR. walk.sh runs a growing list of the standard ones on the matrix product and counts what is left (instructions, basic blocks, and lines that mention a vector of doubles <N x double>). The target (-mtriple, -mcpu) must be given: without it opt does not know which vector instructions exist, and the vectorizer did nothing (the first version of this script forgot, and every row showed 0 vector lines).

== ijk order, 64 x 64 (opt-18, target x86-64, CPU sapphirerapids)
 77 instructions, 16 blocks,   0 lines with vector doubles   <- as emitted by mgc (no passes)
 57 instructions, 12 blocks,   0 lines with vector doubles   <- instcombine, simplifycfg
 56 instructions, 11 blocks,   0 lines with vector doubles   <- + loop-simplify, lcssa, loop-rotate
 57 instructions, 11 blocks,   0 lines with vector doubles   <- + licm (loop-invariant code motion)
 57 instructions, 11 blocks,   0 lines with vector doubles   <- + indvars
 69 instructions, 15 blocks,   1 lines with vector doubles   <- + loop-vectorize
 56 instructions, 10 blocks,   1 lines with vector doubles   <- + instcombine, simplifycfg again
180 instructions, 11 blocks,  32 lines with vector doubles   <- + loop-unroll
102 instructions,  8 blocks,   0 lines with vector doubles   <- the whole -O3 pipeline

== ikj order, 64 x 64 (opt-18, target x86-64, CPU sapphirerapids)
 77 instructions, 16 blocks,   0 lines with vector doubles   <- as emitted by mgc (no passes)
 57 instructions, 12 blocks,   0 lines with vector doubles   <- instcombine, simplifycfg
 56 instructions, 11 blocks,   0 lines with vector doubles   <- + loop-simplify, lcssa, loop-rotate
 56 instructions, 11 blocks,   0 lines with vector doubles   <- + licm (loop-invariant code motion)
 56 instructions, 11 blocks,   0 lines with vector doubles   <- + indvars
106 instructions, 20 blocks,   8 lines with vector doubles   <- + loop-vectorize
 85 instructions, 12 blocks,   8 lines with vector doubles   <- + instcombine, simplifycfg again
377 instructions, 15 blocks, 144 lines with vector doubles   <- + loop-unroll
169 instructions,  6 blocks,  98 lines with vector doubles   <- the whole -O3 pipeline
  • instcombine, simplifycfg: 77 → 57 instructions. This is the dead descriptor packing going away, and constants folded.
  • loop-rotate, licm, indvars: the loops are put in canonical form; the next table row shows no change in size, which is the point of canonical form: it is what the vectorizer needs.
  • loop-vectorize: the ikj order grows from 56 to 106 instructions and gains vector arithmetic (the vector body, the scalar remainder loop, and the run-time checks that guard them). The ijk order grows to 69 instructions with one line mentioning vector doubles. Which line? store <4 x double> zeroinitializer: the zero-fill loop was vectorized, and the product's own loop was not (the last lines of the second excerpt below print it).
  • loop-unroll: both orders unroll their inner loop (180 and 377 instructions).
  • the whole -O3 pipeline goes further than the list. The same file shows the ijk order's result:
== what the whole -O3 pipeline made of the ijk product's setup and inner loop (the lines that matter, from opt's own output)
9:  %calloc = tail call dereferenceable_or_null(32768) ptr @calloc(i64 1, i64 32768)
15:  %16 = getelementptr double, ptr %calloc, i64 %15
22:  %.promoted = load double, ptr %18, align 8
27:  %21 = phi double [ %.promoted, %.preheader ], [ %84, %19 ]
34:  %27 = fmul double %24, %26
35:  %28 = fadd double %21, %27
43:  %35 = fmul double %32, %34
44:  %36 = fadd double %28, %35
52:  %43 = fmul double %40, %42
53:  %44 = fadd double %36, %43
61:  %51 = fmul double %48, %50
62:  %52 = fadd double %44, %51
70:  %59 = fmul double %56, %58
71:  %60 = fadd double %52, %59
in all: 8 fadd, 8 fmul, 17 loads, 1 stores, 1 calloc, 0 malloc

== the one line with a vector of doubles that the ijk order has after loop-vectorize (before the loop-idiom pass that later turns the whole zero-fill loop into calloc)
  store <4 x double> zeroinitializer, ptr %21, align 8

The malloc and the zero-fill loop became one calloc (the loop-idiom pass recognizes "allocate, then fill with zeros"). The running sum is no longer loaded and stored every iteration: %.promoted = load double before the loop, phi double [ %.promoted, … ] inside it, and a single store (17 loads and 1 store in the whole function): LICM's scalar promotion moved the accumulator into a register. The inner loop is unrolled eight times into a chain: %28 = fadd double %21, %27, then %36 = fadd double %28, %35, each addition waiting for the previous one. Remember this chain: it is the next section's subject, and the backend's.

Why the ijk loop is not vectorized, and what the permission costs

remarks.sh asks clang's loop vectorizer for its decisions (-Rpass, -Rpass-missed, -Rpass-analysis):

== ijk, clang -O3 
loop not vectorized: cannot prove it is safe to reorder floating-point operations; allow reordering by specifying '#pragma clang loop vectorize(enable)' before the loop or by providing the compiler option '-ffast-math'.
loop not vectorized
== ijk, clang -O3 -march=sapphirerapids
loop not vectorized: cannot prove it is safe to reorder floating-point operations; allow reordering by specifying '#pragma clang loop vectorize(enable)' before the loop or by providing the compiler option '-ffast-math'.
loop not vectorized
== ikj, clang -O3 
the cost-model indicates that interleaving is not beneficial
vectorized loop (vectorization width: 2, interleaved count: 1)
== ikj, clang -O3 -march=sapphirerapids
the cost-model indicates that interleaving is not beneficial
vectorized loop (vectorization width: 4, interleaved count: 1)

== (2) ijk with the reassoc flag on every fadd in the IR (sed 's/fadd double/fadd reassoc double/'), clang -O3 -march=sapphirerapids
fadd instructions changed: 1
the cost-model indicates that interleaving is not beneficial
vectorized loop (vectorization width: 4, interleaved count: 1)

== (3) ijk with clang's -ffast-math option on the unchanged .ll
loop not vectorized: cannot prove it is safe to reorder floating-point operations; allow reordering by specifying '#pragma clang loop vectorize(enable)' before the loop or by providing the compiler option '-ffast-math'.
loop not vectorized
assembly with and without -ffast-math: byte for byte identical

== the same sizes unknown until run time (examples/03_matmul_dynamic.mg), ijk and ikj, clang -O3 -march=sapphirerapids
-- ijk
loop not vectorized: cannot prove it is safe to reorder floating-point operations; allow reordering by specifying '#pragma clang loop vectorize(enable)' before the loop or by providing the compiler option '-ffast-math'.
loop not vectorized
-- ikj
vectorized loop (vectorization width: 4, interleaved count: 4)

For the default ijk order the vectorizer says, with and without -march=sapphirerapids (the CPU of the machine these pages were produced on; the scripts pin it, see "Is this specific to one CPU?" below):

loop not vectorized: cannot prove it is safe to reorder floating-point operations

For ikj it says vectorized loop (width 2 on plain x86-64, which has 128-bit SSE2 registers; width 4 with -march=sapphirerapids, which allows 256-bit AVX registers).

Why. The ijk inner loop is a reduction: sum = sum + a[i][k] * b[k][j]. A vectorized version adds four partial sums and combines them at the end, which adds the numbers in a different order, and floating-point addition is not associative: (a + b) + c can differ from a + (b + c). LLVM must produce exactly what the program says unless it is told reordering is allowed. The ikj loop has no reduction: each iteration c[i][j] += x * b[k][j] updates a different element, so the iterations are independent and vectorizing them reorders nothing.

The experiment: give the permission, and see what it buys. Fast-math permission is a flag on each instruction in the IR: fadd reassoc double … means "this addition may be reassociated". Add it to every fadd of the ijk IR (sed 's/fadd double/fadd reassoc double/'): the vectorizer now says vectorized loop (vectorization width: 4 …). The ijk loop vectorizes. Is it faster? variants.sh builds Chapter 24's benchmark (dynamic sizes) four ways and times each at N = 256 and 512 (pinned to one core, three passes, each result checked against a reference; the table is summarize_variants.py's):

variant           N  median GFLOP/s in each of the three passes    slowest..fastest
ijk             256    2.17    2.01    2.52     2.01..  2.52
ijk             512    0.63    0.74    0.64     0.63..  0.74
ijk_reassoc     256    1.94    2.43    2.47     1.94..  2.47
ijk_reassoc     512    0.63    0.62    0.66     0.62..  0.66
ikj             256   11.73    9.23    9.94     9.23.. 11.73
ikj             512    7.16    7.34    7.36     7.16..  7.36
ikj_reassoc     256   13.63    9.80    9.98     9.80.. 13.63
ikj_reassoc     512    8.01    8.34    6.84     6.84..  8.34
ikj_contract    256   10.07   11.98   11.15    10.07.. 11.98
ikj_contract    512    9.38    8.24    9.55     8.24..  9.55

mean of the three passes, relative to ijk at the same N:
  ijk            N=256    2.23 GFLOP/s =  1.00x ijk
  ijk            N=512    0.67 GFLOP/s =  1.00x ijk
  ijk_reassoc    N=256    2.28 GFLOP/s =  1.02x ijk
  ijk_reassoc    N=512    0.64 GFLOP/s =  0.95x ijk
  ikj            N=256   10.30 GFLOP/s =  4.61x ijk
  ikj            N=512    7.29 GFLOP/s = 10.88x ijk
  ikj_reassoc    N=256   11.14 GFLOP/s =  4.99x ijk
  ikj_reassoc    N=512    7.73 GFLOP/s = 11.54x ijk
  ikj_contract   N=256   11.07 GFLOP/s =  4.96x ijk
  ikj_contract   N=512    9.06 GFLOP/s = 13.52x ijk
  • Vectorizing the ijk loop does not make it faster. Mean over three passes: 2.28 against 2.23 GFLOP/s at N = 256 and 0.64 against 0.67 at N = 512, with each pair's three passes overlapping. The vectorizer's permission was not what kept ijk slow.
  • The loop order is. ikj is 4.6× faster than ijk at N = 256 and 10.9× at N = 512, with or without the permission (which ikj does not need).
  • Why the vectorized ijk is no faster. b[k][j] walks down a column: consecutive k are a whole row apart in memory, so the vector must be gathered one element at a time (the assembly of the vectorized ijk has 16 vgather instructions; the ikj assembly has none: check_llvm_out.txt). Gathers move the same strided data a scalar loop would, so the reduction's permission buys no bandwidth. This is an inference from the instruction counts and the timings; no hardware counters were read (cache misses were not measured), so "memory-bound" is the explanation that fits, not a measured fact.

A correction. The first version of this experiment used clang's -ffast-math option, the way a C programmer would. It changed nothing: remarks.sh shows the same "cannot prove it is safe" remark and the assembly with and without the flag is byte for byte identical (cmp says so). The reason is that -ffast-math tells the front end which flags to put on the instructions it generates from C or C++ source; a .ll file already has its instructions, with no flags, and clang does not rewrite them. The permission has to be in the IR, which is where Mountain Goat would have to put it if it ever offered it (its lowering emits plain arith.addf; MLIR can attach fastmath<reassoc> to it, which was not done here).

Reading the assembly

Here are the two inner loops from clang -O3 -march=sapphirerapids (mca.py --loops), the ijk order's first, then ikj's:

## ijk (the default order): the innermost loop with the most multiply-adds (34 instructions)
    vmovsd  -56(%r8,%r13,8), %xmm1
    vmovsd  -48(%r8,%r13,8), %xmm2
    vmulsd  (%rcx), %xmm1, %xmm1
    vaddsd  %xmm1, %xmm0, %xmm0
    leaq    (%rcx,%rax,8), %r11
    vmulsd  (%rcx,%rax,8), %xmm2, %xmm1
    vmovsd  -40(%r8,%r13,8), %xmm2
    vmulsd  (%r10,%r11), %xmm2, %xmm2
    vaddsd  %xmm1, %xmm0, %xmm0
    addq    %r10, %r11
    vaddsd  %xmm2, %xmm0, %xmm0
    vmovsd  -32(%r8,%r13,8), %xmm1
    vmulsd  (%r10,%r11), %xmm1, %xmm1
    addq    %r10, %r11
    vaddsd  %xmm1, %xmm0, %xmm0
    vmovsd  -24(%r8,%r13,8), %xmm1
    vmulsd  (%r10,%r11), %xmm1, %xmm1
    addq    %r10, %r11
    vaddsd  %xmm1, %xmm0, %xmm0
    vmovsd  -16(%r8,%r13,8), %xmm1
    vmulsd  (%r10,%r11), %xmm1, %xmm1
    addq    %r10, %r11
    vaddsd  %xmm1, %xmm0, %xmm0
    vmovsd  -8(%r8,%r13,8), %xmm1
    vmulsd  (%r10,%r11), %xmm1, %xmm1
    addq    %r10, %r11
    vaddsd  %xmm1, %xmm0, %xmm0
    vmovsd  (%r8,%r13,8), %xmm1
    vmulsd  (%r10,%r11), %xmm1, %xmm1
    vaddsd  %xmm1, %xmm0, %xmm0
    addq    $8, %r13
    addq    %r9, %rcx
    cmpq    %r13, %rdi
    jne .LBB0_9

## ikj: the innermost loop with the most multiply-adds (15 instructions)
    vmulpd  -96(%r9,%r12,8), %ymm1, %ymm2
    vmulpd  -64(%r9,%r12,8), %ymm1, %ymm3
    vmulpd  -32(%r9,%r12,8), %ymm1, %ymm4
    vmulpd  (%r9,%r12,8), %ymm1, %ymm5
    vaddpd  -96(%rdi,%r12,8), %ymm2, %ymm2
    vaddpd  -64(%rdi,%r12,8), %ymm3, %ymm3
    vaddpd  -32(%rdi,%r12,8), %ymm4, %ymm4
    vaddpd  (%rdi,%r12,8), %ymm5, %ymm5
    vmovupd %ymm2, -96(%rdi,%r12,8)
    vmovupd %ymm3, -64(%rdi,%r12,8)
    vmovupd %ymm4, -32(%rdi,%r12,8)
    vmovupd %ymm5, (%rdi,%r12,8)
    addq    $16, %r12
    cmpq    %r12, %rsi
    jne .LBB0_11
  • ijk (34 instructions, 8 multiply-adds): eight vmulsd/vaddsd pairs (sd = scalar double). Every vaddsd reads and writes %xmm0: the additions form a dependency chain, each waiting for the last, exactly the chain seen in the IR. The loads of b step by %r10 (the row length) between multiplies: the column walk. There are no fused multiply-adds: the vmulsd and vaddsd are separate.
  • ikj (15 instructions, 16 multiply-adds): four vmulpd and four vaddpd on %ymm registers (pd = packed double, ymm = 256 bits = 4 doubles), so 16 multiply-adds per iteration, with memory operands folded in and four stores. The four vectors are independent: no chain. (This CPU has 512-bit registers; clang 18 chose 256-bit ones. Why was not investigated.)
  • Neither uses vfmadd. A fused multiply-add computes a * b + c in one instruction with one rounding, which gives a different result from a multiply followed by an add, so LLVM needs permission: the contract flag on the fmul and the fadd. C compilers grant it by default in C (-ffp-contract=on), which is why you rarely see this; our IR has no flags. Adding contract (same sed trick) turns the ikj loop's multiply and add into vfmadd instructions (16 in the static 64 × 64 version, check_llvm_out.txt), and variants.sh measures them: ikj with contract is 7.3 → 9.1 GFLOP/s at N = 512 (all three of its passes, 8.24 to 9.55, are above all three of plain ikj's, 7.16 to 7.36) and 10.3 → 11.1 at N = 256 (overlapping passes: no clear gain there). That is about +24% at N = 512 on this machine.

What llvm-mca predicts, and where the prediction fails

llvm-mca takes a block of assembly and simulates how the CPU's pipeline would execute it, many times, and reports cycles. It models the core (instruction latencies, issue ports, dispatch width). It assumes every load hits the L1 cache: it does not model the memory system. mca.py runs each variant's hot loop through it (-mcpu=sapphirerapids) and divides by the multiply-adds per iteration:

llvm-mca-18, -mcpu=sapphirerapids, 100 iterations of the loop body; dynamic sizes (examples/03_matmul_dynamic.mg), clang -O3 -march=sapphirerapids
variant                                    instrs mul-adds cycles/iter  cycles per mul-add
ijk (the default order)                        34        8        24.1                3.02
ijk, reassoc on every fadd                     15       16         3.2                0.20
ikj                                            15       16         4.6                0.29
ikj, contract on every fmul and fadd           15       16         3.9                0.25
  • The ijk loop costs 3.02 cycles per multiply-add: the chain of eight dependent additions is the limit. The ikj loop costs 0.29: ten times less.
  • reassoc is predicted to be a big win for ijk: 0.20 cycles per multiply-add, 15 times better. The model sees the chain broken into independent vector adds. The measurement did not show it (previous section: 0.64 against 0.67 GFLOP/s). The model and the measurement disagree, and the disagreement is informative: llvm-mca is blind to the strided column walk, which is the bottleneck. This is the page's cleanest example of what a core model can and cannot say: it correctly ranks ikj above ijk (predicted 10.4×, measured 4.6× at N = 256 and 10.9× at N = 512), and it incorrectly predicts a large gain from vectorizing ijk.
  • contract is predicted to help ikj a little (0.29 → 0.25 cycles per multiply-add, 14%): the same direction as the measurement, at a smaller size than the +24% measured at N = 512.

(One repair along the way: the first version of mca.py picked a loop that contained the inner loops, so it counted too many multiplies; and weighed instructions, not lanes, so it preferred the unrolled scalar loop to the vectorized one. It now takes innermost loops only, ranked by multiply-adds per iteration.)

Which Mountain Goat operations vectorize?

ops_table.sh compiles each one-operation program in ops/ on 64 × 64 matrices with clang -O3 -march=sapphirerapids and counts, in the assembly, packed arithmetic instructions (vaddpd, vmulpd, vmaxpd, vsqrtpd, vcmppd, …: four doubles at once), scalar ones (vaddsd, …), gathers, and library calls. It counts instructions; it says whether the compiler vectorized, not whether that was faster.

operation   packed  scalar  gather  library calls
add             16       0       0  
hadamard        16       0       0  
scale           16       0       0  
relu            32       0       0  
sqrt            16       0       0  
ge              16       0       0  
bcast_add       16       0       0  memcpy 
transpose        0       0      16  
col_sum         16       0       0  
row_sum         64       0      64  
row_mean        80       0      64  
row_max        128       0      64  
exp              0       0       0  exp 
log              0       0       0  log
  • The element-wise operations (add, hadamard (a * b), scale, relu, sqrt, ge, and the broadcast add) are all vectorized with no scalar arithmetic left. (relu's count is 32 against 16 for the others; its instruction mix was not examined. bcast_add also calls memcpy.)
  • exp and log are not vectorized: no packed arithmetic at all, and the assembly calls the C library's exp and log once per element (clang has no vector version of them to call). Softmax (Chapter 29), and so every attention head in Chapters 30 to 36, uses exp.
  • transpose has no arithmetic: it is 16 gathers and moves.
  • The row reductions (row_sum, row_mean, row_max) have no scalar adds and use 64 gathers each, which is the opposite of what the matrix product's reduction did. The reason is not established here: the assembly (64 gathers feeding 64 packed adds, no scalar adds) is consistent with LLVM keeping each row's addition order exactly as written and vectorizing across rows (four rows' running sums in one register, gathered from four rows), which reorders nothing, but the transformation was not identified (the IR was not read for it). The same permission question does not arise when each lane is a different row. col_sum adds whole rows, so it vectorizes without gathers.

Is this specific to one CPU? Yes, in the details

The first CI run of this chapter's test failed, on a different CPU from the one used here, while every other test passed. The compiler's choices depend on the target CPU, so the scripts now pin it (sapphirerapids; CPU=native ./walk.sh overrides) and the chapter's claims are claims about that target. cpu_dependence.py compiles the same IR for four CPUs (compilation only: nothing is run) and shows how much changes:

same IR, compiled for four x86-64 CPUs (compile only; clang -O3 -march=CPU, opt -mcpu=CPU, llvm-mca -mcpu=CPU)
                                              sapphirerapids          skylake-avx512          haswell                 znver3                  
ijk                                           not vectorized          not vectorized          not vectorized          not vectorized          
ikj                                           vectorized (width 4)    vectorized (width 4)    vectorized (width 4)    vectorized (width 4)    
ijk + reassoc                                 vectorized (width 4)    vectorized (width 4)    vectorized (width 4)    vectorized (width 4)    
vgather in ijk + reassoc                      16                      16                      0                       0                       
vgather in row_sum                            64                      64                      0                       0                       
vector fmul left in ijk after -O3             0                       0                       0                       0                       
vfmadd in ikj + contract                      16                      16                      16                      64                      
mca cycles/mul-add: ijk, ijk+reassoc, ikj     3.02 , 0.20 , 0.29      4.02 , 0.26 , 0.30      3.02 , 0.32 , 0.45      3.02 , 0.26 , 0.38
  • What does not depend on the CPU, in these four: ijk is not vectorized, ikj is (width 4), and ijk with the reassoc flag is (width 4). The reduction story holds everywhere tried.
  • What does: the gathers. On sapphirerapids and skylake-avx512 the vectorized ijk loop and row_sum use vgather instructions (16 and 64). On haswell and znver3 there are none, although both CPUs have AVX2 and the vectorizer still vectorizes: it fills the vectors with scalar loads instead (LLVM treats gathers as slow on those CPUs; the exact mechanism in the assembly was not read for them). So the chapter's inference "the vectorized ijk is no faster because it gathers" was tested only on the Intel targets and the measurement was made on an Intel machine; for the other two CPUs only the instruction mix, not a timing, is known.
  • The fused multiply-add count differs (16, 16, 16 and 64 vfmadd for the same loop), and so do llvm-mca's cycles per multiply-add (ijk 3.0 to 4.0, ijk with reassoc 0.20 to 0.32, ikj 0.29 to 0.45): the ranking is the same on all four (ikj and reassoc'd ijk far below ijk), the numbers are not.

Tests

Two new lit files in test/llvm37/ (the suite is now 146 tests; no verifiers or ir test because no compiler operation was added):

Test What it checks
examples the three programs compile to the expected mg operation; every one of the fourteen one-operation programs in ops/ compiles
claims check_llvm.py, below (about 3 seconds)

check_llvm.py runs the tools and tests the claims, in five groups: (1) the IR's shape (one fadd, one malloc, two loop counters for the add; a fmul and a fadd in the product); (2) opt: after loop-vectorize ikj has a vector fmul and ijk has only the vector store of zeros; the whole -O3 pipeline leaves one calloc, no malloc, a promoted accumulator and no vector multiply; (3) the remarks: ijk's "cannot prove it is safe", ikj's "vectorized loop", ijk with reassoc vectorized and gathering (16 vgathers, ikj none), and -ffast-math leaving the assembly identical; (4) the operations: add packed and not scalar, exp a library call and not packed, row_sum gathers, transpose no arithmetic; (5) the backend: ikj has no vfmadd and has them with contract, and llvm-mca puts ijk above five times ikj per multiply-add and reassoc below a third of ijk.

-- 1. reading the IR
  ok   the 2x2 add: one fadd, one malloc, two loop counters (phi i64)
  ok   the 64x64 product (ijk): a fmul and a fadd, five loop counters (two for the zero fill, three for the product)
-- 2. the passes (opt)
  ok   after loop-vectorize the ikj order has a vector fmul
  ok   after loop-vectorize the ijk order has no vector fmul, only the vector store of zeros
  ok   the whole -O3 pipeline turns ijk's malloc and zero-fill loop into one calloc
  ok   the accumulator lives in a register (phi double, promoted from memory) and no multiply is a vector one
-- 3. the vectorizer's reasons (clang remarks)
  ok   ijk: not vectorized, 'cannot prove it is safe to reorder floating-point operations'
  ok   ikj: 'vectorized loop'
  ok   ijk with the reassoc flag on its fadd: 'vectorized loop'
  ok   the vectorized ijk gathers the column of b with vgather instructions (16); ikj needs none (0)
  ok   clang's -ffast-math on the unchanged .ll leaves the assembly byte for byte identical
-- 4. the operations (packed = vector arithmetic, scalar = one double at a time)
  ok   add: packed arithmetic (16), no scalar arithmetic (0)
  ok   exp: no packed arithmetic, a library call to ['exp']
  ok   row_sum: packed arithmetic (64) fed by gathers (64)
  ok   transpose: no arithmetic at all (0 packed), only moves
-- 5. the backend
  ok   ikj: no fused multiply-add (0); with the contract flag: 16
  ok   llvm-mca: ijk 3.02 cycles per multiply-add against ikj 0.29 (more than 5x)
  ok   llvm-mca: ijk with reassoc 0.2 against ijk 3.02 (less than a third)
all checks pass

Are the checks good enough? Feed it six wrong inputs.

claims_mutation.py changes one input at a time (the environment variables CHK_* of the checker) and expects the checker to fail:

NOTE: this script deliberately breaks inputs. 'caught' lines are EXPECTED: they show each check can fail.
baseline (nothing broken): checker passes (expected)
the 'ijk' program is built in ikj order: caught by 4 failing check(s):
      after loop-vectorize the ijk order has no vector fmul, only the vector store of zeros
      the accumulator lives in a register (phi double, promoted from memory) and no multiply is a vector one
      ijk: not vectorized, 'cannot prove it is safe to reorder floating-point operations'
      the vectorized ijk gathers the column of b with vgather instructions (0); ikj needs none (0)
the reassoc flag is not applied (the edit changes nothing): caught by 2 failing check(s):
      ijk with the reassoc flag on its fadd: 'vectorized loop'
      the vectorized ijk gathers the column of b with vgather instructions (0); ikj needs none (0)
the second assembly is built with -O1 in place of -ffast-math (a flag that does matter): caught by 1 failing check(s):
      clang's -O1 on the unchanged .ll leaves the assembly byte for byte identical
no -march=native (plain x86-64: SSE2 instructions, not the v-prefixed AVX ones the checks count): caught by 5 failing check(s):
      ijk with the reassoc flag on its fadd: 'vectorized loop'
      the vectorized ijk gathers the column of b with vgather instructions (0); ikj needs none (0)
      add: packed arithmetic (0), no scalar arithmetic (0)
      row_sum: packed arithmetic (0) fed by gathers (0)
      ikj: no fused multiply-add (0); with the contract flag: 0
the contract flag is replaced by nsz (a flag that does not allow fusing): caught by 1 failing check(s):
      ikj: no fused multiply-add (0); with the contract flag: 0
opt is run without a target (no -mtriple, no -mcpu): caught by 2 failing check(s):
      after loop-vectorize the ikj order has a vector fmul
      after loop-vectorize the ijk order has no vector fmul, only the vector store of zeros

All six are caught, each by the checks that should depend on the input that was broken: the ijk program built in the other order fails the three ijk claims; leaving out reassoc fails the "vectorized" claim and the gather claim; replacing -ffast-math with -O1 (a flag that does change the assembly) fails the byte-for-byte claim; nsz in place of contract fails the fused-multiply-add claim; opt without a target fails both vectorization claims. One result was a surprise and is worth reading: removing AVX (-mno-avx) fails five checks, including "ijk with reassoc is vectorized": with only SSE2 the vectorizer declines the strided reduction loop that it vectorizes with AVX (the reason was not investigated; the cost model or the missing gather instructions are the candidates). The practical lesson is that these claims describe the sapphirerapids target (the checks pin sapphirerapids), and would need different expected values for other targets, as the CPU section shows.

The full suite:

-- Testing: 146 tests, 4 workers --
PASS: IR Forge / Mountain Goat :: lm35/against-reference.mlir (1 of 146)
PASS: IR Forge / Mountain Goat :: lm36/examples.mlir (2 of 146)
PASS: IR Forge / Mountain Goat :: attention33/against-reference.mlir (3 of 146)
PASS: IR Forge / Mountain Goat :: lm36/against-reference.mlir (4 of 146)
PASS: IR Forge / Mountain Goat :: generalize32/against-reference.mlir (5 of 146)
PASS: IR Forge / Mountain Goat :: attention33/examples.mlir (6 of 146)
PASS: IR Forge / Mountain Goat :: transformer30/against-reference.mlir (7 of 146)
PASS: IR Forge / Mountain Goat :: lm35/examples.mlir (8 of 146)
PASS: IR Forge / Mountain Goat :: contraction28/against-definition.mlir (9 of 146)
PASS: IR Forge / Mountain Goat :: contraction/tensor-contraction.mlir (10 of 146)
PASS: IR Forge / Mountain Goat :: attention29/against-reference.mlir (11 of 146)
PASS: IR Forge / Mountain Goat :: generalize32/examples.mlir (12 of 146)
PASS: IR Forge / Mountain Goat :: llvm37/claims.mlir (13 of 146)
PASS: IR Forge / Mountain Goat :: tour/gallery.mlir (14 of 146)
PASS: IR Forge / Mountain Goat :: learning/gradient-descent.mlir (15 of 146)
PASS: IR Forge / Mountain Goat :: bigram31/against-reference.mlir (16 of 146)
PASS: IR Forge / Mountain Goat :: contraction28/examples.mlir (17 of 146)
PASS: IR Forge / Mountain Goat :: tour/tour-examples.mlir (18 of 146)
PASS: IR Forge / Mountain Goat :: attention29/examples.mlir (19 of 146)
PASS: IR Forge / Mountain Goat :: tour/more-examples.mlir (20 of 146)
PASS: IR Forge / Mountain Goat :: loop-order/results-identical.mlir (21 of 146)
PASS: IR Forge / Mountain Goat :: perf/options-same-results.mlir (22 of 146)
PASS: IR Forge / Mountain Goat :: transformer30/examples.mlir (23 of 146)
PASS: IR Forge / Mountain Goat :: loop-order/bitwise-identical.mlir (24 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/values.mlir (25 of 146)
PASS: IR Forge / Mountain Goat :: bigram31/examples.mlir (26 of 146)
PASS: IR Forge / Mountain Goat :: contraction/mismatch-trap.mlir (27 of 146)
PASS: IR Forge / Mountain Goat :: ops/values.mlir (28 of 146)
PASS: IR Forge / Mountain Goat :: ops/elementwise-mismatch-aborts.mlir (29 of 146)
PASS: IR Forge / Mountain Goat :: frontend/cpp-interop.mlir (30 of 146)
PASS: IR Forge / Mountain Goat :: llvm37/examples.mlir (31 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/cpp-interop-reductions.mlir (32 of 146)
PASS: IR Forge / Mountain Goat :: ops/cpp-interop-ops.mlir (33 of 146)
PASS: IR Forge / Mountain Goat :: frontend/more-examples.mlir (34 of 146)
PASS: IR Forge / Mountain Goat :: loop-order/cpp-ikj.mlir (35 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/networks.mlir (36 of 146)
PASS: IR Forge / Mountain Goat :: frontend/dynamic-runs.mlir (37 of 146)
PASS: IR Forge / Mountain Goat :: perf/flags-reach-clang.mlir (38 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/identities.mlir (39 of 146)
PASS: IR Forge / Mountain Goat :: tour/scientific-literals.mlir (40 of 146)
PASS: IR Forge / Mountain Goat :: ops/dynamic-ops.mlir (41 of 146)
PASS: IR Forge / Mountain Goat :: frontend/runtime-mismatch-aborts.mlir (42 of 146)
PASS: IR Forge / Mountain Goat :: perf/tiling-structure.mlir (43 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/dynamic-reductions.mlir (44 of 146)
PASS: IR Forge / Mountain Goat :: execution/gpu-host-with-stub-runtime.mlir (45 of 146)
PASS: IR Forge / Mountain Goat :: execution/dynamic-shapes-run.mlir (46 of 146)
PASS: IR Forge / Mountain Goat :: ops/precedence-and-identities.mlir (47 of 146)
PASS: IR Forge / Mountain Goat :: ops/composed-programs.mlir (48 of 146)
PASS: IR Forge / Mountain Goat :: ops/negate-and-dynamic-divide.mlir (49 of 146)
PASS: IR Forge / Mountain Goat :: frontend/hello-and-static.mlir (50 of 146)
PASS: IR Forge / Mountain Goat :: loop-order/flag-reaches-pass.mlir (51 of 146)
PASS: IR Forge / Mountain Goat :: contraction28/errors.mlir (52 of 146)
PASS: IR Forge / Mountain Goat :: execution/mismatch-aborts.mlir (53 of 146)
PASS: IR Forge / Mountain Goat :: execution/mismatch-columns-aborts.mlir (54 of 146)
PASS: IR Forge / Mountain Goat :: ops/ptx-new-ops.mlir (55 of 146)
PASS: IR Forge / Mountain Goat :: tour/tour-errors.mlir (56 of 146)
PASS: IR Forge / Mountain Goat :: execution/static-add-runs.mlir (57 of 146)
PASS: IR Forge / Mountain Goat :: assert-stderr/message-on-stderr.mlir (58 of 146)
PASS: IR Forge / Mountain Goat :: chapters/ch09-execution-engine.mlir (59 of 146)
PASS: IR Forge / Mountain Goat :: ops/matmul-mismatch-aborts.mlir (60 of 146)
PASS: IR Forge / Mountain Goat :: execution/strided-view.mlir (61 of 146)
PASS: IR Forge / Mountain Goat :: transformer30/errors.mlir (62 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/tiling-runs.mlir (63 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-runs.mlir (64 of 146)
PASS: IR Forge / Mountain Goat :: ops/division-ieee.mlir (65 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/runtime-check-survives-transforms.mlir (66 of 146)
PASS: IR Forge / Mountain Goat :: attention29/errors.mlir (67 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-after-tiling.mlir (68 of 146)
PASS: IR Forge / Mountain Goat :: lm35/errors.mlir (69 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/ptx-layer.mlir (70 of 146)
PASS: IR Forge / Mountain Goat :: assert-stderr/nested-assert-runs.mlir (71 of 146)
PASS: IR Forge / Mountain Goat :: bigram31/errors.mlir (72 of 146)
PASS: IR Forge / Mountain Goat :: execution/mixed-static-dynamic.mlir (73 of 146)
PASS: IR Forge / Mountain Goat :: attention33/errors.mlir (74 of 146)
PASS: IR Forge / Mountain Goat :: frontend/ptx-from-source.mlir (75 of 146)
PASS: IR Forge / Mountain Goat :: chapters/ch01-pipeline.mlir (76 of 146)
PASS: IR Forge / Mountain Goat :: contraction28/ir.mlir (77 of 146)
PASS: IR Forge / Mountain Goat :: assert-stderr/message-bytes-exact.mlir (78 of 146)
PASS: IR Forge / Mountain Goat :: ffn34/errors.mlir (79 of 146)
PASS: IR Forge / Mountain Goat :: assert-stderr/valid-shapes-still-pass.mlir (80 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-needs-constant-trip-counts.mlir (81 of 146)
PASS: IR Forge / Mountain Goat :: generalize32/errors.mlir (82 of 146)
PASS: IR Forge / Mountain Goat :: gpu/pass-order-crash.mlir (83 of 146)
PASS: IR Forge / Mountain Goat :: lm36/errors.mlir (84 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-full-needs-constant-trip-count.mlir (85 of 146)
PASS: IR Forge / Mountain Goat :: gpu/ptx-default.mlir (86 of 146)
PASS: IR Forge / Mountain Goat :: gpu/ptx-index32.mlir (87 of 146)
PASS: IR Forge / Mountain Goat :: loop-order/structure.mlir (88 of 146)
PASS: IR Forge / Mountain Goat :: frontend/front-end-errors.mlir (89 of 146)
PASS: IR Forge / Mountain Goat :: gpu/host-runtime-calls-bare.mlir (90 of 146)
PASS: IR Forge / Mountain Goat :: gpu/ptx-bare-pointers.mlir (91 of 146)
PASS: IR Forge / Mountain Goat :: gpu/host-runtime-calls.mlir (92 of 146)
PASS: IR Forge / Mountain Goat :: attention29/ir.mlir (93 of 146)
PASS: IR Forge / Mountain Goat :: transformer30/ir.mlir (94 of 146)
PASS: IR Forge / Mountain Goat :: gpu/nvvm-lowering.mlir (95 of 146)
PASS: IR Forge / Mountain Goat :: bigram31/ir.mlir (96 of 146)
PASS: IR Forge / Mountain Goat :: chapters/ch02-example-programs.mlir (97 of 146)
PASS: IR Forge / Mountain Goat :: ops/front-end-errors.mlir (98 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/roundtrip-and-lowering.mlir (99 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/front-end-errors.mlir (100 of 146)
PASS: IR Forge / Mountain Goat :: ops/matmul-lowering-structure.mlir (101 of 146)
PASS: IR Forge / Mountain Goat :: assert-stderr/guard-nested-assert.mlir (102 of 146)
PASS: IR Forge / Mountain Goat :: assert-stderr/static-unchanged.mlir (103 of 146)
PASS: IR Forge / Mountain Goat :: gpu/kernel-outlining.mlir (104 of 146)
PASS: IR Forge / Mountain Goat :: frontend/emit-mlir.mlir (105 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-epilogue.mlir (106 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-fires-when-static.mlir (107 of 146)
PASS: IR Forge / Mountain Goat :: generalize32/ir.mlir (108 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-declines.mlir (109 of 146)
PASS: IR Forge / Mountain Goat :: gpu/cuda-comparison.mlir (110 of 146)
PASS: IR Forge / Mountain Goat :: loops/tiling.mlir (111 of 146)
PASS: IR Forge / Mountain Goat :: dynamic-loops/tiling-structure.mlir (112 of 146)
PASS: IR Forge / Mountain Goat :: ops/elementwise-static-mismatch.mlir (113 of 146)
PASS: IR Forge / Mountain Goat :: verifier/transpose-bad-shape.mlir (114 of 146)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice.mlir (115 of 146)
PASS: IR Forge / Mountain Goat :: assert-stderr/run-twice-no-collision.mlir (116 of 146)
PASS: IR Forge / Mountain Goat :: loops/fusion.mlir (117 of 146)
PASS: IR Forge / Mountain Goat :: loops/unroll-full.mlir (118 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/verifier-broadcast.mlir (119 of 146)
PASS: IR Forge / Mountain Goat :: verifier/dynamic-accepted.mlir (120 of 146)
PASS: IR Forge / Mountain Goat :: loop-order/bad-option.mlir (121 of 146)
PASS: IR Forge / Mountain Goat :: ops/matmul-inner-mismatch.mlir (122 of 146)
PASS: IR Forge / Mountain Goat :: verifier/transpose-rank3.mlir (123 of 146)
PASS: IR Forge / Mountain Goat :: assert-stderr/rewrite-structure.mlir (124 of 146)
PASS: IR Forge / Mountain Goat :: verifier/unranked-rejected.mlir (125 of 146)
PASS: IR Forge / Mountain Goat :: ops/matmul-bad-result-shape.mlir (126 of 146)
PASS: IR Forge / Mountain Goat :: broadcast/verifier-reduce.mlir (127 of 146)
PASS: IR Forge / Mountain Goat :: lowering/bufferize-static-add.mlir (128 of 146)
PASS: IR Forge / Mountain Goat :: generalize32/verifiers.mlir (129 of 146)
PASS: IR Forge / Mountain Goat :: verifier/add-static-mismatch.mlir (130 of 146)
PASS: IR Forge / Mountain Goat :: lowering/bufferize-dynamic-add.mlir (131 of 146)
PASS: IR Forge / Mountain Goat :: ops/scalar-bad-op.mlir (132 of 146)
PASS: IR Forge / Mountain Goat :: lowering/dynamic-add-affine.mlir (133 of 146)
PASS: IR Forge / Mountain Goat :: lowering/mixed-add-one-check.mlir (134 of 146)
PASS: IR Forge / Mountain Goat :: canonicalize/fold-constant-add.mlir (135 of 146)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice-dynamic-exact.mlir (136 of 146)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice-dynamic-mixed.mlir (137 of 146)
PASS: IR Forge / Mountain Goat :: ops/dynamic-accepted.mlir (138 of 146)
PASS: IR Forge / Mountain Goat :: lowering/static-add-affine.mlir (139 of 146)
PASS: IR Forge / Mountain Goat :: contraction28/verifiers.mlir (140 of 146)
PASS: IR Forge / Mountain Goat :: lowering/dynamic-transpose-no-check.mlir (141 of 146)
PASS: IR Forge / Mountain Goat :: transformer30/verifiers.mlir (142 of 146)
PASS: IR Forge / Mountain Goat :: attention29/verifiers.mlir (143 of 146)
PASS: IR Forge / Mountain Goat :: bigram31/verifiers.mlir (144 of 146)
PASS: IR Forge / Mountain Goat :: ffn34/examples.mlir (145 of 146)
PASS: IR Forge / Mountain Goat :: ffn34/against-reference.mlir (146 of 146)

Testing Time: 98.73s

Total Discovered Tests: 146
  Passed: 146 (100.00%)

Limits and what is not established

  • One machine, one LLVM. An Intel Xeon (sapphirerapids in LLVM's naming) at 2.1 GHz, LLVM 18.1.3, clang 18.1.3. Vector widths, the choice of 256-bit registers, llvm-mca's numbers and the benchmark all depend on them. The checks pin sapphirerapids; the CPU section shows that gathers, fused multiply-adds and llvm-mca numbers differ on other targets.
  • "Memory-bound" is inferred, not measured. The explanation for the vectorized ijk being no faster is gathers in the assembly plus unchanged timings; no hardware counters (cache misses, TLB misses) were read.
  • The benchmark is the Chapter 24 harness with its noise. Three passes, one pinned core, spreads of up to about 30% between passes at N = 256 (for example ikj's 9.2 to 11.7 GFLOP/s); the contract result at N = 512 is consistent across passes, the one at N = 256 is not.
  • llvm-mca is a core model. It ignores the memory system and assumes perfect branch prediction; the page shows it ranking correctly and over-predicting the gain from vectorizing ijk.
  • -ffast-math was shown to be a no-op on .ll files, but Mountain Goat does not generate the flags. Adding reassoc or contract to the generated IR was done by text substitution in the experiments; it was not added to the compiler, and the results of such programs would no longer be bit-for-bit those of Chapter 24's loop order (reassoc and contract change rounding).
  • The row reductions' mechanism is not identified (see the operations section).
  • Only the matrix product and fourteen single operations were looked at, at 64 × 64; the training programs of Chapters 35 and 36, whose compile time was long, were not studied (where mg-opt spends it is not known).
  • No custom LLVM pass was written, and the AVX-512 question (why 256-bit registers) was not pursued.
  • Platform: x86-64 Linux, LLVM 18.1.3.

Reproducing

cd docs/part32/code && ./build.sh
cd ../../part37/code
./stages.sh > stages_out.txt && ./walk.sh > walk_out.txt && ./remarks.sh > remarks_out.txt && ./ops_table.sh > ops_table_out.txt
./mca.py > mca_out.txt && ./mca.py --loops > loops_out.txt
./variants.sh > variants_out.txt && ./summarize_variants.py > variants_summary.txt
./check_llvm.py > check_llvm_out.txt && ./claims_mutation.py > claims_mutation_out.txt
cd ../../part15/code && ./run_lit.sh          # 146 tests

Chapter summary

  • After MLIR, mgc writes a .ll file (LLVM IR in SSA form: phi for loop counters, getelementptr for addresses, fadd double with no flags). opt then deletes the memref-descriptor packing, turns malloc plus a zero-fill loop into calloc, keeps the matrix product's running sum in a register, and unrolls the inner loop.
  • The default ijk loop is not vectorized because it is a floating-point reduction and LLVM "cannot prove it is safe to reorder floating-point operations". Giving it permission (the reassoc flag in the IR) makes it vectorize, and it gets no faster: the vectorized loop gathers the strided column of b. The loop order, not the vectorizer's permission, is what separates the two (4.6× at N = 256, 10.9× at N = 512).
  • llvm-mca correctly predicts that the ijk chain costs about ten times more than the ikj loop per multiply-add, and incorrectly predicts a 15× gain from vectorizing ijk: it models the core, not the memory.
  • clang's -ffast-math does nothing to a .ll file (the assembly is byte for byte identical); the flags must be in the IR. The contract flag turns ikj's multiply and add into fused multiply-adds, +24% at N = 512 on this machine and no clear gain at N = 256.
  • Element-wise operations vectorize; exp and log do not (library calls); the row reductions vectorize across rows with gathers.
  • Eighteen checks pass; six wrong inputs were caught, and one of them showed that the vectorizer declines the reassociated ijk loop without AVX.

Self-check questions

Each answer is collapsed; try the question first.

  1. Why does LLVM refuse to vectorize sum = sum + a * b but vectorize c[j] = c[j] + x * b[j]?

    Answer

    The first is a reduction: vectorizing it computes several partial sums and adds them at the end, in a different order than the program wrote, and floating-point addition is not associative, so the result could differ in the last digits. LLVM keeps exactly the program's order unless a reassoc flag allows otherwise. The second updates a different element each iteration, so the iterations are independent and doing four at once changes no individual result.

  2. The fadd in the IR has no flags. Where would a C programmer have gotten them, and why did -ffast-math do nothing here?

    Answer

    When clang compiles C or C++ source, -ffast-math makes the front end put fast-math flags (reassoc, nnan, …) on the instructions it generates. mgc generates its instructions through MLIR, with no flags, and then clang is handed a finished .ll file; clang's optimizer reads the flags that are there and does not add any. The assembly with and without the option was byte for byte identical. The flag has to be on the instruction in the IR (fadd reassoc double, or fastmath<reassoc> in MLIR).

  3. With reassoc the ijk loop was vectorized. Why was it not faster?

    Answer

    The loop reads b down a column, one element per row, so a vector of four consecutive k values has to be gathered from four different rows (the assembly has 16 vgather instructions where ikj has none). The vectorized loop moves the same scattered data a scalar loop would. The timings (0.64 against 0.67 GFLOP/s at N = 512) say the arithmetic was not the bottleneck. This is an inference from the instruction counts and the timings; cache misses were not measured.

  4. What does llvm-mca model, and what did the experiment show about its limits?

    Answer

    It models the CPU core: instruction latencies, issue ports and dispatch width, with every load assumed to hit the L1 cache. It ranked ikj above ijk correctly (0.29 against 3.02 cycles per multiply-add) but predicted that vectorizing ijk would be 15 times better (0.20), which the measurement contradicted, because the strided column walk (the real limit) is a memory-system effect it does not simulate.

  5. What does the contract flag allow, and why does LLVM need to be told?

    Answer

    It allows a fmul followed by a fadd to be fused into one fused multiply-add (vfmadd), which rounds once instead of twice and so can give a slightly different result. Without the flag LLVM must keep two roundings. C compilers grant it by default for C source (-ffp-contract=on), which is why it is rarely noticed; a .ll file generated from MLIR has no flags. With the flag the ikj loop became vfmadd instructions and ran about 24% faster at N = 512 (and showed no clear gain at N = 256).

  6. In ops_table_out.txt, exp has no packed arithmetic. What does the assembly do instead, and why does that matter for the transformer chapters?

    Answer

    It calls the C library's exp once per element: LLVM has no vector version of it to use. Softmax in every attention head (Chapters 29 to 36) computes exp over the whole score matrix (112 × 112 per head in Chapters 35 and 36), so those calls are a large part of the work that the matrix products' loop-order tuning does not touch. This chapter did not measure how large.

  7. The chapter's first opt experiment showed 0 vector lines for every pass. What was wrong?

    Answer

    opt was run without a target (-mtriple, -mcpu), so it had no description of the machine's vector instructions and the vectorizer had nothing to vectorize with. With -mtriple=x86_64-unknown-linux-gnu -mcpu=native the same passes vectorize. One of the six wrong inputs in claims_mutation.py reproduces this on purpose, and the checker catches it.