Skip to content

18. Why Fusion Declines: Reading the Pass, and a Second Bug Found Along the Way

Mountain goats on the mountain at dawn

What you will understand: why --affine-loop-fusion does nothing on loops with dynamic bounds, which Chapter 17 measured but could not explain. The method is the one that works for any opaque compiler behavior: read the source, form a hypothesis, then design experiments that discriminate between hypotheses rather than merely agree with one. The result is a precise rule, established from the pass's own code and confirmed on six hand-written programs. Testing the obvious workaround then exposed a second, unrelated problem: the same pass produces invalid IR on tiled dynamic loops. Every source excerpt on this page is embedded from unmodified copies of the LLVM 18.1.3 files kept in the repository.

What you need to know first: Chapter 17's results, in particular the fusion rows. New ground: how a loop-fusion pass decides whether to fuse (a cost model), and reading MLIR's affine transform source.

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: what a fusion pass decides

Two adjacent loop nests, where the first writes a buffer and the second reads it, can often be merged into one nest, so each element is consumed right after it is produced and the intermediate buffer can shrink. Chapter 7 showed this on static loops: an add nest and a transpose nest became one nest and a 4x6 buffer became a single scalar slot. But fusion is not always a win (it can duplicate work), so the pass does not fuse blindly. It runs a profitability analysis: a cost model that counts operation instances (roughly, ops in the body times trip counts) for the nests before and after fusion and compares them. A cost model made of products of trip counts needs the trip counts as numbers. That is the thread this chapter pulls.

What Chapter 17 observed

Fusion left the dynamic chain at four loops. A dynamic add-then-add chain was also left alone, while the same add-then-transpose chain with static bounds fused from four loops to two. That ruled out the transpose, and Chapter 17 stopped there: "dynamic bounds block fusion; the cause was not established". The pass reports nothing when it declines, so the observable behavior is only "the IR did not change".

Step 1: read the source

isFusionProfitable is the function that decides. Its opening lines (LoopFusion.cpp):

static bool isFusionProfitable(Operation *srcOpInst, Operation *srcStoreOpInst,
                               AffineForOp dstForOp,
                               ArrayRef<ComputationSliceState> depthSliceUnions,
                               unsigned maxLegalFusionDepth,
                               unsigned *dstLoopDepth,
                               double computeToleranceThreshold) {
  LLVM_DEBUG({
    llvm::dbgs() << "Checking whether fusion is profitable between src op:\n";
    llvm::dbgs() << ' ' << *srcOpInst << " and destination loop:\n";
    llvm::dbgs() << dstForOp << "\n";
  });

  if (maxLegalFusionDepth == 0) {
    LLVM_DEBUG(llvm::dbgs() << "Can't fuse: maxLegalFusionDepth is 0\n");
    return false;
  }

  // Compute cost of sliced and unsliced src loop nest.
  SmallVector<AffineForOp, 4> srcLoopIVs;
  getAffineForIVs(*srcOpInst, &srcLoopIVs);

  // Walk src loop nest and collect stats.
  LoopNestStats srcLoopNestStats;
  if (!getLoopNestStats(srcLoopIVs[0], &srcLoopNestStats))
    return false;

  // Compute cost of dst loop nest.
  LoopNestStats dstLoopNestStats;
  if (!getLoopNestStats(dstForOp, &dstLoopNestStats))
    return false;

Two early exits matter. Lines 468 and 473 call getLoopNestStats on the producer nest and on the consumer nest and return false (decline) if either call fails. getLoopNestStats (in LoopFusionUtils.cpp) is where the trip counts are collected:

/// Collect loop nest statistics (eg. loop trip count and operation count)
/// in 'stats' for loop nest rooted at 'forOp'. Returns true on success,
/// returns false otherwise.
bool mlir::affine::getLoopNestStats(AffineForOp forOpRoot,
                                    LoopNestStats *stats) {
  auto walkResult = forOpRoot.walk([&](AffineForOp forOp) {
    auto *childForOp = forOp.getOperation();
    auto *parentForOp = forOp->getParentOp();
    if (forOp != forOpRoot) {
      if (!isa<AffineForOp>(parentForOp)) {
        LLVM_DEBUG(llvm::dbgs() << "Expected parent AffineForOp\n");
        return WalkResult::interrupt();
      }
      // Add mapping to 'forOp' from its parent AffineForOp.
      stats->loopMap[parentForOp].push_back(forOp);
    }

    // Record the number of op operations in the body of 'forOp'.
    unsigned count = 0;
    stats->opCountMap[childForOp] = 0;
    for (auto &op : *forOp.getBody()) {
      if (!isa<AffineForOp, AffineIfOp>(op))
        ++count;
    }
    stats->opCountMap[childForOp] = count;

    // Record trip count for 'forOp'. Set flag if trip count is not
    // constant.
    std::optional<uint64_t> maybeConstTripCount = getConstantTripCount(forOp);
    if (!maybeConstTripCount) {
      // Currently only constant trip count loop nests are supported.
      LLVM_DEBUG(llvm::dbgs() << "Non-constant trip count unsupported\n");
      return WalkResult::interrupt();
    }

    stats->tripCountMap[childForOp] = *maybeConstTripCount;
    return WalkResult::advance();
  });
  return !walkResult.wasInterrupted();

The relevant lines are the walk over every affine.for in the nest, and inside it: if getConstantTripCount(forOp) yields no value, the code logs "Non-constant trip count unsupported" and interrupts the walk, so the function returns false. The comment is explicit: // Currently only constant trip count loop nests are supported. One loop with a non-constant trip count anywhere in either nest is enough.

A second exit exists a little further down. After the cost stats, the pass computes the size of the region the producer writes (LoopFusion.cpp):

  MemRefRegion srcWriteRegion(srcStoreOpInst->getLoc());
  if (failed(srcWriteRegion.compute(srcStoreOpInst, /*loopDepth=*/0))) {
    LLVM_DEBUG(llvm::dbgs()
               << "Unable to compute MemRefRegion for source operation\n");
    return false;
  }

  std::optional<int64_t> maybeSrcWriteRegionSizeBytes =
      srcWriteRegion.getRegionSize();
  if (!maybeSrcWriteRegionSizeBytes.has_value())
    return false;

and MemRefRegion::getRegionSize (in Analysis/Utils.cpp) returns no value, with the message "Dynamic shapes not yet supported", when the region does not have a constant bounding size:

std::optional<int64_t> MemRefRegion::getRegionSize() {
  auto memRefType = cast<MemRefType>(memref.getType());

  if (!memRefType.getLayout().isIdentity()) {
    LLVM_DEBUG(llvm::dbgs() << "Non-identity layout map not yet supported\n");
    return false;
  }

  // Indices to use for the DmaStart op.
  // Indices for the original memref being DMAed from/to.
  SmallVector<Value, 4> memIndices;
  // Indices for the faster buffer being DMAed into/from.
  SmallVector<Value, 4> bufIndices;

  // Compute the extents of the buffer.
  std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
  if (!numElements) {
    LLVM_DEBUG(llvm::dbgs() << "Dynamic shapes not yet supported\n");
    return std::nullopt;
  }
  auto eltSize = getMemRefIntOrFloatEltSizeInBytes(memRefType);
  if (!eltSize)
    return std::nullopt;
  return *eltSize * *numElements;

So the source offers two candidate reasons, and they predict different things. The trip-count check depends on the loops' bounds; the region-size check depends on the shape of what is accessed. Finally, how the pass reacts to a "no". At the producer-consumer call site:

            LLVM_DEBUG(llvm::dbgs() << "Skipping profitability analysis. Not "
                                       "supported for this case\n");
          else if (!isFusionProfitable(producerStores[0], producerStores[0],
                                       dstAffineForOp, depthSliceUnions,
                                       maxLegalFusionDepth, &bestDstLoopDepth,
                                       computeToleranceThreshold))
            continue;

When isFusionProfitable returns false the code does continue: skip this candidate pair, say nothing. That is exactly the silent no-op Chapter 17 saw.

Step 2: the source's own explanation is not available

Reading code tells you what the pass would say, but the message strings live inside LLVM_DEBUG(...), which is compiled out of release builds. Whether this toolchain can print them was checked rather than assumed (debug_unavailable.sh):

#!/bin/sh
# Can this toolchain tell us WHY fusion declined? LLVM_DEBUG messages are compiled out of release builds. Output: debug_unavailable_out.txt
HERE=$(cd "$(dirname "$0")" && pwd); M=${MG_OPT:-$HERE/../../part14/code/build/mg-opt}
echo '$ mlir-opt-18 --debug-only=affine-loop-fusion exp_A.mlir --affine-loop-fusion'
mlir-opt-18 --debug-only=affine-loop-fusion $HERE/exp_A.mlir --affine-loop-fusion -o /dev/null 2>&1 | head -2
echo
echo '$ strings /usr/lib/llvm-18/bin/mlir-opt | grep -c "Non-constant trip count unsupported"'
strings /usr/lib/llvm-18/bin/mlir-opt | grep -c "Non-constant trip count unsupported"
echo '$ strings /usr/lib/llvm-18/bin/mlir-opt | grep -c "Dynamic shapes not yet supported"'
strings /usr/lib/llvm-18/bin/mlir-opt | grep -c "Dynamic shapes not yet supported"
exit 0

$ mlir-opt-18 --debug-only=affine-loop-fusion exp_A.mlir --affine-loop-fusion
mlir-opt-18: Unknown command line argument '--debug-only=affine-loop-fusion'.  Try: 'mlir-opt-18 --help'
mlir-opt-18: Did you mean '--debug-pass=affine-loop-fusion'?

$ strings /usr/lib/llvm-18/bin/mlir-opt | grep -c "Non-constant trip count unsupported"
0
$ strings /usr/lib/llvm-18/bin/mlir-opt | grep -c "Dynamic shapes not yet supported"
0

--debug-only does not exist in this mlir-opt-18, and neither message string is present in the binary. So the source cannot be confirmed by asking the pass. It has to be confirmed by experiment.

Step 3: experiments that discriminate

The two hypotheses make opposite predictions about two kinds of program:

  • H1, trip counts: dynamic loop bounds over static buffers should decline; constant loop bounds over dynamic buffers should fuse (nothing non-constant for getLoopNestStats to trip on, and the region touched is still constant-sized).
  • H2, region size / dynamic memref shapes: the opposite: dynamic buffers should decline.

Chapter 17's chain varied both at once (dynamic bounds and dynamic buffers), so it could not tell them apart. The experiments below are hand-written affine programs, each an add nest feeding a transpose nest through an intermediate buffer, varying one property. The control, exp_C, is fully static:

func.func @C(%a: memref<4x6xf64>, %b: memref<4x6xf64>) -> memref<6x4xf64> {
  %s = memref.alloc() : memref<4x6xf64>
  %out = memref.alloc() : memref<6x4xf64>
  affine.for %i = 0 to 4 {
    affine.for %j = 0 to 6 {
      %x = affine.load %a[%i, %j] : memref<4x6xf64>
      %y = affine.load %b[%i, %j] : memref<4x6xf64>
      %z = arith.addf %x, %y : f64
      affine.store %z, %s[%i, %j] : memref<4x6xf64>
    }
  }
  affine.for %i = 0 to 6 {
    affine.for %j = 0 to 4 {
      %t = affine.load %s[%j, %i] : memref<4x6xf64>
      affine.store %t, %out[%i, %j] : memref<6x4xf64>
    }
  }
  return %out : memref<6x4xf64>
}

exp_A: both nests' loop bounds are function-argument symbols (%n, %m), buffers static:

func.func @A(%a: memref<4x6xf64>, %b: memref<4x6xf64>, %n: index, %m: index) -> memref<6x4xf64> {
  %s = memref.alloc() : memref<4x6xf64>
  %out = memref.alloc() : memref<6x4xf64>
  affine.for %i = 0 to %n {
    affine.for %j = 0 to %m {
      %x = affine.load %a[%i, %j] : memref<4x6xf64>
      %y = affine.load %b[%i, %j] : memref<4x6xf64>
      %z = arith.addf %x, %y : f64
      affine.store %z, %s[%i, %j] : memref<4x6xf64>
    }
  }
  affine.for %i = 0 to %m {
    affine.for %j = 0 to %n {
      %t = affine.load %s[%j, %i] : memref<4x6xf64>
      affine.store %t, %out[%i, %j] : memref<6x4xf64>
    }
  }
  return %out : memref<6x4xf64>
}

exp_B: loop bounds constant, buffers dynamic (memref<?x?xf64>, allocated from runtime sizes):

func.func @B(%a: memref<?x?xf64>, %b: memref<?x?xf64>, %n: index, %m: index) -> memref<?x?xf64> {
  %s = memref.alloc(%n, %m) : memref<?x?xf64>
  %out = memref.alloc(%m, %n) : memref<?x?xf64>
  affine.for %i = 0 to 4 {
    affine.for %j = 0 to 6 {
      %x = affine.load %a[%i, %j] : memref<?x?xf64>
      %y = affine.load %b[%i, %j] : memref<?x?xf64>
      %z = arith.addf %x, %y : f64
      affine.store %z, %s[%i, %j] : memref<?x?xf64>
    }
  }
  affine.for %i = 0 to 6 {
    affine.for %j = 0 to 4 {
      %t = affine.load %s[%j, %i] : memref<?x?xf64>
      affine.store %t, %out[%i, %j] : memref<?x?xf64>
    }
  }
  return %out : memref<?x?xf64>
}

Three more variants (exp_E, exp_F, exp_G) are generated from the control by changing exactly one loop's bound to the symbol %n: the producer's outer loop, the producer's inner loop, and the consumer's outer loop. Their exact differences from the control (exp_variants_diff.txt; note each also gains the %n parameter):

### exp_E vs the static control exp_C
1c1
< func.func @C(%a: memref<4x6xf64>, %b: memref<4x6xf64>) -> memref<6x4xf64> {
---
> func.func @C(%a: memref<4x6xf64>, %b: memref<4x6xf64>, %n: index) -> memref<6x4xf64> {
4c4
<   affine.for %i = 0 to 4 {
---
>   affine.for %i = 0 to %n {

### exp_F vs the static control exp_C
1c1
< func.func @C(%a: memref<4x6xf64>, %b: memref<4x6xf64>) -> memref<6x4xf64> {
---
> func.func @C(%a: memref<4x6xf64>, %b: memref<4x6xf64>, %n: index) -> memref<6x4xf64> {
5c5
<     affine.for %j = 0 to 6 {
---
>     affine.for %j = 0 to %n {

### exp_G vs the static control exp_C
1c1
< func.func @C(%a: memref<4x6xf64>, %b: memref<4x6xf64>) -> memref<6x4xf64> {
---
> func.func @C(%a: memref<4x6xf64>, %b: memref<4x6xf64>, %n: index) -> memref<6x4xf64> {
12c12
<   affine.for %i = 0 to 6 {
---
>   affine.for %i = 0 to %n {

The script that runs everything:

#!/bin/sh
# Chapter 18: which loop-bound property makes --affine-loop-fusion decline? Hand-written affine programs, one property varied each.
# All are an add nest feeding a transpose nest through an intermediate buffer; fusion should merge them (4 loops -> 2) when it can.
# Needs ../../part14/code/build.sh. Output: fusion_experiments_out.txt
HERE=$(cd "$(dirname "$0")" && pwd); M=${MG_OPT:-$HERE/../../part14/code/build/mg-opt}; W=$HERE/work; mkdir -p $W
nth() {  # file, pattern, replacement, n: replace the n-th occurrence of pattern in file
  python3 - "$1" "$2" "$3" "$4" <<'P'
import sys,re
f,pat,rep,n=sys.argv[1],sys.argv[2],sys.argv[3],int(sys.argv[4]); s=open(f).read(); k=0
def r(m):
    global k; k+=1; return rep if k==n else m.group(0)
open(f,'w').write(re.sub(pat,r,s))
P
}
# variants of the fully static control C that make exactly ONE loop's bound dynamic (a function-argument symbol %n)
for v in E F G; do sed 's/@C(%a: memref<4x6xf64>, %b: memref<4x6xf64>)/@C(%a: memref<4x6xf64>, %b: memref<4x6xf64>, %n: index)/' $HERE/exp_C.mlir > $W/exp_$v.mlir; done
nth $W/exp_E.mlir 'affine.for %i = 0 to 4' 'affine.for %i = 0 to %n' 1     # producer nest, OUTER loop dynamic
nth $W/exp_F.mlir 'affine.for %j = 0 to 6' 'affine.for %j = 0 to %n' 1     # producer nest, INNER loop dynamic
nth $W/exp_G.mlir 'affine.for %i = 0 to 6' 'affine.for %i = 0 to %n' 1     # CONSUMER nest, outer loop dynamic
cp $W/exp_E.mlir $HERE/exp_E.mlir; cp $W/exp_F.mlir $HERE/exp_F.mlir; cp $W/exp_G.mlir $HERE/exp_G.mlir
printf "%-4s %-64s %-7s %s\n" exp "what is dynamic" "before" "after fusion"
row() { f=$HERE/exp_$1.mlir; printf "%-4s %-64s %-7s %s\n" "$1" "$2" "$(grep -c affine.for $f)" "$($M $f --affine-loop-fusion | grep -c affine.for)"; }
row C "nothing (static bounds, static buffers) - control"
row A "BOTH nests' bounds (function-argument symbols); buffers static"
row B "the BUFFERS (memref<?x?xf64>); loop bounds constant"
row E "one loop: producer, outer"
row F "one loop: producer, inner"
row G "one loop: consumer, outer"
echo
echo "WORKAROUND ATTEMPT: tile first (constant tile size), then fuse. Static controls first."
for ts in 1 2; do
  $M $HERE/../../part17/code/static_chain.mlir --convert-mg-to-affine | $M --affine-loop-tile="tile-size=$ts" -o $W/I_t$ts.mlir
  if $M $W/I_t$ts.mlir --affine-loop-fusion -o $W/I_f$ts.mlir 2>$W/I_f$ts.err; then r="verifies, $(grep -c affine.for $W/I_f$ts.mlir) loops"; else r="VERIFIER ERROR: $(head -1 $W/I_f$ts.err | sed 's/^[^ ]* //')"; fi
  printf "I%s   STATIC 4x6 chain, tiled by %s (%s loops) then fused: %s\n" $ts $ts "$(grep -c affine.for $W/I_t$ts.mlir)" "$r"
done
$M $HERE/../../part17/code/chain.mlir --convert-mg-to-affine -o $W/H_affine.mlir
$M $W/H_affine.mlir --affine-loop-tile="tile-size=4" -o $W/H_tiled.mlir
if $M $W/H_tiled.mlir --affine-loop-fusion -o $W/H_fused.mlir 2>$W/H_fused.err; then r="verifies, $(grep -c affine.for $W/H_fused.mlir) loops"; else r="VERIFIER ERROR: $(head -1 $W/H_fused.err | sed 's/^[^ ]* //')"; fi
printf "H    DYNAMIC chain, tiled by 4 (%s loops) then fused: %s\n" "$(grep -c affine.for $W/H_tiled.mlir)" "$r"
echo
echo "What the fusion pass did to the tiled dynamic nest (verification off, generic form), first loop-header lines that differ:"
$M $W/H_tiled.mlir -mlir-print-op-generic -o $W/H_tiled_generic.mlir
$M $W/H_tiled.mlir --affine-loop-fusion --verify-each=0 -mlir-print-op-generic -o $W/H_fused_generic.mlir 2>/dev/null
diff $W/H_tiled_generic.mlir $W/H_fused_generic.mlir | grep -E '^[<>].*"affine.for"' | sed -E 's/<\{lowerBoundMap = #map1, //; s/\}> \(\{$//' | cut -c1-150
for v in E F G; do echo "### exp_$v vs the static control exp_C"; diff $HERE/exp_C.mlir $HERE/exp_$v.mlir; echo; done > $HERE/exp_variants_diff.txt

Results

The first part of the real output (fusion_experiments_out.txt): loops before and after --affine-loop-fusion, where a successful fusion of these programs takes 4 loops to 2.

exp  what is dynamic                                                  before  after fusion
C    nothing (static bounds, static buffers) - control                4       2
A    BOTH nests' bounds (function-argument symbols); buffers static   4       4
B    the BUFFERS (memref<?x?xf64>); loop bounds constant              4       2
E    one loop: producer, outer                                        4       4
F    one loop: producer, inner                                        4       4
G    one loop: consumer, outer                                        4       4
  • C (control): fuses, 4 to 2. The programs are fusable in principle.
  • A (dynamic bounds, static buffers): declines. H1 predicted this; H2 did not.
  • B (constant bounds, dynamic buffers): fuses. This is the discriminating result. If dynamic buffer shapes were the blocker (H2), B would decline. It does not, because the region accessed is still constant-sized (the loops touch a fixed 4x6 block), so the getRegionSize check passes even though the memref type is dynamic.
  • E, F, G: declining with only one dynamic loop anywhere (producer outer, producer inner, consumer outer). That matches getLoopNestStats walking every loop of both nests and giving up at the first non-constant one.

What this establishes, and what it does not

Established (source reading plus six experiments that agree with it and exclude the alternative): this toolchain's --affine-loop-fusion needs every affine.for in both the producer and the consumer nest to have a constant trip count. Dynamic buffer shapes alone do not prevent fusion. When the rule fails the pass declines silently, via continue.

Not established, stated plainly:

  • The second exit was never isolated. getRegionSize's "Dynamic shapes not yet supported" check exists, but every program that could reach it with a non-constant region already failed the trip-count check first (a region cannot be unbounded unless a loop bound is dynamic). Whether that message can fire by itself was not demonstrated.
  • getConstantTripCount's definition was not read. Its behavior is inferred from the experiments (constant bounds yield a count; function-argument symbols do not), not from its code. Whether a bound like min(...) ever counts as constant was not tested here.
  • The sibling-fusion path (the other call to isFusionProfitable, near line 1187) calls the same function and presumably obeys the same rule, but no sibling-fusion program was tried.

This explains a fact Chapter 17 recorded but could not explain, and it makes a prediction that is easy to falsify (a toolchain that relaxes the rule would fuse the dynamic programs). The test below pins it.

A workaround attempt that found a bug

An obvious idea: if the problem is non-constant trip counts, give the pass constant ones by tiling first with a constant tile size, then fuse. The tile loops step by a constant, so perhaps the pass will see something it likes. It does not work, and failing in an unexpected way. The second half of the output records it, with static controls:

WORKAROUND ATTEMPT: tile first (constant tile size), then fuse. Static controls first.
I1   STATIC 4x6 chain, tiled by 1 (8 loops) then fused: verifies, 4 loops
I2   STATIC 4x6 chain, tiled by 2 (8 loops) then fused: verifies, 8 loops
H    DYNAMIC chain, tiled by 4 (8 loops) then fused: VERIFIER ERROR: error: operand #0 does not dominate this use
  • On the static chain, tiling by 1 and then fusing works (8 loops down to 4) and tiling by 2 then fusing leaves the loops alone (8), both with valid IR.
  • On the dynamic chain, tiling by 4 and then fusing does not decline. The pass changes the IR and the result fails verification: operand #0 does not dominate this use.

That last case is a different kind of failure from everything above: not "does nothing" but "produces invalid IR". To see what the pass did, verification was turned off (--verify-each=0) and both versions were printed in MLIR's generic form so only real changes show. The loop-header lines that differ (< before fusion, > after, again from fusion_experiments_out.txt):

What the fusion pass did to the tiled dynamic nest (verification off, generic form), first loop-header lines that differ:
<     "affine.for"(%15, %11) operandSegmentSizes = array<i32: 1, 1, 0>, step = 4 : index, upperBoundMap = #map1
>     "affine.for"(%arg4, %11, %arg4) operandSegmentSizes = array<i32: 1, 2, 0>, step = 1 : index, upperBoundMap = #map2
<       "affine.for"(%15, %13) operandSegmentSizes = array<i32: 1, 1, 0>, step = 4 : index, upperBoundMap = #map1
>       "affine.for"(%arg5, %13, %arg5) operandSegmentSizes = array<i32: 1, 2, 0>, step = 1 : index, upperBoundMap = #map2
<         "affine.for"(%arg2, %11, %arg2) operandSegmentSizes = array<i32: 1, 2, 0>, step = 1 : index, upperBoundMap = #map2
>         "affine.for"(%15, %11) operandSegmentSizes = array<i32: 1, 1, 0>, step = 4 : index, upperBoundMap = #map1
<           "affine.for"(%arg3, %13, %arg3) operandSegmentSizes = array<i32: 1, 2, 0>, step = 1 : index, upperBoundMap = #map2
>           "affine.for"(%15, %13) operandSegmentSizes = array<i32: 1, 1, 0>, step = 4 : index, upperBoundMap = #map1
<     "affine.for"(%21, %17) operandSegmentSizes = array<i32: 1, 1, 0>, step = 4 : index, upperBoundMap = #map1
>     "affine.for"(%arg4, %17, %arg4) operandSegmentSizes = array<i32: 1, 2, 0>, step = 1 : index, upperBoundMap = #map2
<       "affine.for"(%21, %19) operandSegmentSizes = array<i32: 1, 1, 0>, step = 4 : index, upperBoundMap = #map1
>       "affine.for"(%arg5, %19, %arg5) operandSegmentSizes = array<i32: 1, 2, 0>, step = 1 : index, upperBoundMap = #map2
<         "affine.for"(%arg2, %17, %arg2) operandSegmentSizes = array<i32: 1, 2, 0>, step = 1 : index, upperBoundMap = #map2
>         "affine.for"(%21, %17) operandSegmentSizes = array<i32: 1, 1, 0>, step = 4 : index, upperBoundMap = #map1
<           "affine.for"(%arg3, %19, %arg3) operandSegmentSizes = array<i32: 1, 2, 0>, step = 1 : index, upperBoundMap = #map2
>           "affine.for"(%21, %19) operandSegmentSizes = array<i32: 1, 1, 0>, step = 4 : index, upperBoundMap = #map1

Read the step fields. Before, the nest is tile loops (step = 4) outermost, then point loops (step = 1, whose bounds mention the tile loops' induction variables, e.g. (%arg4, %11, %arg4)). After, the nest order is reversed: the step = 1 loops are outermost and the step = 4 loops innermost, in both nests. The point loops' bounds still reference the tile loops' induction variables (%arg4, %arg5), which are now defined inside them, so they no longer dominate their use. That is the verifier's complaint.

Where it happens in the source

The pass interchanges loops before it even considers profitability. At the start of its per-destination-nest work (LoopFusion.cpp):

    if (dstNode->op->getNumResults() > 0)
      return;

    LLVM_DEBUG(llvm::dbgs() << "Evaluating dst loop " << dstId << "\n");

    // Sink sequential loops in 'dstNode' (and thus raise parallel loops)
    // while preserving relative order. This can increase the maximum loop
    // depth at which we can fuse a slice of a producer loop nest into a
    // consumer loop nest.
    sinkSequentialLoops(dstNode);

sinkSequentialLoops(dstNode) runs for every destination loop nest, whether or not any fusion will follow. Its definition (LoopUtils.cpp):

// Sinks all sequential loops to the innermost levels (while preserving
// relative order among them) and moves all parallel loops to the
// outermost (while again preserving relative order among them).
AffineForOp mlir::affine::sinkSequentialLoops(AffineForOp forOp) {
  SmallVector<AffineForOp, 4> loops;
  getPerfectlyNestedLoops(loops, forOp);
  if (loops.size() < 2)
    return forOp;

  // Gather dependence components for dependences between all ops in loop nest
  // rooted at 'loops[0]', at loop depths in range [1, maxLoopDepth].
  unsigned maxLoopDepth = loops.size();
  std::vector<SmallVector<DependenceComponent, 2>> depCompsVec;
  getDependenceComponents(loops[0], maxLoopDepth, &depCompsVec);

  // Mark loops as either parallel or sequential.
  SmallVector<bool, 8> isParallelLoop(maxLoopDepth, true);
  for (auto &depComps : depCompsVec) {
    assert(depComps.size() >= maxLoopDepth);
    for (unsigned j = 0; j < maxLoopDepth; ++j) {
      DependenceComponent &depComp = depComps[j];
      assert(depComp.lb.has_value() && depComp.ub.has_value());
      if (*depComp.lb != 0 || *depComp.ub != 0)
        isParallelLoop[j] = false;
    }
  }

  unsigned numParallelLoops = llvm::count(isParallelLoop, true);

  // Compute permutation of loops that sinks sequential loops (and thus raises
  // parallel loops) while preserving relative order.
  SmallVector<unsigned, 4> loopPermMap(maxLoopDepth);
  unsigned nextSequentialLoop = numParallelLoops;
  unsigned nextParallelLoop = 0;
  for (unsigned i = 0; i < maxLoopDepth; ++i) {
    if (isParallelLoop[i]) {
      loopPermMap[i] = nextParallelLoop++;
    } else {
      loopPermMap[i] = nextSequentialLoop++;
    }
  }

  // Check if permutation 'loopPermMap' would violate dependences.
  if (!checkLoopInterchangeDependences(depCompsVec, loops, loopPermMap))
    return forOp;
  // Perform loop interchange according to permutation 'loopPermMap'.
  unsigned loopNestRootIndex = permuteLoops(loops, loopPermMap);
  return loops[loopNestRootIndex];

The steps: collect the perfectly nested loops; compute dependence components between the ops; mark a loop sequential if any dependence component has a nonzero bound; compute a permutation that moves sequential loops inward and parallel loops outward; check only data dependences (checkLoopInterchangeDependences); then call permuteLoops. The head of permuteLoops:

// input[i] should move from position i -> permMap[i]. Returns the position in
// `input` that becomes the new outermost loop.
unsigned mlir::affine::permuteLoops(MutableArrayRef<AffineForOp> input,
                                    ArrayRef<unsigned> permMap) {
  assert(input.size() == permMap.size() && "invalid permutation map size");
  // Check whether the permutation spec is valid. This is a small vector - we'll
  // just sort and check if it's iota.
  SmallVector<unsigned, 4> checkPermMap(permMap.begin(), permMap.end());
  llvm::sort(checkPermMap);
  if (llvm::any_of(llvm::enumerate(checkPermMap),
                   [](const auto &en) { return en.value() != en.index(); }))
    assert(false && "invalid permutation map");

  // Nothing to do.
  if (input.size() < 2)
    return 0;

  assert(isPerfectlyNested(input) && "input not perfectly nested");

  // Compute the inverse mapping, invPermMap: since input[i] goes to position
  // permMap[i], position i of the permuted nest is at input[invPermMap[i]].
  SmallVector<std::pair<unsigned, unsigned>, 4> invPermMap;
  for (unsigned i = 0, e = input.size(); i < e; ++i)
    invPermMap.push_back({permMap[i], i});
  llvm::sort(invPermMap);

  // Move the innermost loop body to the loop that would be the innermost in the

validates that the permutation is a permutation and that the loops are perfectly nested. In the lines read, nothing checks whether a loop's bounds use an enclosing loop's induction variable. That is exactly the structure of a tiled nest, so a permutation that moves the tile loops inward yields invalid IR.

What this explains, and what it does not:

  • Consistent with the evidence: the observed permutation (tile loops moved inward) is the output of this function; it runs before profitability; and the only legality check visible before the permutation concerns data dependences.
  • Inferred, not demonstrated: why the tile loops are judged sequential on the dynamic nest but not on the static one. The natural reading is that dependence analysis with symbolic bounds cannot prove independence and reports nonzero components, while with constant bounds it can. The pass's dependence results were not printed (debug output is compiled out), so this is a hypothesis.
  • Not read in full: checkLoopInterchangeDependences and the body of permuteLoops beyond its head. The claim is only that no bound check appears in the lines shown here, not that none exists anywhere.

What this means for Mountain Goat's pipeline

  • Fusion cannot help dynamic shapes in this toolchain. Every nest in a dynamic mg program has non-constant trip counts, so fusion declines. Chapter 7's fusion benefit exists only for static shapes.
  • Order matters: never tile and then fuse dynamic loops. Chapter 7's own order (fusion, then tiling, then unrolling) is safe because fusion runs first. The reversed order breaks on dynamic bounds with this LLVM version.
  • Not tried: specializing a dynamic program into static copies for common sizes (which would let fusion apply), or checking whether a newer LLVM relaxes either behavior.

The tests, and whether they can fail

Two tests pin this chapter's findings. The first pins the rule (the constant-trip-count requirement) with the six programs above, three that must fuse and declining ones where each single dynamic loop blocks it:

// Chapter 18: the RULE behind Chapter 17's "fusion declines on dynamic bounds", found by reading LoopFusion.cpp and testing it:
// --affine-loop-fusion needs every loop in both nests to have a CONSTANT trip count. Dynamic BUFFERS do not matter (B fuses);
// a dynamic bound on ANY single loop (A: all of them; E, F: producer outer/inner; G: consumer) makes it decline silently.
// Pinned for this toolchain version only: if a newer LLVM relaxes the rule, the DECLINES runs fail, which is the signal to revisit Chapter 18.
// RUN: %mg-opt %inputs/exp_C.mlir --affine-loop-fusion | %FileCheck %s --check-prefix=FUSES
// RUN: %mg-opt %inputs/exp_B.mlir --affine-loop-fusion | %FileCheck %s --check-prefix=FUSES
// RUN: %mg-opt %inputs/exp_A.mlir --affine-loop-fusion | %FileCheck %s --check-prefix=DECLINES
// RUN: %mg-opt %inputs/exp_E.mlir --affine-loop-fusion | %FileCheck %s --check-prefix=DECLINES
// RUN: %mg-opt %inputs/exp_F.mlir --affine-loop-fusion | %FileCheck %s --check-prefix=DECLINES
// RUN: %mg-opt %inputs/exp_G.mlir --affine-loop-fusion | %FileCheck %s --check-prefix=DECLINES
// FUSES-COUNT-2: affine.for
// FUSES-NOT: affine.for
// DECLINES-COUNT-4: affine.for
// DECLINES-NOT: affine.for

The second pins the bug, with the static controls that show the failure needs dynamic bounds. Its header says it is designed to start failing: if a newer LLVM fixes the interchange, the dynamic run will stop producing an error, and that is the signal to revisit this chapter:

// Chapter 18: PINS A TOOLCHAIN BUG (LLVM 18.1.3). Running --affine-loop-fusion on a TILED nest with dynamic bounds produces INVALID IR:
// the pass's sinkSequentialLoops step swaps the tile loops inward past the point loops whose bounds use the tile induction variables.
// The same pass on a tiled STATIC nest is fine. If a newer LLVM fixes this, the DYN run fails: that is the signal to revisit Chapter 18.
// RUN: %mg-opt %inputs/chain.mlir --convert-mg-to-affine | %mg-opt --affine-loop-tile="tile-size=4" -o %t.dyn.mlir
// RUN: %not %mg-opt %t.dyn.mlir --affine-loop-fusion 2>&1 | %FileCheck %s --check-prefix=DYN
// RUN: %mg-opt %inputs/static_chain.mlir --convert-mg-to-affine | %mg-opt --affine-loop-tile="tile-size=1" | %mg-opt --affine-loop-fusion | %FileCheck %s --check-prefix=STATIC1
// RUN: %mg-opt %inputs/static_chain.mlir --convert-mg-to-affine | %mg-opt --affine-loop-tile="tile-size=2" | %mg-opt --affine-loop-fusion | %FileCheck %s --check-prefix=STATIC2
// DYN: error: operand #0 does not dominate this use
// STATIC1-COUNT-4: affine.for
// STATIC1-NOT: affine.for
// STATIC2-COUNT-8: affine.for
// STATIC2-NOT: affine.for

The suite is now 44 tests (run_out_44.txt):

-- Testing: 44 tests, 4 workers --
PASS: IR Forge / Mountain Goat :: execution/mismatch-columns-aborts.mlir (1 of 44)
PASS: IR Forge / Mountain Goat :: execution/dynamic-shapes-run.mlir (2 of 44)
PASS: IR Forge / Mountain Goat :: execution/mismatch-aborts.mlir (3 of 44)
PASS: IR Forge / Mountain Goat :: execution/gpu-host-with-stub-runtime.mlir (4 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/tiling-runs.mlir (5 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-runs.mlir (6 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/runtime-check-survives-transforms.mlir (7 of 44)
PASS: IR Forge / Mountain Goat :: execution/static-add-runs.mlir (8 of 44)
PASS: IR Forge / Mountain Goat :: execution/mixed-static-dynamic.mlir (9 of 44)
PASS: IR Forge / Mountain Goat :: execution/strided-view.mlir (10 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-needs-constant-trip-counts.mlir (11 of 44)
PASS: IR Forge / Mountain Goat :: gpu/pass-order-crash.mlir (12 of 44)
PASS: IR Forge / Mountain Goat :: gpu/ptx-default.mlir (13 of 44)
PASS: IR Forge / Mountain Goat :: gpu/ptx-bare-pointers.mlir (14 of 44)
PASS: IR Forge / Mountain Goat :: gpu/host-runtime-calls-bare.mlir (15 of 44)
PASS: IR Forge / Mountain Goat :: gpu/ptx-index32.mlir (16 of 44)
PASS: IR Forge / Mountain Goat :: gpu/host-runtime-calls.mlir (17 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-fires-when-static.mlir (18 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-full-needs-constant-trip-count.mlir (19 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-declines.mlir (20 of 44)
PASS: IR Forge / Mountain Goat :: gpu/nvvm-lowering.mlir (21 of 44)
PASS: IR Forge / Mountain Goat :: gpu/kernel-outlining.mlir (22 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/tiling-structure.mlir (23 of 44)
PASS: IR Forge / Mountain Goat :: lowering/static-add-affine.mlir (24 of 44)
PASS: IR Forge / Mountain Goat :: verifier/unranked-rejected.mlir (25 of 44)
PASS: IR Forge / Mountain Goat :: canonicalize/fold-constant-add.mlir (26 of 44)
PASS: IR Forge / Mountain Goat :: gpu/cuda-comparison.mlir (27 of 44)
PASS: IR Forge / Mountain Goat :: loops/tiling.mlir (28 of 44)
PASS: IR Forge / Mountain Goat :: loops/unroll-full.mlir (29 of 44)
PASS: IR Forge / Mountain Goat :: verifier/transpose-rank3.mlir (30 of 44)
PASS: IR Forge / Mountain Goat :: lowering/mixed-add-one-check.mlir (31 of 44)
PASS: IR Forge / Mountain Goat :: loops/fusion.mlir (32 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/unroll-epilogue.mlir (33 of 44)
PASS: IR Forge / Mountain Goat :: lowering/dynamic-add-affine.mlir (34 of 44)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice-dynamic-mixed.mlir (35 of 44)
PASS: IR Forge / Mountain Goat :: verifier/add-static-mismatch.mlir (36 of 44)
PASS: IR Forge / Mountain Goat :: lowering/bufferize-dynamic-add.mlir (37 of 44)
PASS: IR Forge / Mountain Goat :: lowering/dynamic-transpose-no-check.mlir (38 of 44)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice-dynamic-exact.mlir (39 of 44)
PASS: IR Forge / Mountain Goat :: canonicalize/transpose-twice.mlir (40 of 44)
PASS: IR Forge / Mountain Goat :: verifier/transpose-bad-shape.mlir (41 of 44)
PASS: IR Forge / Mountain Goat :: lowering/bufferize-static-add.mlir (42 of 44)
PASS: IR Forge / Mountain Goat :: verifier/dynamic-accepted.mlir (43 of 44)
PASS: IR Forge / Mountain Goat :: dynamic-loops/fusion-after-tiling.mlir (44 of 44)

Testing Time: 1.02s

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

Five new mutations were added to the Chapter 17 failure-injection script, three for the rule test and two for the bug-pin test, and all were caught (the complete output):

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

Mutations 7 to 9 feed a "must decline" run a program that fuses (or a "must fuse" run a program that declines), so the rule test fails exactly when the rule stops holding; 10 feeds the "must error" run a static program that verifies; 11 changes the static control's tile size so its loop count is wrong.

What this does and does not establish

  • One LLVM version. All of it describes llvmorg-18.1.3; the source read and the binary run are the same release. Newer versions may differ.
  • Fusion was examined only for this producer-consumer shape. Sibling fusion, other op mixes and other loop counts were not.
  • The invalid-IR finding is a symptom and a located cause, not a root-cause analysis. The inferred link (dependence analysis marks tile loops sequential on dynamic bounds) is a hypothesis, and the bug was not reported upstream or tested against other versions.
  • No performance claims. Nothing here was timed.
  • 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/part18/code
./debug_unavailable.sh > debug_unavailable_out.txt
./fusion_experiments.sh > fusion_experiments_out.txt
cd ../part15/code
./run_lit.sh > run_out_44.txt
./dynloops_mutation.sh > dynloops_mutation_out.txt

The LLVM source in code/llvm-18.1.3/ was read from llvm/llvm-project at tag llvmorg-18.1.3 (provenance and license in its NOTICE.md); every quoted line is embedded from those unmodified copies. As in Chapters 10 through 17, no documentation was consulted: each claim comes from running the commands or reading the source.

Chapter summary

This chapter explained Chapter 17's unexplained limitation. Reading the LLVM 18.1.3 source showed that --affine-loop-fusion's profitability analysis collects trip counts for both loop nests and declines the moment any loop has a non-constant one (getLoopNestStats: "Currently only constant trip count loop nests are supported"), and that a decline is a silent continue. The source also contains a second candidate reason (dynamic region sizes). Experiments designed to tell them apart showed that constant-bound loops over dynamic buffers fuse while a dynamic bound on any single loop, anywhere, declines. So trip counts, not buffer shapes, are the blocker. Testing the obvious workaround (tile by a constant, then fuse) exposed a second problem: on tiled dynamic loops the pass interchanges loops through sinkSequentialLoops without checking that loop bounds survive the move, producing invalid IR, while static tiled loops are fine. Two lit tests pin the rule and the bug (suite: 44), and eleven mutations were all caught.

Deliberately out of scope, stated explicitly: only one LLVM version and one producer-consumer shape; the getRegionSize exit was never isolated; getConstantTripCount and most of permuteLoops were not read; the reason tile loops are judged sequential on dynamic nests is an inference; the bug was not reported upstream; and specializing to static sizes was not tried.

Self-check questions

1. Chapter 17's chain had both dynamic loop bounds and dynamic buffers. Why could it not distinguish the two candidate reasons for fusion declining, and what experiment did?

Worked answer: because both properties were present at once, either explanation predicted a decline. The source offered two reasons: a non-constant trip count (getLoopNestStats) and a non-constant region size (getRegionSize). Experiment B separated them: constant loop bounds over dynamic buffers. If dynamic buffer shapes were the blocker it would decline; it fused (4 loops to 2), because the region those loops access is a fixed 4x6 block. Experiment A, dynamic bounds over static buffers, declined, so the trip counts are what matter.

2. Why did the chapter try to read the pass's own debug explanation, and why could it not?

Worked answer: the pass logs its reason for declining, so asking it would be the most direct confirmation. But the messages are inside LLVM_DEBUG(...), which is compiled out of release builds: mlir-opt-18 has no --debug-only option, and neither message string appears in the binary (strings finds zero occurrences of each). So the source was read for the hypothesis and the experiments were used to confirm it.

3. Experiments E, F and G each make a single loop dynamic. What does it show that all three decline?

Worked answer: it shows the rule is not "the outer loops" or "the producer" but any loop in either nest. That matches getLoopNestStats, which walks every affine.for in a nest and interrupts at the first non-constant trip count, and which isFusionProfitable calls for both the producer and the consumer. A dynamic bound on the producer's outer loop, the producer's inner loop or the consumer's outer loop each triggers it.

4. Tiling by a constant and then fusing did not simply fail to help. What actually happened, and what do the static controls show?

Worked answer: on the dynamic chain the pass changed the IR and the result failed verification (operand #0 does not dominate this use). Printed in generic form, the nest order was reversed: the step = 1 point loops moved outermost and the step = 4 tile loops innermost, in both nests, so the point loops' bounds referred to tile induction variables now defined inside them. The static controls (tile by 1 then fuse gives 4 loops, tile by 2 then fuse leaves 8) verify, so the failure needs dynamic bounds.

5. The invalid IR is attributed to sinkSequentialLoops. What in the source supports that, and what is only inferred?

Worked answer: the pass calls sinkSequentialLoops(dstNode) on every destination loop nest before any profitability decision; the function labels loops sequential from dependence components, computes a permutation moving sequential loops inward, checks only data dependences, and calls permuteLoops, whose visible head checks only that the map is a valid permutation and the loops are perfectly nested. The observed output is exactly that permutation. What is only inferred is why the tile loops are judged sequential on the dynamic nest but not the static one (the dependence results could not be printed), and the claim that no bound check exists is limited to the lines read.