Skip to content

39. Finding the Quadratic: a Differential Profile of the Lowering Pass

Mountain goats in space helmets on Triton, a moon of Neptune

What you will understand: how to find why a program is slow when timing alone says only that it is, using a differential profile: run the same code at several sizes under a profiler that counts instructions and see which function's cost grows faster than the rest. Chapter 38 measured that MLIR's SCFToControlFlow pass is super-linear in the number of loops in one function and fixed it by outlining, but said "the mechanism inside MLIR was not identified". This chapter identifies it: one function, ilist_traits<Operation>::transferNodesFromList, called by Block::splitBlock, whose instruction count is exactly quadratic (×3.98, ×3.99, ×4.00 per doubling) while everything else is linear. There is no compiler change in this chapter.

What you need to know first: Chapter 38 (the problem, the synthetic experiment, the fix). The tools are valgrind --tool=callgrind and callgrind_annotate; the chapter explains what they report.

Compile and run

cd docs/part38/code && ./build.sh                 # once: the compiler (this chapter adds nothing to it)
cd ../../part39/code
./profile_scf.py > profile_out.txt                # the differential profile (about 2.5 minutes)
./check_profile.py > check_profile_out.txt        # the claims, as checks on exact instruction counts (about 45 seconds)
./claims_mutation.py > claims_mutation_out.txt    # three WRONG inputs the checker must catch (about 3 minutes)
cd ../../part15/code && ./run_lit.sh              # the whole test suite
Needs valgrind (it provides callgrind and callgrind_annotate); CI now installs it. Every output on this page comes from these commands.

Why this page shows a mutation run, and why 'caught' is the wanted result

claims_mutation.py feeds the checker deliberately wrong inputs; "caught" is the wanted result and "NOT CAUGHT" would be a gap.

The method: count instructions, not seconds

A stopwatch gives one number per run and is noisy. callgrind runs the program on a simulated CPU and counts the instructions executed in every function, exactly and repeatably. If a program is linear except for one quadratic part, then running it at n, 2n, 4n, 8n and comparing each function's count between runs shows the culprit: linear functions grow ×2 per doubling, the quadratic one ×4. The program is Chapter 38's synthetic one: n tiny loop nests (each copies four numbers) in one function, lowered with mg-opt --lower-affine --convert-scf-to-cf (the two passes the slow stage runs for loops).

Part 1: which function is quadratic?

PART 1. callgrind instruction counts (millions) for --lower-affine --convert-scf-to-cf on n loop nests in ONE function
     n  all functions  growth  transferNodesFromList  growth
  1000          352.0                            8.1        
  2000          695.7   x1.98                   32.1   x3.98
  4000         1430.4   x2.06                  128.3   x3.99
  8000         3091.5   x2.16                  512.5   x4.00

the functions that account for the growth from n = 2000 to n = 8000 (millions of instructions at 2000, at 8000, ratio; 4x the loops: ratio 4 = linear, 16 = quadratic)
     32.1      512.5  x 15.9  llvm::ilist_traits<mlir::Operation>::transferNodesFromList(llvm::ilist_traits<mlir::Operation>&, llvm::ilist_i
     24.1       94.7  x  3.9  std::pair<llvm::DenseMapIterator<llvm::PointerUnion<mlir::Operation*, mlir::Block*>, llvm::detail::DenseSetEmp
     20.1       80.7  x  4.0  mlir::detail::StorageUniquerImpl::getOrCreate(mlir::TypeID, unsigned int, llvm::function_ref<bool (mlir::Stora
     16.2       64.6  x  4.0  std::pair<llvm::detail::DenseSetImpl<(anonymous namespace)::ParametricStorageUniquer::HashedStorage, llvm::Den
     15.2       60.8  x  4.0  (anonymous namespace)::OperationVerifier::verifyOpAndDominance(mlir::Operation&)
     12.7       48.3  x  3.8  ./malloc/./malloc/malloc.c:_int_malloc
  • The whole program's instruction count grows ×1.98, ×2.06, ×2.16 per doubling: about linear.
  • transferNodesFromList's count grows ×3.98, ×3.99, ×4.00: exactly quadratic, from 8.1 million instructions at 1,000 loops to 512 million at 8,000.
  • Compare the functions that account for the growth from n = 2,000 to 8,000 (the second table): transferNodesFromList multiplies by 15.9 (4 × 4: quadratic); the five next functions (a hash-map lookup, type uniquing, the verifier, malloc) multiply by 3.8 to 4.0: linear.

Part 2: who calls it, and why it is slow

PART 2. who calls it, and the cache misses (callgrind --cache-sim=yes, n = 6000)
columns: instructions, L1 read misses, L1 write misses (each with its share of the whole program)
its caller (Block::splitBlock): 288,480,000 (13.00%) 17,985,138 (63.30%) 71,993,324 (97.54%) < ???:mlir::Block::splitBlock(llvm::ilist_iterator<llvm::ilist_detail::node_options<mlir:
the function itself:           288,408,032 (13.00%) 17,985,138 (63.30%) 71,993,324 (97.54%) * ???:llvm::ilist_traits<mlir::Operation>::transferNodesFromList(llvm::ilist_traits<mlir:
program totals: 2,219,248,260 (100.0%) 28,412,768 (100.0%) 73,809,483 (100.0%) PROGRAM TOTALS

(The columns are instructions, simulated L1 data-cache read misses, and L1 write misses, each with its share of the program total, for n = 6,000 under --cache-sim=yes; the first line is the caller.) The function is called by mlir::Block::splitBlock, and:

  • it executes 13.0% of all instructions,
  • but causes 63.3% of the L1 read misses and 97.5% of the L1 write misses of the whole program.

Block::splitBlock(it) cuts a block in two at an operation and moves every operation from it to the end of the block into a new block. transferNodesFromList is the linked-list move: it walks the moved operations and rewrites each one's pointer to its parent block. SCFToControlFlow lowers each scf.for by splitting the block at the loop (the code after the loop must become the block that follows it). In a function that is one long run of loops, the loop at position i has the other n − i nests behind it, so splitting at it moves all of them. The total number of operations moved is about n²/2 times the operations per nest, which is exactly the quadratic count above. Each move touches memory at every operation (a write per node), which is why this one function dominates the cache misses even though it is only 13% of the instructions.

This also explains Chapter 38's puzzle that the time grew by ×9 per doubling at first while the instruction count of the whole program grew by about ×2: the quadratic part is a pointer-chasing loop that misses the cache, so each of its instructions costs much more than an average one. (That the wall-clock factors were then 9.0, 9.7, 4.8 and 3.6 and not a steady ×4 is not explained by this profile; a change of cost per instruction as the working set outgrows the caches is a candidate that was not tested.)

Part 3: and after outlining?

PART 3. the same function after --mg-outline-loops (Chapter 38): instruction counts at n = 2000 and 8000
n = 2000: all functions 483.7 million, transferNodesFromList 0.00 million, Block::splitBlock present: False
n = 8000: all functions 1860.5 million, transferNodesFromList 0.00 million, Block::splitBlock present: False

With Chapter 38's --mg-outline-loops run first, transferNodesFromList and splitBlock are not in the profile at all: the one function holds a list of calls, not loops, so there is nothing for SCFToControlFlow to split. The whole program is linear (484 million instructions at 2,000 loops, 1,861 million at 8,000: ×3.85 for ×4). The same loops spread over functions of 100 give ×2.0 per doubling in the check below. Chapter 38 showed that splitting the function fixes the time; this shows why: each function's block is small, so each split moves few operations.

Tests

One new lit file, test/profile39/claims.mlir (the suite is now 150 tests). check_profile.py runs callgrind on mg-opt at n = 250, 500 and 1,000 and checks, from exact instruction counts (so it is not a timing test and not flaky):

  ok   one function: transferNodesFromList grows x3.93 and x3.97 per doubling (4 = quadratic)
  ok   one function: the whole program grows x1.77 and x1.88 per doubling (about linear)
  ok   transferNodesFromList is called by Block::splitBlock
  ok   functions of 100 loops: transferNodesFromList grows x2.20 and x2.00 per doubling (2 = linear)
  ok   after --mg-outline-loops: no transferNodesFromList and no splitBlock in the profile (n = 500, 1000)
all checks pass
  1. in one function transferNodesFromList grows by 3.9 to 4.1 per doubling while the whole program grows by less than 2.3;
  2. it is called by Block::splitBlock;
  3. with the same loops in functions of 100, it grows by less than 2.3 per doubling (here ×2.20 and ×2.00: linear);
  4. after --mg-outline-loops neither function is in the profile.

CI now installs valgrind (the build step of ci.yml and the tool list of ci.sh).

Are the checks good enough? Three wrong inputs.

NOTE: this script deliberately breaks inputs. 'caught' lines are EXPECTED: they show each check can fail.
baseline (nothing broken): checker passes (expected)
the 'functions of 100' case is really one function (CHK_PER=100000): caught by 1 failing check(s):
      functions of 100000 loops: transferNodesFromList grows x3.93 and x3.97 per doubling (2 = linear)
the outlining pass is replaced by canonicalize (a pass that does not outline): caught by 1 failing check(s):
      after --canonicalize: no transferNodesFromList and no splitBlock in the profile (n = 500, 1000)
the profile is of --lower-affine only, without SCFToControlFlow (the pass under study): caught by 2 failing check(s):
      one function: transferNodesFromList grows x0.00 and x0.00 per doubling (4 = quadratic)
      transferNodesFromList is called by Block::splitBlock

All three are caught, each by the claim that depends on the broken input: the "functions of 100" case secretly made one function fails the linear claim (×3.93, ×3.97); a pass that does not outline (--canonicalize) in place of --mg-outline-loops fails the "after outlining" claim; and profiling --lower-affine alone, without the pass under study, fails the quadratic and the caller claims (the function never runs: ×0.00). (The third case first crashed the checker with a division by zero instead of failing a claim; the checker now guards the division, and the output above is from the repaired one.)

The full suite:

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

Testing Time: 105.88s

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

Limits and what is not established

  • This is MLIR 18.1.3's SCFToControlFlow. Another version may split blocks differently; this was not checked.
  • The profile identifies the function and its caller, not the exact line. The link between "splitting moves the tail of the block" and the quadratic count is established by the function names, the exact ×4 growth, and the absence of the function after outlining, but the pass's source was not read and no alternative explanation was excluded by experiment (for example by patching MLIR).
  • The wall-clock explanation is partial. The cache-miss share (63% and 97.5%) fits the observation that time grew faster than instructions; a timing experiment that isolates it (for example the same count of moved operations laid out contiguously) was not done, and the later wall-clock factors (4.8, 3.6) are unexplained.
  • A fix inside MLIR was not tried. Lowering the loops from the last to the first would make each split move a short tail; that is an idea suggested by the mechanism, not something tested here. Chapter 38's outlining avoids the problem in the compiler this book builds.
  • The synthetic function is far simpler than the training program. Its loops copy four numbers; the check is on instruction counts and mechanism, not on the training program's absolute time.
  • Only the lowering passes were profiled, not clang or mlir-translate, which Chapter 38 showed to be linear.
  • Platform: x86-64 Linux, valgrind 3.22, LLVM/MLIR 18.1.3.

Reproducing

cd docs/part38/code && ./build.sh
cd ../../part39/code
./profile_scf.py > profile_out.txt && ./check_profile.py > check_profile_out.txt && ./claims_mutation.py > claims_mutation_out.txt
cd ../../part15/code && ./run_lit.sh          # 150 tests

Chapter summary

  • A differential profile (the same code at four sizes under callgrind) finds the function whose cost grows faster than the rest: here transferNodesFromList, ×3.98, ×3.99, ×4.00 per doubling of the loops, while the program as a whole grows ×2.
  • It is called by Block::splitBlock: lowering each scf.for splits the function's block at the loop and moves everything after it, so n loops in one function cost about n²/2 moved operations.
  • That one function is 13% of the instructions but 63% of the L1 read misses and 97.5% of the write misses, which is why wall-clock time grew faster than the instruction count.
  • After Chapter 38's outlining, the function and splitBlock do not appear at all.
  • The claims are checked from exact instruction counts, with three wrong inputs caught; CI now installs valgrind. No compiler change.

Self-check questions

Each answer is collapsed; try the question first.

  1. Why count instructions with callgrind instead of timing the pass?

    Answer

    Instruction counts are exact and repeatable (the same every run), per function; a stopwatch gives one noisy number per run and cannot say which function is responsible. Running at several sizes and comparing each function's count turns "the pass is slow" into "this function grows ×4 when everything else grows ×2".

  2. In the table, the whole program grows ×2.06 per doubling but one function grows ×3.99. What does each number tell you?

    Answer

    The whole-program number says the program is about linear overall (most of the work scales with the size). The function's ×3.99 says it alone is quadratic; at these sizes it is still a small share of the total instructions (512 of 3,092 million at 8,000 loops), so the total's growth is only slightly above ×2 and creeps up (1.98, 2.06, 2.16) as the quadratic part takes a larger share.

  3. What does Block::splitBlock do, and why does lowering a long run of loops make it quadratic?

    Answer

    It cuts a block in two at an operation and moves all later operations to a new block, updating each moved operation's parent pointer. Lowering a loop to branches needs a new block for the code after it, so each loop's lowering moves everything behind it. With n loops in one function, the first moves about n nests' worth of operations, the next n − 1, and so on: about n²/2 in total.

  4. After --mg-outline-loops, splitBlock is absent from the profile. Why?

    Answer

    Outlining replaces each top-level loop nest with a call, so the big function contains no loops left to lower (its loops are in the small outlined functions, which are few, and each is a short block). With no loop to lower in the big block, SCFToControlFlow never splits it.

  5. The same 32,000 loops took 88 s in one function and 0.4 s in functions of 500 (Chapter 38). How does this chapter account for the difference, and what does it leave unexplained?

    Answer

    In functions of 500 each split moves at most a few hundred nests' worth of operations, so the total is linear in the number of loops; in one function it is quadratic, and the quadratic part misses the cache. What it does not explain is the exact wall-clock factors (9.0, 9.7, 4.8, 3.6): the instruction count grows ×4 cleanly, but the time per moved operation changes with the working-set size, which was not measured.

  6. Why can this chapter's tests run in CI when they depend on a profiler?

    Answer

    They check exact instruction counts, not times, so they give the same answer on any machine, and CI installs valgrind. A timing-based test of the same claim would depend on the machine's speed and load and would be flaky.