17. Loop Transforms on Dynamic Bounds¶
What you will understand: whether Chapter 7's three loop transforms (fusion, tiling, unrolling) still work, and still give correct answers, when the loop bounds are not known until runtime. Chapter 13 made Mountain Goat handle dynamic shapes and listed this as untested; Chapter 16 listed it again among what the suite did not cover. The chapter runs nine transform variants on a dynamic program across eleven runtime shapes, checks every result against an independent computation, finds what each transform actually does to the IR, and explains the two places where a transform quietly does nothing. Every test, script, harness and IR listing is embedded from the repository.
What you need to know first: Chapter 7's transforms on static loops, Chapter 13's dynamic lowering (memref.dim, operand-bound loops) and Chapter 14's runtime shape check. New ground: how a loop transform copes with a trip count it cannot know.
Compile and run
Every command, listing and output on this page is reproduced by the commands in Reproducing this chapter at the bottom of the page, which also lists what must be built first. The chain of builds is in Getting Started.
Why this page shows FAIL lines, and why that is good
Parts of this page come from negative controls: the same tests run against an older build, or against deliberately broken code (a "mutation"). In those runs a FAIL is the expected, wanted result: it means a test noticed the problem, which is how we know the tests are worth anything. What would be wrong is the opposite, a deliberately broken build that passes everything. The baseline (the unmodified current build) must always show every test passing, and it does. Each script that does this says so in its own header and prints a reminder at the top of its output.
Background: why a dynamic bound makes loop transforms harder¶
Chapter 7 transformed loops like affine.for %i = 0 to 2: the compiler knew the loop ran exactly twice. With dynamic shapes the bound is a value read at runtime: affine.for %i = 0 to %dim. Each transform leans on knowing the trip count in a different way, so each reacts differently:
| Transform | What it needs | What can go wrong with an unknown trip count |
|---|---|---|
| Tiling (split a loop into tile loops and point loops) | nothing about the count, but the last tile may be partial | the point loop must stop at the end of the data, not at the end of the tile, or it reads and writes out of bounds |
| Partial unrolling (repeat the body k times per iteration) | nothing about the count, but it may not be a multiple of k | the leftover iterations must still run, in an epilogue loop, or the tail of the array is skipped |
| Full unrolling (replace the loop with straight-line copies) | a constant trip count: you cannot emit "n copies" when n is unknown | it cannot apply at all |
| Fusion (merge two adjacent loop nests into one) | proof that the two nests cover the same iteration space and that merging preserves every data dependence | with symbolic bounds that proof may be impossible, and a cautious pass declines |
The first two are about correctness at the boundary: the answer must be right for sizes that do not divide the tile or unroll factor. The last two are about the transform declining, which is safe but means no optimization. Both kinds of behavior are measured below.
The test program¶
An add followed by a transpose, with every dimension dynamic. It is the dynamic version of the Chapter 7 chain, and it produces two loop nests with an intermediate buffer between them:
func.func @chain(%a: tensor<?x?xf64>, %b: tensor<?x?xf64>) -> tensor<?x?xf64> {
%s = mg.add %a, %b : tensor<?x?xf64>, tensor<?x?xf64> -> tensor<?x?xf64>
%t = mg.transpose %s : tensor<?x?xf64> to tensor<?x?xf64>
func.return %t : tensor<?x?xf64>
}
After --convert-mg-to-affine it becomes this, the baseline all transforms start from (show/chain_affine.mlir, 45 lines: Chapter 14's two runtime checks, a dynamically sized allocation, then the add nest, then the transpose nest):
Full baseline chain_affine.mlir
#map = affine_map<(d0) -> (d0)>
module {
func.func @chain(%arg0: memref<?x?xf64>, %arg1: memref<?x?xf64>) -> memref<?x?xf64> {
%c0 = arith.constant 0 : index
%dim = memref.dim %arg0, %c0 : memref<?x?xf64>
%c0_0 = arith.constant 0 : index
%dim_1 = memref.dim %arg1, %c0_0 : memref<?x?xf64>
%0 = arith.cmpi eq, %dim, %dim_1 : index
cf.assert %0, "mg.add: operand shapes differ at runtime in dimension 0"
%c1 = arith.constant 1 : index
%dim_2 = memref.dim %arg0, %c1 : memref<?x?xf64>
%c1_3 = arith.constant 1 : index
%dim_4 = memref.dim %arg1, %c1_3 : memref<?x?xf64>
%1 = arith.cmpi eq, %dim_2, %dim_4 : index
cf.assert %1, "mg.add: operand shapes differ at runtime in dimension 1"
%c0_5 = arith.constant 0 : index
%dim_6 = memref.dim %arg0, %c0_5 : memref<?x?xf64>
%c1_7 = arith.constant 1 : index
%dim_8 = memref.dim %arg0, %c1_7 : memref<?x?xf64>
%alloc = memref.alloc(%dim_6, %dim_8) : memref<?x?xf64>
%c0_9 = arith.constant 0 : index
affine.for %arg2 = #map(%c0_9) to #map(%dim_6) {
affine.for %arg3 = #map(%c0_9) to #map(%dim_8) {
%2 = affine.load %arg0[%arg2, %arg3] : memref<?x?xf64>
%3 = affine.load %arg1[%arg2, %arg3] : memref<?x?xf64>
%4 = arith.addf %2, %3 : f64
affine.store %4, %alloc[%arg2, %arg3] : memref<?x?xf64>
}
}
%c1_10 = arith.constant 1 : index
%dim_11 = memref.dim %alloc, %c1_10 : memref<?x?xf64>
%c0_12 = arith.constant 0 : index
%dim_13 = memref.dim %alloc, %c0_12 : memref<?x?xf64>
%alloc_14 = memref.alloc(%dim_11, %dim_13) : memref<?x?xf64>
%c0_15 = arith.constant 0 : index
affine.for %arg2 = #map(%c0_15) to #map(%dim_11) {
affine.for %arg3 = #map(%c0_15) to #map(%dim_13) {
%2 = affine.load %alloc[%arg3, %arg2] : memref<?x?xf64>
affine.store %2, %alloc_14[%arg2, %arg3] : memref<?x?xf64>
}
}
return %alloc_14 : memref<?x?xf64>
}
}
The part that matters is the two nests, each bounded by values read from the buffers' runtime sizes:
%alloc = memref.alloc(%dim_6, %dim_8) : memref<?x?xf64>
%c0_9 = arith.constant 0 : index
affine.for %arg2 = #map(%c0_9) to #map(%dim_6) {
affine.for %arg3 = #map(%c0_9) to #map(%dim_8) {
%2 = affine.load %arg0[%arg2, %arg3] : memref<?x?xf64>
%3 = affine.load %arg1[%arg2, %arg3] : memref<?x?xf64>
%4 = arith.addf %2, %3 : f64
affine.store %4, %alloc[%arg2, %arg3] : memref<?x?xf64>
}
}
%c1_10 = arith.constant 1 : index
%dim_11 = memref.dim %alloc, %c1_10 : memref<?x?xf64>
%c0_12 = arith.constant 0 : index
%dim_13 = memref.dim %alloc, %c0_12 : memref<?x?xf64>
%alloc_14 = memref.alloc(%dim_11, %dim_13) : memref<?x?xf64>
%c0_15 = arith.constant 0 : index
affine.for %arg2 = #map(%c0_15) to #map(%dim_11) {
affine.for %arg3 = #map(%c0_15) to #map(%dim_13) {
%2 = affine.load %alloc[%arg3, %arg2] : memref<?x?xf64>
affine.store %2, %alloc_14[%arg2, %arg3] : memref<?x?xf64>
}
How correctness is checked¶
A transform that keeps the program compiling proves little; the question is whether the numbers are right on awkward sizes. The harness computes transpose(a + b) directly in C for each shape and compares every element of the compiled function's result, exiting non-zero on any mismatch. The eleven shapes include ones chosen to break remainder handling: 1x1, a single row, a single column, and sizes (3x5, 7x4, 5x9, 13x3) that divide neither 2, 4 nor 16 evenly.
// Checks @chain(a, b) = transpose(a + b) for many runtime shapes, comparing against a straightforward C computation.
// Prints one PASS/FAIL line per shape; exits 1 if any shape fails. Shapes include ones that do NOT divide common tile
// sizes (1x1, 5x1, 3x5, 7x4, ...), because remainder handling is where tiling and unrolling go wrong.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct { double *allocated; double *aligned; int64_t offset; int64_t sizes[2]; int64_t strides[2]; } Memref2D;
extern Memref2D chain(double *a0, double *a1, int64_t off0, int64_t s0_0, int64_t s0_1, int64_t st0_0, int64_t st0_1,
double *b0, double *b1, int64_t off1, int64_t s1_0, int64_t s1_1, int64_t st1_0, int64_t st1_1);
static int check(int64_t rows, int64_t cols) {
double *a = malloc(sizeof(double) * rows * cols), *b = malloc(sizeof(double) * rows * cols);
for (int64_t i = 0; i < rows; i++)
for (int64_t j = 0; j < cols; j++) { a[i * cols + j] = i * 10 + j + 1; b[i * cols + j] = (i + 1) * (j + 2) * 0.5; }
Memref2D r = chain(a, a, 0, rows, cols, cols, 1, b, b, 0, rows, cols, cols, 1);
int ok = r.sizes[0] == cols && r.sizes[1] == rows;
for (int64_t i = 0; ok && i < rows; i++)
for (int64_t j = 0; j < cols; j++) {
double want = a[i * cols + j] + b[i * cols + j];
double got = r.aligned[r.offset + j * r.strides[0] + i * r.strides[1]];
if (got != want) { printf(" mismatch at a[%ld][%ld]: want %g got %g\n", (long)i, (long)j, want, got); ok = 0; break; }
}
printf("%-5s %2ldx%-2ld -> result %ldx%ld\n", ok ? "PASS" : "FAIL", (long)rows, (long)cols, (long)r.sizes[0], (long)r.sizes[1]);
free(a); free(b);
return ok;
}
int main(void) {
static const int64_t shapes[][2] = {{1,1},{1,6},{5,1},{2,3},{3,2},{3,5},{4,4},{7,4},{5,9},{8,8},{13,3}};
int allok = 1;
for (unsigned k = 0; k < sizeof shapes / sizeof shapes[0]; k++) allok &= check(shapes[k][0], shapes[k][1]);
printf("%s\n", allok ? "ALL SHAPES PASS" : "SOME SHAPES FAIL");
return allok ? 0 : 1;
}
A second harness calls the same function with operands whose shapes disagree; Chapter 14's runtime check must abort it before any out-of-bounds load:
// Calls @chain with operands whose runtime shapes DISAGREE (a is 2x3, b is 1x2 over a two-element buffer).
// Chapter 14's runtime check must abort the program before any out-of-bounds load; reaching the printf is a failure.
#include <stdint.h>
#include <stdio.h>
typedef struct { double *allocated; double *aligned; int64_t offset; int64_t sizes[2]; int64_t strides[2]; } Memref2D;
extern Memref2D chain(double*,double*,int64_t,int64_t,int64_t,int64_t,int64_t,double*,double*,int64_t,int64_t,int64_t,int64_t,int64_t);
int main(void) {
double a[6] = {1,2,3,4,5,6}, b[2] = {10,20};
Memref2D r = chain(a,a,0,2,3,3,1, b,b,0,1,2,2,1);
printf("returned %ldx%ld (should be unreachable)\n", (long)r.sizes[0], (long)r.sizes[1]);
return 0;
}
run_variants.sh builds each variant to a native executable, runs both harnesses, and reports the transformed IR's loop count:
#!/bin/sh
# Lower chain.mlir (dynamic add then transpose) to affine, apply one set of Chapter 7 passes, lower to native code, and
# (1) run the self-checking harness on eleven runtime shapes,
# (2) run the mismatch harness, which must ABORT (Chapter 14's runtime check must survive the transform).
# Needs ../../part14/code/build.sh to have been run. Output: run_variants_out.txt
# NOTE: the mismatch run is SUPPOSED to abort (non-zero exit status); that is the check passing, not failing.
HERE=$(cd "$(dirname "$0")" && pwd); M=${MG_OPT:-$HERE/../../part14/code/build/mg-opt}; W=$HERE/work; mkdir -p $W
LOW='--lower-affine --convert-scf-to-cf --convert-arith-to-llvm --finalize-memref-to-llvm --convert-func-to-llvm --reconcile-unrealized-casts'
$M $HERE/chain.mlir --convert-mg-to-affine -o $W/chain_affine.mlir || exit 2
build() { # name (expects $W/name.affine.mlir)
$M $W/$1.affine.mlir $LOW -o $W/$1.llvm.mlir 2>$W/$1.err && mlir-translate-18 --mlir-to-llvmir $W/$1.llvm.mlir -o $W/$1.ll &&
clang-18 -c $W/$1.ll -o $W/$1.o 2>/dev/null && clang-18 $HERE/chain_harness.c $W/$1.o -o $W/$1.exe &&
clang-18 $HERE/chain_mismatch_harness.c $W/$1.o -o $W/$1.mm
}
report() { # name
loops=$(grep -c "affine.for" $W/$1.affine.mlir)
shapes=$($W/$1.exe | grep -E "^(ALL|SOME)")
$W/$1.mm >/dev/null 2>&1; rc=$?
case $rc in 134) abort="aborts (exit 134)";; 0) abort="DID NOT ABORT";; *) abort="exit $rc";; esac
printf "%-16s loops=%-2s shapes: %-16s mismatch: %s\n" "$1" "$loops" "$shapes" "$abort"
}
run() { # name, passes...
name=$1; shift
$M $W/chain_affine.mlir "$@" -o $W/$name.affine.mlir 2>$W/$name.err || { echo "$name: transform FAILED: $(head -c 200 $W/$name.err)"; return; }
build $name || { echo "$name: build FAILED: $(head -c 300 $W/$name.err)"; return; }
report $name
}
echo "variant (loops = affine.for in the transformed IR; baseline has 4)"
run baseline
run fusion --affine-loop-fusion
run tile2 --affine-loop-tile="tile-size=2"
run tile4 --affine-loop-tile="tile-size=4"
run tile16 --affine-loop-tile="tile-size=16"
run unroll_full --affine-loop-unroll="unroll-full"
run unroll2 --affine-loop-unroll="unroll-factor=2"
run unroll4 --affine-loop-unroll="unroll-factor=4"
run tile4_unroll2 --affine-loop-tile="tile-size=4" --affine-loop-unroll="unroll-factor=2"
echo
echo "NEGATIVE CONTROL: baseline with every arith.addf rewritten to arith.subf. The harness must FAIL."
sed 's/arith.addf/arith.subf/' $W/baseline.affine.mlir > $W/control.affine.mlir
build control && { $W/control.exe | head -4 | sed 's/^/ /'; $W/control.exe | grep -E "^(ALL|SOME)" | sed 's/^/ /'; }
exit 0
Results¶
The complete, unedited output of that script (run_variants_out.txt):
variant (loops = affine.for in the transformed IR; baseline has 4)
baseline loops=4 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
fusion loops=4 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
tile2 loops=8 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
tile4 loops=8 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
tile16 loops=8 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
unroll_full loops=4 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
unroll2 loops=6 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
unroll4 loops=6 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
tile4_unroll2 loops=8 shapes: ALL SHAPES PASS mismatch: aborts (exit 134)
NEGATIVE CONTROL: baseline with every arith.addf rewritten to arith.subf. The harness must FAIL.
mismatch at a[0][0]: want 2 got 0
FAIL 1x1 -> result 1x1
mismatch at a[0][0]: want 2 got 0
FAIL 1x6 -> result 6x1
SOME SHAPES FAIL
Reading it:
- Every variant passes every shape. Tiling at 2, 4 and 16 (16 is larger than most of the shapes, so there is a single partial tile), partial unrolling at 2 and 4, and tiling followed by unrolling all produced exactly the C answer on all eleven shapes.
- The runtime check survives every transform. The mismatch program aborts (exit 134) in all nine variants, including after tiling plus unrolling. Chapter 14 left open whether a loop transform could reorder or drop the
cf.assert; on this program, it did not. - Two variants changed nothing.
fusionandunroll_fullreportloops=4, the same as the baseline. Section "Where a transform quietly does nothing" below shows that the IR is byte-identical. - The negative control fails as it should. With every
arith.addfrewritten toarith.subf, the harness reportsFAILand prints the first mismatch. This matters: without it, "all shapes pass" could only mean the harness never complains. (The control is applied to the baseline IR, not to a transform, so it shows the harness can fail, not that any transform is wrong.)
Tiling: how the remainder is handled¶
With tile size 4 the add nest becomes the following (show/chain_tile4.mlir; the transpose nest is transformed identically). The two maps first, then the nest:
affine.for %arg2 = #map(%c0_9) to #map(%dim_6) step 4 {
affine.for %arg3 = #map(%c0_9) to #map(%dim_8) step 4 {
affine.for %arg4 = #map(%arg2) to min #map1(%dim_6, %arg2) {
affine.for %arg5 = #map(%arg3) to min #map1(%dim_8, %arg3) {
%2 = affine.load %arg0[%arg4, %arg5] : memref<?x?xf64>
%3 = affine.load %arg1[%arg4, %arg5] : memref<?x?xf64>
%4 = arith.addf %2, %3 : f64
affine.store %4, %alloc[%arg4, %arg5] : memref<?x?xf64>
}
}
}
}
The outer two loops are the tile loops: they step through the data four at a time (step 4). The inner two are the point loops, each walking the elements inside one tile. The remainder is handled by the point loops' upper bound: min #map1(%dim_6, %arg2) means min(%arg2 + 4, %dim_6), since #map1 = (d0, d1) -> (d1 + 4, d0) applied to (%dim_6, %arg2) gives (%arg2 + 4, %dim_6). For all tiles but the last, the first term wins and the tile is full; for the last tile the second term wins and the loop stops at the end of the data. That min is what makes a 5x9 matrix, whose rows and columns are not multiples of 4, come out right.
The structure test pins exactly this shape (the map, step 4 twice per nest, and a min bound on both point loops, for both nests), and a separate test runs the tiled program on all eleven shapes:
// Chapter 17: the tiled dynamic nest steps the tile loops by 4 and clips each point loop with min(...), which is how
// a remainder tile is handled. Two nests (add, transpose), so everything below happens twice.
// RUN: %mg-opt %inputs/chain.mlir --convert-mg-to-affine | %mg-opt --affine-loop-tile="tile-size=4" | %FileCheck %s
// CHECK: #map1 = affine_map<(d0, d1) -> (d1 + 4, d0)>
// CHECK-COUNT-2: affine.for %{{.*}} = #map(%{{.*}}) to #map(%{{.*}}) step 4 {
// CHECK: affine.for %{{.*}} = #map(%{{.*}}) to min #map1(%{{.*}}, %{{.*}}) {
// CHECK: affine.for %{{.*}} = #map(%{{.*}}) to min #map1(%{{.*}}, %{{.*}}) {
// CHECK-COUNT-2: affine.for %{{.*}} = #map(%{{.*}}) to #map(%{{.*}}) step 4 {
// CHECK: to min #map1
// Chapter 17: tiling a DYNAMIC-bound nest (tile size 4) stays correct on eleven runtime shapes, including ones that do not divide 4.
// RUN: %mg-opt %inputs/chain.mlir --convert-mg-to-affine -o %t.affine.mlir
// RUN: %mg-opt %t.affine.mlir --affine-loop-tile="tile-size=4" -o %t.tiled.mlir
// RUN: %mg-opt %t.tiled.mlir %lower-to-llvm -o %t.llvm.mlir
// RUN: %mlir-translate --mlir-to-llvmir %t.llvm.mlir -o %t.ll
// RUN: %clang -c %t.ll -o %t.o
// RUN: %clang %inputs/chain_harness.c %t.o -o %t.exe
// RUN: %t.exe | %FileCheck %s
// CHECK-NOT: FAIL
// CHECK: ALL SHAPES PASS
Partial unrolling: the main loop and the epilogue¶
With unroll-factor=2 the inner loop of the add nest becomes (show/chain_unroll2.mlir):
#map = affine_map<(d0) -> (d0)>
#map1 = affine_map<()[s0] -> ((s0 floordiv 2) * 2)>
#map2 = affine_map<(d0) -> (d0 + 1)>
%c0_9 = arith.constant 0 : index
affine.for %arg2 = #map(%c0_9) to #map(%dim_6) {
affine.for %arg3 = #map(%c0_9) to #map1()[%dim_8] step 2 {
%2 = affine.load %arg0[%arg2, %arg3] : memref<?x?xf64>
%3 = affine.load %arg1[%arg2, %arg3] : memref<?x?xf64>
%4 = arith.addf %2, %3 : f64
affine.store %4, %alloc[%arg2, %arg3] : memref<?x?xf64>
%5 = affine.apply #map2(%arg3)
%6 = affine.load %arg0[%arg2, %5] : memref<?x?xf64>
%7 = affine.load %arg1[%arg2, %5] : memref<?x?xf64>
%8 = arith.addf %6, %7 : f64
affine.store %8, %alloc[%arg2, %5] : memref<?x?xf64>
}
affine.for %arg3 = #map1()[%dim_8] to #map(%dim_8) {
%2 = affine.load %arg0[%arg2, %arg3] : memref<?x?xf64>
%3 = affine.load %arg1[%arg2, %arg3] : memref<?x?xf64>
%4 = arith.addf %2, %3 : f64
affine.store %4, %alloc[%arg2, %arg3] : memref<?x?xf64>
}
}
There are two loops where there was one. The main loop runs from 0 up to (n floordiv 2) * 2 (#map1, n rounded down to a multiple of 2) in steps of 2, and its body holds two copies of the original work (lines 26 to 29 are the iteration at %arg3, lines 30 to 34 the one at %arg3 + 1, computed by affine.apply #map2). The epilogue loop then runs from where the main loop stopped up to n, one iteration at a time. For an even n the epilogue runs zero times; for an odd n it runs once. That is the same remainder idea as tiling's min, expressed as a second loop instead of a clipped bound.
// Chapter 17: unrolling by 2 splits the inner loop into a main loop that stops at (n floordiv 2) * 2 and steps by 2,
// plus an epilogue loop for the leftover iteration. Seen for both nests.
// RUN: %mg-opt %inputs/chain.mlir --convert-mg-to-affine | %mg-opt --affine-loop-unroll="unroll-factor=2" | %FileCheck %s
// CHECK: #map1 = affine_map<()[s0] -> ((s0 floordiv 2) * 2)>
// CHECK: affine.for %{{.*}} = #map(%{{.*}}) to #map1()[%{{.*}}] step 2 {
// CHECK: arith.addf
// CHECK: arith.addf
// CHECK: affine.for %{{.*}} = #map1()[%{{.*}}] to #map(%{{.*}}) {
// CHECK: affine.for %{{.*}} = #map(%{{.*}}) to #map1()[%{{.*}}] step 2 {
// CHECK: affine.for %{{.*}} = #map1()[%{{.*}}] to #map(%{{.*}}) {
// Chapter 17: partial unrolling (factor 4) of a dynamic-bound nest stays correct on eleven shapes, remainders included.
// RUN: %mg-opt %inputs/chain.mlir --convert-mg-to-affine -o %t.affine.mlir
// RUN: %mg-opt %t.affine.mlir --affine-loop-unroll="unroll-factor=4" -o %t.unrolled.mlir
// RUN: %mg-opt %t.unrolled.mlir %lower-to-llvm -o %t.llvm.mlir
// RUN: %mlir-translate --mlir-to-llvmir %t.llvm.mlir -o %t.ll
// RUN: %clang -c %t.ll -o %t.o
// RUN: %clang %inputs/chain_harness.c %t.o -o %t.exe
// RUN: %t.exe | %FileCheck %s
// CHECK-NOT: FAIL
// CHECK: ALL SHAPES PASS
Where a transform quietly does nothing¶
Full unrolling needs a constant trip count¶
Applied to the fully dynamic chain, --affine-loop-unroll="unroll-full" produced no error and no change. fusion_probe.sh and show.sh record that the output is byte-identical to the input:
That is the expected behavior (you cannot write out "n copies" for an unknown n) but it is worth seeing because the pass reports nothing: a script that assumed full unrolling had happened would be wrong without any diagnostic. With a partially static shape the same pass does work on the loop whose trip count is known. For tensor<?x2xf64> the add nest's inner loop runs exactly twice:
func.func @chain2(%a: tensor<?x2xf64>, %b: tensor<?x2xf64>) -> tensor<2x?xf64> {
%s = mg.add %a, %b : tensor<?x2xf64>, tensor<?x2xf64> -> tensor<?x2xf64>
%t = mg.transpose %s : tensor<?x2xf64> to tensor<2x?xf64>
func.return %t : tensor<2x?xf64>
}
and full unrolling removed that loop (4 loops down to 3) and left the dynamic outer loop (show/chain2_unroll_full.mlir, add nest):
affine.for %arg2 = #map(%c0_5) to #map(%dim_4) {
%1 = affine.load %arg0[%arg2, %c0] : memref<?x2xf64>
%2 = affine.load %arg1[%arg2, %c0] : memref<?x2xf64>
%3 = arith.addf %1, %2 : f64
affine.store %3, %alloc[%arg2, %c0] : memref<?x2xf64>
%4 = affine.apply #map1(%c0)
%5 = affine.load %arg0[%arg2, %4] : memref<?x2xf64>
%6 = affine.load %arg1[%arg2, %4] : memref<?x2xf64>
%7 = arith.addf %5, %6 : f64
affine.store %7, %alloc[%arg2, %4] : memref<?x2xf64>
}
The two stores, [%arg2, %c0] and [%arg2, %4], are the two unrolled iterations of the former inner loop, inside the surviving dynamic loop over rows. The transpose nest keeps its loops: its outer loop is the static one, and full unrolling only targets innermost loops (a Chapter 7 finding).
// Chapter 17: full unrolling needs a constant trip count. With fully dynamic bounds it silently does nothing (4 loops stay 4);
// with a ?x2 shape the add nest's inner loop (trip count 2) is unrolled away (4 -> 3 loops) and the dynamic loops remain.
// RUN: %mg-opt %inputs/chain.mlir --convert-mg-to-affine | %mg-opt --affine-loop-unroll="unroll-full" | %FileCheck %s --check-prefix=DYN
// RUN: %mg-opt %inputs/chain2.mlir --convert-mg-to-affine | %mg-opt --affine-loop-unroll="unroll-full" | %FileCheck %s --check-prefix=PART
// DYN-COUNT-4: affine.for
// DYN-NOT: affine.for
// PART-COUNT-3: affine.for
// PART-NOT: affine.for
Fusion declines on dynamic bounds, and why that was narrowed down but not explained¶
--affine-loop-fusion left the dynamic chain alone (show/fusion_noop.txt):
An obvious guess is that the transpose's access pattern is the blocker, since Chapter 7 found that fusing add with transpose required permuting a loop. fusion_probe.sh tests that with three programs: the dynamic chain, a dynamic add followed by another add (no transpose, identical index patterns), and the same add-then-transpose chain with static 4x6 bounds:
#!/bin/sh
# Why did --affine-loop-fusion do nothing on the dynamic chain? Narrowing it down with three programs. Output: fusion_probe_out.txt
HERE=$(cd "$(dirname "$0")" && pwd); M=${MG_OPT:-$HERE/../../part14/code/build/mg-opt}; W=$HERE/work; mkdir -p $W
count() { grep -c "affine.for" "$1"; }
for p in chain addadd static_chain; do
$M $HERE/$p.mlir --convert-mg-to-affine -o $W/$p.affine.mlir
$M $W/$p.affine.mlir --affine-loop-fusion -o $W/$p.fused.mlir
printf "%-14s affine.for before fusion: %s after: %s\n" $p $(count $W/$p.affine.mlir) $(count $W/$p.fused.mlir)
done
echo
echo "partial static shape: ?x2 chain, loops before / after full unroll / after fusion"
$M $HERE/chain2.mlir --convert-mg-to-affine -o $W/chain2.affine.mlir
printf "chain2 before: %s after unroll-full: %s after fusion: %s\n" $(count $W/chain2.affine.mlir) \
$($M $W/chain2.affine.mlir --affine-loop-unroll="unroll-full" | grep -c "affine.for") \
$($M $W/chain2.affine.mlir --affine-loop-fusion | grep -c "affine.for")
chain affine.for before fusion: 4 after: 4
addadd affine.for before fusion: 4 after: 4
static_chain affine.for before fusion: 4 after: 2
partial static shape: ?x2 chain, loops before / after full unroll / after fusion
chain2 before: 4 after unroll-full: 3 after fusion: 4
The result disproves the guess. The dynamic add-then-add chain is also left at 4 loops, while the static add-then-transpose chain fuses from 4 loops to 2. So the transpose is not what blocks fusion; dynamic bounds are, at least in this form. The static fused result, for comparison (show/static_chain_fused.mlir; note the intermediate buffer shrank to a 1x1 scalar slot, as in Chapter 7):
module {
func.func @chain(%arg0: memref<4x6xf64>, %arg1: memref<4x6xf64>) -> memref<6x4xf64> {
%alloc = memref.alloc() : memref<1x1xf64>
%alloc_0 = memref.alloc() : memref<6x4xf64>
affine.for %arg2 = 0 to 6 {
affine.for %arg3 = 0 to 4 {
%0 = affine.load %arg0[%arg3, %arg2] : memref<4x6xf64>
%1 = affine.load %arg1[%arg3, %arg2] : memref<4x6xf64>
%2 = arith.addf %0, %1 : f64
affine.store %2, %alloc[0, 0] : memref<1x1xf64>
%3 = affine.load %alloc[0, 0] : memref<1x1xf64>
affine.store %3, %alloc_0[%arg2, %arg3] : memref<6x4xf64>
}
}
return %alloc_0 : memref<6x4xf64>
}
}
Why fusion declines was not established. Plausible explanations include that the intermediate buffer's size is dynamic, or that the dependence analysis cannot prove the two nests' symbolic iteration spaces equal; this chapter did not read the pass's source, as Chapter 12 did for other passes, and no test here distinguishes those explanations. The honest summary is a measured limitation without a verified cause. (Update, added after Chapter 18: the cause is now established. The pass's profitability analysis requires a constant trip count for every loop in both nests; dynamic buffer shapes alone do not block fusion. Chapter 18 also found that tiling and then fusing dynamic loops produces invalid IR.)
Two tests pin the pair: one asserts that fusion leaves the dynamic nests at four loops, with a header saying it is designed to start failing if a newer toolchain fuses them (in the same spirit as Chapter 16's crash test), and one asserts that the identical chain with static bounds does fuse, so the first test cannot pass merely because fusion is broken everywhere.
// Chapter 17: PINS AN OBSERVED LIMITATION. --affine-loop-fusion leaves a dynamic-bound nest pair alone: 4 loops in, 4 out
// (the same pair with static bounds fuses 4 -> 2, see loops/fusion.mlir). The cause was not established. If a newer
// toolchain starts fusing these, this test fails: that is the signal to revisit Chapter 17, not a regression.
// RUN: %mg-opt %inputs/chain.mlir --convert-mg-to-affine | %mg-opt --affine-loop-fusion | %FileCheck %s
// CHECK-COUNT-4: affine.for
// CHECK-NOT: affine.for
// Chapter 17: the control for fusion-declines: the SAME add-then-transpose chain with static 4x6 bounds does fuse (4 -> 2 loops).
// RUN: %mg-opt %inputs/static_chain.mlir --convert-mg-to-affine | %mg-opt --affine-loop-fusion | %FileCheck %s
// CHECK-COUNT-2: affine.for
// CHECK-NOT: affine.for
The runtime check survives the transforms¶
Chapter 14 closed an out-of-bounds read with a cf.assert emitted before the loop, and noted it was untested whether a loop transform preserves it. The test applies tiling and unrolling together, builds the mismatch harness, and requires the process to abort, with the explanation visible under line-buffered output:
// Chapter 17: Chapter 14's runtime shape check must survive tiling and unrolling: a mismatched call still ABORTS.
// RUN: %mg-opt %inputs/chain.mlir --convert-mg-to-affine -o %t.affine.mlir
// RUN: %mg-opt %t.affine.mlir --affine-loop-tile="tile-size=4" --affine-loop-unroll="unroll-factor=2" -o %t.xf.mlir
// RUN: %mg-opt %t.xf.mlir %lower-to-llvm -o %t.llvm.mlir
// RUN: %mlir-translate --mlir-to-llvmir %t.llvm.mlir -o %t.ll
// RUN: %clang -c %t.ll -o %t.o
// RUN: %clang %inputs/chain_mismatch_harness.c %t.o -o %t.exe
// RUN: %not --crash %t.exe
// RUN: %not --crash stdbuf -oL %t.exe 2>&1 | %FileCheck %s
// CHECK: mg.add: operand shapes differ at runtime in dimension 0
This holds on this program for these transforms. It is an observation, not a proof: the assert is outside the loops, so tiling and unrolling, which rewrite loop nests, have no reason to touch it, and nothing here examines passes that could move or remove it.
The tests, and whether they can fail¶
The suite grew from 34 tests (Chapter 16) to 42 with the eight above. The complete run (run_out_42.txt):
-- Testing: 42 tests, 4 workers --
PASS: IR Forge / Mountain Goat :: execution/static-add-runs.mlir (1 of 42)
PASS: IR Forge / Mountain Goat :: execution/dynamic-shapes-run.mlir (2 of 42)
PASS: IR Forge / Mountain Goat :: execution/mismatch-aborts.mlir (3 of 42)
PASS: IR Forge / Mountain Goat :: execution/gpu-host-with-stub-runtime.mlir (4 of 42)
PASS: IR Forge / Mountain Goat :: execution/mixed-static-dynamic.mlir (5 of 42)
PASS: IR Forge / Mountain Goat :: execution/strided-view.mlir (6 of 42)
PASS: IR Forge / Mountain Goat :: gpu/ptx-default.mlir (7 of 42)
PASS: IR Forge / Mountain Goat :: gpu/pass-order-crash.mlir (8 of 42)
PASS: IR Forge / Mountain Goat :: gpu/ptx-index32.mlir (9 of 42)
PASS: IR Forge / Mountain Goat :: execution/mismatch-columns-aborts.mlir (10 of 42)
PASS: IR Forge / Mountain Goat :: gpu/host-runtime-calls.mlir (11 of 42)
PASS: IR Forge / Mountain Goat :: gpu/host-runtime-calls-bare.mlir (12 of 42)
PASS: IR Forge / Mountain Goat :: gpu/nvvm-lowering.mlir (13 of 42)
PASS: IR Forge / Mountain Goat :: loops/tiling.mlir (14 of 42)
PASS: IR Forge / Mountain Goat :: gpu/ptx-bare-pointers.mlir (15 of 42)
PASS: IR Forge / Mountain Goat :: gpu/kernel-outlining.mlir (16 of 42)
PASS: IR Forge / Mountain Goat :: verifier/dynamic-accepted.mlir (17 of 42)
PASS: IR Forge / Mountain Goat :: gpu/cuda-comparison.mlir (18 of 42)
PASS: IR Forge / Mountain Goat :: lowering/static-add-affine.mlir (19 of 42)
PASS: IR Forge / Mountain Goat :: verifier/unranked-rejected.mlir (20 of 42)
PASS: IR Forge / Mountain Goat :: lowering/mixed-add-one-check.mlir (21 of 42)
PASS: IR Forge / Mountain Goat :: verifier/transpose-bad-shape.mlir (22 of 42)
PASS: IR Forge / Mountain Goat :: lowering/dynamic-transpose-no-check.mlir (23 of 42)
PASS: IR Forge / Mountain Goat :: loops/fusion.mlir (24 of 42)
PASS: IR Forge / Mountain Goat :: verifier/transpose-rank3.mlir (25 of 42)
PASS: IR Forge / Mountain Goat :: lowering/bufferize-static-add.mlir (26 of 42)
PASS: IR Forge / Mountain Goat :: loops/unroll-full.mlir (27 of 42)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice-dynamic-exact.mlir (28 of 42)
PASS: IR Forge / Mountain Goat :: verifier/add-static-mismatch.mlir (29 of 42)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice-dynamic-mixed.mlir (30 of 42)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice.mlir (31 of 42)
PASS: IR Forge / Mountain Goat :: lowering/bufferize-dynamic-add.mlir (32 of 42)
PASS: IR Forge / Mountain Goat :: canonicalize/fold-constant-add.mlir (33 of 42)
PASS: IR Forge / Mountain Goat :: lowering/dynamic-add-affine.mlir (34 of 42)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-fires-when-static.mlir (35 of 42)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-declines.mlir (36 of 42)
PASS: IR Forge / Mountain Goat :: dynamic-loops/tiling-structure.mlir (37 of 42)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-epilogue.mlir (38 of 42)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-full-needs-constant-trip-count.mlir (39 of 42)
PASS: IR Forge / Mountain Goat :: dynamic-loops/runtime-check-survives-transforms.mlir (40 of 42)
PASS: IR Forge / Mountain Goat :: dynamic-loops/tiling-runs.mlir (41 of 42)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-runs.mlir (42 of 42)
Testing Time: 0.86s
Total Discovered Tests: 42
Passed: 42 (100.00%)
Passing on a first run proves nothing, so dynloops_mutation.sh changes one thing in a copy of the suite per mutation and runs only the affected test. It carries forward the guard from Chapter 16 that rejects any mutation which changes the file's line count:
#!/bin/sh
# Chapter 17: do the dynamic-loop tests fail when the thing they pin changes? Each mutation edits ONE file in a COPY of the
# suite and runs only the affected test. A mutation that changes the file's line count is rejected (a substitution never should).
# READ THIS FIRST: this script injects deliberate bugs into the dynamic-loop tests' subject and re-runs the tests.
# FAIL lines (and non-zero exit statuses) in this script's output are the EXPECTED result: each injected bug SHOULD make at least one test fail.
# The unmodified, current build is the baseline and must show no failures. A mutation or old build that makes NO test fail would be the problem.
echo "NOTE: this script deliberately runs broken or older code. FAIL lines below are EXPECTED: they show the tests can detect the problem. The baseline (unmodified current build) must show none."
HERE=$(cd "$(dirname "$0")" && pwd)
export MG_OPT=${MG_OPT:-$HERE/../../part14/code/build/mg-opt}
export DECODE_PTX=$(cd "$HERE/../../part10/code" && pwd)/decode_ptx.py
n=0
mut() { # description | file under test/ | sed expression | test to run
n=$((n+1)); W=$HERE/work/dm-$n; rm -rf "$W"; mkdir -p "$W"; cp -r "$HERE/test" "$W/test"
sed -i "$3" "$W/test/$2"
if cmp -s "$HERE/test/$2" "$W/test/$2"; then echo "MUTATION $n NOT APPLIED ($1)"; return; fi
if [ "$(wc -l < "$HERE/test/$2")" != "$(wc -l < "$W/test/$2")" ]; then echo "MUTATION $n MALFORMED ($1): line count changed"; return; fi
out=$(MG_TEST_TMP="$W/out" lit "$W/test/$4" 2>&1 | grep -E "^(PASS|FAIL)" | sed 's/IR Forge \/ Mountain Goat :: //;s/ ([0-9]* of [0-9]*)//')
echo "MUTATION $n: $1"; echo " $out"
}
mut "tile size 4 -> 2 in the structure test's recipe" dynamic-loops/tiling-structure.mlir '/RUN:/s/tile-size=4/tile-size=2/' dynamic-loops/tiling-structure.mlir
mut "unroll factor 2 -> 4 in the epilogue test's recipe" dynamic-loops/unroll-epilogue.mlir '/RUN:/s/unroll-factor=2/unroll-factor=4/' dynamic-loops/unroll-epilogue.mlir
mut "fusion-declines run on the STATIC chain (fusion fires)" dynamic-loops/fusion-declines.mlir '/RUN:/s#%inputs/chain.mlir#%inputs/static_chain.mlir#' dynamic-loops/fusion-declines.mlir
mut "self-checking harness computes a-b instead of a+b" Inputs/chain_harness.c 's/double want = a\[i \* cols + j\] + b\[i \* cols + j\];/double want = a[i * cols + j] - b[i * cols + j];/' dynamic-loops/tiling-runs.mlir
mut "partial-static unroll test fed the fully dynamic chain" dynamic-loops/unroll-full-needs-constant-trip-count.mlir '/check-prefix=PART/s#%inputs/chain2.mlir#%inputs/chain.mlir#' dynamic-loops/unroll-full-needs-constant-trip-count.mlir
mut "mismatch harness made to MATCH (no abort expected)" Inputs/chain_mismatch_harness.c 's/b\[2\] = {10,20}/b[6] = {10,20,30,40,50,60}/; s/b,b,0,1,2,2,1/b,b,0,2,3,3,1/' dynamic-loops/runtime-check-survives-transforms.mlir
mut "rule test: the DECLINES run for A fed the static control C" dynamic-loops/fusion-needs-constant-trip-counts.mlir '/RUN:.*exp_A.mlir/s#exp_A.mlir#exp_C.mlir#' dynamic-loops/fusion-needs-constant-trip-counts.mlir
mut "rule test: the FUSES run for B fed the dynamic-bound program A" dynamic-loops/fusion-needs-constant-trip-counts.mlir '/RUN:.*exp_B.mlir/s#exp_B.mlir#exp_A.mlir#' dynamic-loops/fusion-needs-constant-trip-counts.mlir
mut "rule test: the DECLINES run for G fed the static control C" dynamic-loops/fusion-needs-constant-trip-counts.mlir '/RUN:.*exp_G.mlir/s#exp_G.mlir#exp_C.mlir#' dynamic-loops/fusion-needs-constant-trip-counts.mlir
mut "bug-pin test: the dynamic run fed the STATIC chain (no error expected)" dynamic-loops/fusion-after-tiling.mlir '/RUN: %mg-opt %inputs\/chain.mlir/s#chain.mlir#static_chain.mlir#' dynamic-loops/fusion-after-tiling.mlir
mut "bug-pin test: static run for tile 1 given tile size 2 instead" dynamic-loops/fusion-after-tiling.mlir '/RUN:.*static_chain.*tile-size=1/s#tile-size=1#tile-size=2#' dynamic-loops/fusion-after-tiling.mlir
MUTATION 1: tile size 4 -> 2 in the structure test's recipe
FAIL: dynamic-loops/tiling-structure.mlir
MUTATION 2: unroll factor 2 -> 4 in the epilogue test's recipe
FAIL: dynamic-loops/unroll-epilogue.mlir
MUTATION 3: fusion-declines run on the STATIC chain (fusion fires)
FAIL: dynamic-loops/fusion-declines.mlir
MUTATION 4: self-checking harness computes a-b instead of a+b
FAIL: dynamic-loops/tiling-runs.mlir
MUTATION 5: partial-static unroll test fed the fully dynamic chain
FAIL: dynamic-loops/unroll-full-needs-constant-trip-count.mlir
MUTATION 6: mismatch harness made to MATCH (no abort expected)
FAIL: dynamic-loops/runtime-check-survives-transforms.mlir
MUTATION 7: rule test: the DECLINES run for A fed the static control C
FAIL: dynamic-loops/fusion-needs-constant-trip-counts.mlir
MUTATION 8: rule test: the FUSES run for B fed the dynamic-bound program A
FAIL: dynamic-loops/fusion-needs-constant-trip-counts.mlir
MUTATION 9: rule test: the DECLINES run for G fed the static control C
FAIL: dynamic-loops/fusion-needs-constant-trip-counts.mlir
MUTATION 10: bug-pin test: the dynamic run fed the STATIC chain (no error expected)
FAIL: dynamic-loops/fusion-after-tiling.mlir
MUTATION 11: bug-pin test: static run for tile 1 given tile size 2 instead
FAIL: dynamic-loops/fusion-after-tiling.mlir
All six mutations are caught: a changed tile size, a changed unroll factor, the "fusion declines" test fed the static chain (so fusion fires and the test fails, showing it really detects fusion firing), a harness whose expected value is wrong (so every shape fails), the partial-static unroll test fed the fully dynamic chain, and a mismatch harness changed to match (so nothing aborts). In the first run of this script, mutation 6 reported NOT APPLIED: it had been written with two -e expressions that the helper's single-expression interface mishandled. The script surfaced it instead of counting it as a pass; it was rewritten as one expression and rerun, and its diff is now exactly the two intended lines.
What this does and does not establish¶
- One program, two nests. Everything above is the add-then-transpose chain and two sibling programs. Other op sequences were not tried.
- Eleven shapes is a sample. The shapes were chosen to include remainders, but eleven is not exhaustive, and very large sizes were not tried.
- Correctness only, no performance. Tiling and unrolling exist to make code faster, but nothing here was timed. A transform can be correct and slower; no claim about speed is made.
- Fusion's cause is unexplained (update, added after Chapter 18: explained there), as stated above, and it is a limitation of this toolchain version's pass on this IR, not a statement about fusion in general.
- Only Chapter 7's transforms. No other affine passes (interchange, vectorization, loop-invariant code motion) were examined.
- Rank 2 only, as throughout since Chapter 13.
- The GPU path was not run on dynamic shapes; the bare-pointer option still requires static shapes (Chapter 12).
- No CI. The suite runs when someone runs it.
Reproducing this chapter¶
../part14/code/build.sh # the mg-opt under test (and: pip install lit)
cd docs/part17/code
./run_variants.sh > run_variants_out.txt # nine variants x eleven shapes, abort check, negative control
./fusion_probe.sh > fusion_probe_out.txt # narrowing down why fusion declined
./show.sh # the IR listings above, under show/
cd ../part15/code
./run_lit.sh > run_out_42.txt # the 42-test suite
./dynloops_mutation.sh # the six mutations
Every file and output above is embedded from the repository when the site is built, so this page cannot drift from the code it describes. As in Chapters 10 through 16, no documentation was consulted for any claim: each result comes from running the commands.
Chapter summary¶
This chapter settled whether Chapter 7's loop transforms survive dynamic bounds. Tiling (sizes 2, 4 and 16), partial unrolling (factors 2 and 4) and tiling plus unrolling all produced exactly the right answer on eleven runtime shapes, including shapes that divide neither the tile nor the unroll factor, because tiling clips each point loop with a min bound and unrolling adds an epilogue loop for the leftover iterations. Chapter 14's runtime shape check survived every transform. Two transforms quietly do nothing: full unrolling needs a constant trip count (and works on a loop whose count is static, such as the 2 in ?x2), and fusion declines on dynamic bounds even for a plain add-then-add chain, while the same static add-then-transpose chain fuses from 4 loops to 2. The cause of the fusion limitation was narrowed (it is not the transpose) but not established. Eight new lit tests pin all of this and six mutations were all caught.
Deliberately out of scope, stated explicitly: nothing was timed, so no claim is made that any transform helps; only one program and Chapter 7's three transforms were examined; fusion's cause is unexplained; and the GPU path and rank other than 2 were not touched.
Self-check questions¶
1. Why must tiling clip its point loops with min(arg + tile, n), and what would go wrong without the min?
Worked answer: the tile loop steps through the data in strides of the tile size, but when n is not a multiple of the tile size the last tile is partial. A point loop running a fixed tile-size number of iterations would walk past the end of the data in that last tile, reading and writing out of bounds. The min bound makes the last tile stop at n. The chapter's evidence is the tiled IR (min #map1(%dim_6, %arg2)) and the passing results on 5x9, 7x4, 13x3 and other shapes that are not multiples of 4.
2. What does the epilogue loop do after partial unrolling, and when does it run zero times?
Worked answer: the main loop runs up to (n floordiv k) * k, n rounded down to a multiple of the unroll factor k, stepping by k with k copies of the body. The epilogue loop runs the remaining n mod k iterations one at a time. When n is already a multiple of k the main loop covers everything and the epilogue loop's range is empty, so it runs zero times. For unroll-factor=2 that is every even n.
3. Full unrolling produced no error and no change on the dynamic chain. Why is "no error" a trap, and how was the no-op demonstrated?
Worked answer: a pass that declines to apply reports nothing, so a script or reader could assume the loops were unrolled when they were not. The chapter shows the output IR is byte-identical to the input (cmp), and the loop count stays at 4. The reason is that full unrolling must emit a fixed number of copies of the body, which needs a constant trip count; with a bound read from memref.dim there is none. With tensor<?x2xf64> the inner loop's count is the constant 2, and the same pass does unroll it (4 loops down to 3).
4. A natural guess is that the transpose's access pattern stops --affine-loop-fusion on the dynamic chain. How did the chapter test that guess, and what was the answer?
Worked answer: it ran fusion on three programs: the dynamic add-then-transpose chain, a dynamic add-then-add chain (identical index patterns, no transpose), and the same add-then-transpose chain with static 4x6 bounds. The dynamic add-then-add chain was also left at 4 loops, while the static add-then-transpose chain fused to 2. So the transpose is not the blocker; dynamic bounds are. The chapter then stops: it did not establish why dynamic bounds block fusion, and says no test distinguishes the candidate explanations. (Update, added after Chapter 18: the pass requires constant trip counts for every loop in both nests, found by reading the source and confirmed with six experiments.)
5. Why does fusion-declines.mlir come with a companion test, fusion-fires-when-static.mlir, and what is the first test designed to do if the toolchain changes?
Worked answer: the first test passes when fusion leaves the dynamic nests alone, which would also be true if fusion were simply broken everywhere. The companion shows the same chain with static bounds does fuse (4 loops to 2), so the first test is passing for the specific reason the chapter claims. The first test is also designed to start failing if a newer toolchain begins fusing dynamic nests: that is the signal to revisit this chapter's finding, not a regression in the book.