Lesson 12.4 — lit, FileCheck and automatic check generation

Techniques: lit, LLVM's test runner (RUN lines, substitutions, REQUIRES/UNSUPPORTED/XFAIL); FileCheck, the pattern matcher behind almost every LLVM test (directive semantics, variables, numeric expressions), given here a formal semantics; automatic check generation with update_test_checks.py · Pebble implements: every Chapter 12+ pass is tested with lit + FileCheck (tests/ch12/lit/); the lab's Part A asks you to write a FileCheck test that tolerates harmless changes and catches real ones · Drill: filecheck-match · Prerequisites: Lesson 12.3 · Time: 4–5 hours

A compiler test has to say "the output should look like this" without saying "the output must be exactly this": register names, attributes and unrelated instructions change every week. LLVM's answer is a text matcher, FileCheck, that reads directives from comments in the test itself, driven by a test runner, lit, that reads the commands from the same file; nearly every test under llvm/test is written this way. The directives look simple, but their meaning is subtle: FileCheck is a greedy, non-backtracking matcher, not a constraint solver, and several of its rules surprise experienced users. This lesson gives FileCheck a precise semantics, proves what the greedy algorithm does and does not guarantee, and shows the surprising cases on the real tool.

1. Problem and motivation

lit

A test suite needs a uniform way to say how to run each test, on which configurations it applies, and what counts as success. lit (LLVM Integrated Tester) finds tests by file suffix under a directory with a lit.cfg.py, reads the RUN: lines of each test, replaces substitutions (%s the file, %t a temporary path, %opt, %plugin in this course), runs the resulting shell pipelines, and classifies the test as PASS, FAIL, XFAIL, XPASS or UNSUPPORTED [LLVM-lit]. It is the runner of LLVM, Clang, MLIR and this course's tests/chNN/lit suites.

FileCheck

Comparing whole outputs breaks on every irrelevant change. FileCheck checks an ordered list of patterns against the output, with directives for "next line", "same line", "not in between", "in any order" and "per function block" [LLVM-FileCheck], and the Testing Guide makes it the default way to write regression tests [LLVM-TestingGuide]. Its patterns capture values ([[R:%.*]]) and compute with them ([[#N+1]]), so a test can say "the ret returns what the shl defined" without naming the register.

Automatic check generation

Writing precise CHECK lines by hand for a 30-instruction function is slow and error-prone, and updating hundreds of them after a canonicalization change is worse. llvm/utils/update_test_checks.py runs a test's RUN lines and writes the CHECK lines: every function gets a CHECK-LABEL, every instruction a CHECK-NEXT, every SSA name a capture [LLVM-UTC]. Most InstCombine tests are generated this way; reviewers read the diff of the checks instead of writing them.

2. Definitions and algorithms

Definition 12.4.1 (Input, positions, matches)

The input is a string \(\mathit{in}\) over characters; positions are \(0..\lvert \mathit{in} \rvert\); the line of a position \(q\) is \(1\) plus the number of newlines in \(\mathit{in}[0, q)\). Before matching, FileCheck canonicalizes horizontal whitespace: every run of spaces and tabs becomes one space, in the input and in patterns. A pattern \(p\) denotes a language \(L(p)\) of strings without newlines (literal text, {{regex}} with POSIX extended regular expressions where . does not match newline, captures and uses of variables). A match of \(p\) in the range \([a, b)\) is an interval \([s, e) \subseteq [a, b)\) with \(\mathit{in}[s, e) \in L(p)\). The leftmost match \(\mathrm{first}(p, a, b)\) is the match with the smallest \(s\) (and, for a regex, the longest at that \(s\)).

Definition 12.4.2 (Directives and check strings)

A check file is a sequence of directives \(d_1, \dots, d_m\) of kinds CHECK, CHECK-NEXT, CHECK-SAME, CHECK-LABEL, CHECK-COUNT-\(c\) (positive), CHECK-DAG and CHECK-NOT. FileCheck groups them into check strings: each positive directive together with the maximal run of DAG/NOT directives immediately before it; trailing DAG/NOT directives get an implicit positive directive EOF that matches the empty string at the end of the input. Within a check string, a DAG group is a maximal run of consecutive CHECK-DAGs; a CHECK-NOT separates groups.

Definition 12.4.3 (Declarative semantics: FileCheck as constraints)

Ignore CHECK-LABEL for a moment. An assignment \(\sigma\) maps every positive and DAG directive \(d\) to a match \(\sigma(d) = [s_d, e_d)\). It satisfies the check file if:

1. order: for consecutive positive directives \(d \prec d'\) (with their DAG groups in between), \(e_d \le s_g\) for the first-in-input match \(g\) of the next DAG group, groups follow each other in the input (\(\max e\) of a group \(\le \min s\) of the next), and the last group ends before \(s_{d'}\);
2. next/same: if \(d'\) is CHECK-NEXT, \(\mathit{in}[e_{\mathrm{prev}}, s_{d'})\) contains exactly one newline; if CHECK-SAME, none; where \(e_{\mathrm{prev}}\) is the end of the previous positive match or of the last DAG group in between;
3. dag: the matches of one DAG group are pairwise non-overlapping;
4. not: a CHECK-NOT with pattern \(p\) between regions \([a, b)\) — from the end of what precedes it to the start of what follows it — has no match in \([a, b)\);
5. count: CHECK-COUNT-\(c\) is \(c\) consecutive CHECKs of the same pattern.

The check file holds declaratively on \(\mathit{in}\) if some assignment satisfies it.

Algorithm 12.4.4 (Operational semantics: FileCheck's greedy matcher)

• Input: check strings \(c_1, \dots, c_n\); canonicalized input \(\mathit{in}\).
• Output: pass, or the first failing directive(s).
• Precondition: no CHECK-NEXT/SAME is the first directive; variables are defined before they are used.
• Postcondition: pass iff every check string succeeded (Theorem 12.4.9 relates this to Definition 12.4.3).
• Invariant: pos is the end of the last successful positive match in the current label block; nothing before pos is searched again.

function FileCheck(c_1..c_n, in):                       # FileCheck::checkInput
    failed ← false; buf ← 0; i ← 1
    for each CHECK-LABEL c_j, in order (then a final pseudo-label at the end):
        [ls, le) ← first(c_j.pattern, buf, |in|)        # label scan: positive pattern only
        if none: report c_j; return FAIL                 # a missing label aborts everything
        region ← [buf, le); buf ← le
        pos ← region.start
        while i ≤ j:                                     # c_i .. c_j, the label itself included again
            r ← CheckString(c_i, pos, region.end)
            if r = FAIL: failed ← true; i ← j + 1; break  # skip the rest of this block only
            pos ← r.end; i ← i + 1
    return failed ? FAIL : PASS

function CheckString(c, start, end):                     # FileCheckString::Check
    (last, nots) ← CheckDag(c.dagnots, start, end)
    if last = FAIL: return FAIL
    s ← none; cur ← last
    repeat c.count times:                                # CHECK-COUNT
        m ← first(c.pattern, cur, end); if none: report c; return FAIL
        if s = none: s ← m.start
        cur ← m.end
    k ← number of newlines in in[last, s)
    if c is NEXT and k ≠ 1: report c; return FAIL        # searched like CHECK, THEN checked
    if c is SAME and k ≠ 0: report c; return FAIL
    if some p ∈ nots has a match in [last, s): report it; return FAIL
    return [s, cur)

function CheckDag(items, start, end):                    # FileCheckString::CheckDag
    groupStart ← start; ranges ← []; nots ← []
    for each item x in order:
        if x is NOT: nots ← nots · [x]; continue
        q ← groupStart
        loop:                                            # skip matches overlapping this group's
            m ← first(x.pattern, q, end); if none: report x; return FAIL
            if m overlaps some r ∈ ranges: q ← end of the first overlapped r; continue
            insert m into ranges (sorted); break
        if x ends its DAG group:
            if nots ≠ []:
                if some p ∈ nots has a match in [groupStart, min start of ranges): report; return FAIL
                nots ← []
            groupStart ← max end of ranges; ranges ← []
    return (groupStart, nots)                            # remaining NOTs are checked by CheckString

Definition 12.4.5 (Variables and numeric expressions)

[[NAME:regex]] matches regex and binds the matched text to NAME when the directive succeeds; [[NAME]] matches exactly that text. [[#NAME:]] captures an unsigned decimal number, [[#NAME+1]] (also -, and %X, %x, %d formats) matches the value of the expression. Variables persist across CHECK-LABEL blocks unless --enable-var-scope is given (then names not starting with $ are cleared at each label).

lit

Definition 12.4.6 (lit test and verdict)

A lit test is a file with lines RUN: cmd (a shell pipeline after substitution), optional REQUIRES: f / UNSUPPORTED: f (boolean expressions over features the configuration defines) and XFAIL: f. The outcome of running it is \(\mathrm{ok}\) if every RUN pipeline exits with 0 (lit enables pipefail), \(\mathrm{fail}\) otherwise. The verdict is: UNSUPPORTED if a REQUIRES is false or an UNSUPPORTED is true (not run); otherwise PASS / FAIL for ok / fail, unless an XFAIL expression is true, in which case XFAIL / XPASS for fail / ok. Only FAIL and XPASS make the suite fail.

Algorithm 12.4.7 (lit)

• Input: paths; configuration files lit.cfg.py (suffixes, substitutions, features, test format).
• Output: a verdict per test; exit status 0 iff no FAIL/XPASS.
• Precondition: every test file lies under a directory whose configuration can be found upward.
• Postcondition: each discovered test gets exactly one verdict (Definition 12.4.6).
• Invariant: tests are independent: each gets its own %t and runs in a fresh shell.

function Lit(paths):
    tests ← Discover(paths)                     # walk directories, apply config.suffixes and excludes
    run ← parallel for T in tests:              # -j workers
        if not Applies(T.requires, T.unsupported, config.features): verdict[T] ← UNSUPPORTED; continue
        ok ← true
        for R in T.run_lines:
            cmd ← Substitute(R, config.substitutions ∪ {%s, %S, %t, %T})   # longest names first
            if RunShell(cmd, pipefail) ≠ 0: ok ← false; break
        xf ← Eval(T.xfail, config.features)
        verdict[T] ← xf ? (ok ? XPASS : XFAIL) : (ok ? PASS : FAIL)
    return (any verdict ∈ {FAIL, XPASS}) ? 1 : 0

Automatic check generation

Algorithm 12.4.8 (update_test_checks.py, simplified)

• Input: a test file whose RUN line pipes opt ... | FileCheck %s.
• Output: the file with every function followed by generated CHECK lines.
• Precondition: opt is on PATH (or --opt-binary); the RUN line's FileCheck prefix is known.
• Postcondition: the generated checks pass on the output they were generated from (Theorem 12.4.14).
• Invariant: each IR value name gets one variable, defined at its first occurrence and used afterwards.

function UpdateTestChecks(test):
    for each RUN line (tool, args, prefixes):
        out ← run tool args on test
        for each function f in out:
            body_f ← the lines of f
    remove old autogenerated CHECK lines; add the NOTE line with UTC_ARGS
    for each function f in test:
        emit "; CHECK-LABEL: define <ret> @f("
        emit "; CHECK-SAME: <params with %x replaced by [[X:%.*]]>) {"
        vars ← names bound by the signature
        for each line L of body_f:
            for each value name %v in L:
                if %v ∉ vars: replace it by [[V:%.*]] (fresh upper-case name, suffix on clash); vars ← vars ∪ {%v}
                else: replace it by [[V]]
            emit "; CHECK-NEXT: " + L                     # labels get CHECK: <label>: instead
        emit ";"                                          # end of the function's checks

3. Worked example

The running example is the output of pebble-strength on two functions, and a check file a learner might write for it (Exercise E2), with FileCheck's directive numbers:

define i32 @mul8(i32 %x) {
  %r = shl i32 %x, 3
  ret i32 %r
}
define i32 @sdiv4(i32 %x) {
  %1 = ashr i32 %x, 31
  %2 = lshr i32 %1, 30
  %3 = add i32 %x, %2
  %r = ashr i32 %3, 2
  ret i32 %r
}

 1  CHECK-LABEL: @mul8(
 2  CHECK: shl i32 %x, 3
 3  CHECK-NOT: mul
 4  CHECK-LABEL: @sdiv4(
 5  CHECK-DAG: lshr
 6  CHECK-DAG: ashr i32 %x, 31
 7  CHECK-NOT: sdiv
 8  CHECK: [[T:%[0-9]+]] = add i32 %x
 9  CHECK-NEXT: %r = ashr i32 [[T]], 2

Check strings: \(c_1 = (1)\), \(c_2 = (2)\), \(c_3 = (3; 4)\) — the NOT belongs to the label —, \(c_4 = (5, 6, 7; 8)\) with one DAG group \(\{5, 6\}\) followed by NOT 7, \(c_5 = (9)\). Algorithm 12.4.4, one row per step (line numbers of the input):

step	action	range searched	result	state
1	scan label 1 @mul8(	whole input	line 1	block 1 = lines 1..1 (up to the label's match)
2	check \(c_1\) again in block 1	block 1	line 1	pos = after @mul8(
3	scan label 4 @sdiv4(	after @mul8(	line 5	block 2 = rest of line 1 .. @sdiv4( on line 5
4	\(c_2\): CHECK 2	block 2	line 2	pos = after shl i32 %x, 3
5	\(c_3\): NOT 3 queued; label 4 in block 2	line 2 .. line 5	label at line 5; mul absent from the range → ok	pos = after @sdiv4(
6	scan the final pseudo-label (end of input)	—	—	block 3 = rest of line 5 .. end
7	\(c_4\): DAG 5 lshr	block 3	line 7	ranges =
8	DAG 6 ashr i32 %x, 31	from block start (DAGs restart)	line 6, no overlap	ranges = {6, 7}; group ends; groupStart = end of the line-7 match
9	CHECK 8, capture T	after lshr on line 7	line 8, T = %3	NOT 7 checked on [after lshr, start of line-8 match): no sdiv → ok
10	\(c_5\): CHECK-NEXT 9 with T = %3	after line-8 match	line 9	exactly one newline in between → ok. PASS

Note step 8: DAG 6 matched earlier in the input than DAG 5 — CHECK-DAG allows any order within a group.

Try it

./course drill filecheck-match --seed 3 --difficulty medium --solution gives a DAG/NOT problem of this kind; --difficulty hard adds labels, counts and captured variables.

4. Invariants and correctness

Theorem 12.4.9 (Soundness of the greedy matcher)

If Algorithm 12.4.4 passes on \(\mathit{in}\), the matches it found form an assignment satisfying Definition 12.4.3 (with labels: each label block satisfies it for the directives assigned to it).

Proof

Let \(\sigma\) map each positive and DAG directive to the match the algorithm accepted. Order: every positive search starts at pos, the end of the previous accepted match or of the last DAG group, so \(s_{d'} \ge e_{\mathrm{prev}}\); each DAG group's searches start at groupStart, the end of what precedes it, and the next group starts at the maximum end of this group's ranges, which is the group order of Definition 12.4.3. Next/same: CheckString counts the newlines in exactly \([e_{\mathrm{prev}}, s)\) and fails unless the count is 1 (NEXT) or 0 (SAME). Dag: a DAG match overlapping an accepted one is never inserted. Not: each queued NOT is searched in exactly the region between the matches around it and a match fails the run. Count: the \(c\) repetitions are consecutive searches. Since the run passed, no check failed, so every clause holds for \(\sigma\). ∎

Theorem 12.4.10 (Completeness for literal CHECK chains)

If a check file consists only of CHECK and CHECK-COUNT directives with literal patterns (no regexes, no variables), then Algorithm 12.4.4 passes iff the check file holds declaratively.

Proof

"Only if" is Theorem 12.4.9. "If": let \(\sigma\) satisfy the constraints, and let \(g_1, g_2, \dots\) be the greedy matches. We show \(e(g_i) \le e(\sigma(d_i))\) for all \(i\) by induction (an exchange argument). For \(i = 1\), the greedy search from \(0\) finds the leftmost occurrence, which starts no later than \(\sigma(d_1)\); both have the pattern's fixed length, so it ends no later. For \(i > 1\), the greedy search starts at \(e(g_{i-1}) \le e(\sigma(d_{i-1})) \le s(\sigma(d_i))\), so \(\sigma(d_i)\) lies inside the searched range and the leftmost match \(g_i\) exists, starts no later and, with equal length, ends no later. Hence every greedy search succeeds and the algorithm passes. ∎

Proposition 12.4.11 (Where greediness loses)

Theorem 12.4.10 fails for each of CHECK-NEXT, CHECK-NOT, CHECK-DAG and regex patterns: for each there is an input on which the check file holds declaratively but FileCheck fails.

1. NEXT: CHECK: a / CHECK-NEXT: c on the lines a b a c.
2. NOT: CHECK: a / CHECK-NOT: X / CHECK: b on the line a X a b.
3. DAG: CHECK-DAG: x / CHECK-DAG: x y on the lines x y, x.
4. Regex: CHECK: {{a.*}} / CHECK: b on the line ab.

Proof

For each, a satisfying assignment and the greedy failure. (1) Assign a to line 3 and c to line 4: exactly one newline in between. Greedy takes the a of line 1; the leftmost c after it is on line 4, three newlines away: fail. (2) Assign the second a (position 4) and b: the region between them is a space. Greedy takes the first a; the region up to b contains X: fail. (3) Assign x to line 2 and x y to line 1: disjoint. Greedy gives x the first x of line 1; x y overlaps it, the search resumes after it and finds no x y: fail. (4) Assign {{a.*}} to a and b to b. The regex match is leftmost-longest, ab, and no b follows: fail. The real-world box in §7 runs all four with FileCheck 23.1.2. ∎

Theorem 12.4.12 (A CHECK-NOT between CHECK-DAGs orders them)

Let DAG group \(G_1\) be followed by CHECK-NOT \(p\) and then DAG group \(G_2\). FileCheck checks \(p\) on \([\max_{g \in G_1} e_g, \min_{h \in G_2} s_h)\), and every match of \(G_2\) starts after every match of \(G_1\) ends. In particular CHECK-DAG: a / CHECK-NOT: Y / CHECK-DAG: b fails on the input b, a even though Y never occurs, while CHECK-DAG: a / CHECK-DAG: b passes.

Proof

In CheckDag, the group end of \(G_1\) sets groupStart to the maximum end of \(G_1\)'s ranges and clears the ranges; every search of \(G_2\) starts at groupStart, so all of \(G_2\)'s matches start at or after it. When \(G_2\)'s group ends, the queued NOTs are searched in [groupStart, min start of ranges), the stated region. For the example, a is matched on line 2; b must then be found after line 2's a, and there is none: CHECK-DAG: b fails ("expected string not found"). Without the NOT, both DAGs are in one group, searched from the same start, and match lines 2 and 1 without overlap. ∎

Proposition 12.4.13 (Labels confine and recover)

With CHECK-LABELs \(\ell_1, \dots, \ell_k\) found at increasing positions, every directive between \(\ell_{j-1}\) and \(\ell_j\) is matched inside \([\mathrm{end}(\ell_{j-1}), \mathrm{end}(\ell_j))\); a failure in one block does not prevent the other blocks from being checked, but a label that is not found aborts the run.

Proof

FileCheck scans each label from the end of the previous one before checking the block, and passes region.end = le to every CheckString of the block, so no search leaves the region. On a failure it sets failed and moves i to the next block instead of returning; only a failed label scan returns immediately. ∎

Theorem 12.4.14 (Generated checks are self-consistent)

Let \(\mathit{out}\) be the output from which Algorithm 12.4.8 generated checks \(K\). Then FileCheck with \(K\) passes on \(\mathit{out}\), and fails on every output that differs from \(\mathit{out}\) in some function body by more than a consistent renaming of value names (or by lines outside the checked functions).

Proof sketch (full argument: the generator in [LLVM-UTC] and Theorem 12.4.9)

Each function's checks are a LABEL, a SAME for the signature, and one NEXT per body line with names replaced by captures [[V:%.*]] at first occurrence and uses [[V]] afterwards. On \(\mathit{out}\), the label scan finds the function, each NEXT's leftmost match is the corresponding line (the pattern is that line with names generalized), captures bind the actual names, so all constraints hold and the greedy run follows \(\mathit{out}\) line by line. Conversely, a body that inserts, deletes or changes a line breaks a NEXT (exactly one newline) or a pattern, and a renaming that is not consistent breaks a use [[V]]. The %.* in captures is why "consistent renaming" is the only tolerated change. ∎

A CHECK line that can never fail

CHECK-NOT: sdiv written after the last CHECK of a function block is checked only up to the next label, not in the whole function; CHECK: ret matches ret in %ret.addr; and a misspelled directive such as CHEKC: is ordinary comment text to FileCheck. Every test in tests/ch12/lit was mutation-checked for this reason: a planted bug must make it fail.

5. Complexity

Let \(\lvert \mathit{in} \rvert = n\) characters, \(m\) directives, \(\lvert p \rvert\) the pattern length, \(g\) the size of the largest DAG group, \(T\) the number of tests and \(W\) the number of lit workers.

Technique	Time (worst)	Time (typical)	Space	Notes
lit	\(\sum_T\) (cost of its RUN lines) / \(W\)	dominated by the tools run; lit itself is milliseconds per test	per-test temporary files	-j parallelism; tests are independent (Algorithm 12.4.7)
FileCheck	\(O(m \cdot n \cdot \lvert p \rvert)\) for literals; DAG groups add a factor \(g\) (restarts after overlaps)	linear-ish: each positive search moves forward	the input and the patterns	regex matching is backtracking-free (POSIX regexec) but may be super-linear per call
update_test_checks	one run of each RUN line + \(O(\lvert \mathit{out} \rvert)\) rewriting	seconds per test	the output	re-run after every intended change

Justification. Each positive directive does one leftmost search over at most the rest of its block, \(O(n \lvert p \rvert)\) with a naive literal search; NOT and DAG searches cover ranges of the same bound. A DAG pattern can be rediscovered at most once per overlapping earlier match of its group, adding a factor \(g\). Pathological family: a DAG group of \(g\) identical patterns CHECK-DAG: a on an input of \(g\) lines a: the \(j\)-th DAG finds line 1, overlaps, resumes after it, ..., and accepts line \(j\) after \(j - 1\) restarts: \(\sum_j j = \Theta(g^2)\) searches. At scale the cost that matters is lit's: LLVM's ninja check-llvm runs tens of thousands of tests, which is why lit parallelizes across tests.

6. Variants and refinements

lit

• Test formats beyond ShTest: GoogleTest (runs each gtest as a lit test), ExecutableTest [LLVM-lit]. Trade-off: one runner for unit and file tests.
• split-file keeps several input files in one test (#--- a.ll). Trade-off: longer tests, but no Inputs/ indirection.
• %{...} custom substitutions and DEFINE:/REDEFINE: for parameterized RUN lines.

FileCheck

• --match-full-lines, --strict-whitespace, --implicit-check-not=<pattern> make matching stricter (the last adds a NOT between every pair of directives: the course's uninit.c test uses it). Trade-off: brittleness.
• --dump-input annotates the input with every match and failure (lit shows it on failure, §7).
• CHECK-EMPTY, COM: comments, --check-prefixes=A,B to share checks between RUN lines.

Automatic check generation

• update_llc_test_checks.py (assembly), update_mir_test_checks.py, update_cc_test_checks.py (Clang output), update_analyze_test_checks.py (printer output) in llvm/utils/. Trade-off: one generator per output format.
• --version N and UTC_ARGS pin the generator's behavior per test, so regenerating does not rewrite unrelated lines. Trade-off: several generations of check style coexist.
• Snapshot testing (Lesson 12.5) is the limit case: check everything, update by accepting.

7. In real compilers

lit

llvm/utils/lit/lit/ — TestRunner.py (executeShTest, parseIntegratedTestScript), Test.py (the result codes) [LLVM-litSrc]; the course's configuration tests/lit.cfg.py (%opt, %plugin, %clang-ir, the solution feature).

lit verdicts: PASS, FAIL with an annotated dump, XFAIL

Reproduce (lit 23.1.2 — the course's uv environment has it, uv run lit from the repository — opt and FileCheck 23.1.2 on PATH):

mkdir -p demo && cd demo
cat > lit.cfg.py <<'EOF'
import lit.formats
config.name = "demo"
config.test_format = lit.formats.ShTest(execute_external=False)
config.suffixes = [".ll"]
config.substitutions.append(("%opt", "opt"))
config.substitutions.append(("%FileCheck", "FileCheck"))
EOF
printf '; RUN: %%opt -passes=instcombine -S %%s | %%FileCheck %%s\ndefine i32 @f(i32 %%x) {\n; CHECK: shl i32 %%x, 3\n  %%r = mul i32 %%x, 8\n  ret i32 %%r\n}\n' > mul.ll
printf '; RUN: %%opt -passes=instcombine -S %%s | %%FileCheck %%s\n; XFAIL: *\ndefine i32 @g(i32 %%x) {\n; CHECK: ashr i32 %%x, 2\n  %%r = sdiv i32 %%x, 4\n  ret i32 %%r\n}\n' > sdiv.ll
printf '; RUN: %%opt -passes=instcombine -S %%s | %%FileCheck %%s\ndefine i32 @h(i32 %%x) {\n; CHECK: lshr i32 %%x, 2\n  %%r = sdiv i32 %%x, 4\n  ret i32 %%r\n}\n' > wrong.ll
cd .. && lit -j1 -v demo 2>&1 | sed "s|$PWD/||g" | grep -vE '^Testing Time|^$'

Output (complete):

-- Testing: 3 tests, 1 workers --
PASS: demo :: mul.ll (1 of 3)
XFAIL: demo :: sdiv.ll (2 of 3)
FAIL: demo :: wrong.ll (3 of 3)
******************** TEST 'demo :: wrong.ll' FAILED ********************
Exit Code: 1
Command Output (stdout):
--
# RUN: at line 1
opt -passes=instcombine -S demo/wrong.ll | FileCheck demo/wrong.ll
# executed command: opt -passes=instcombine -S demo/wrong.ll
# executed command: FileCheck demo/wrong.ll
# .---command stderr------------
# | demo/wrong.ll:3:10: error: CHECK: expected string not found in input
# | ; CHECK: lshr i32 %x, 2
# |          ^
# | <stdin>:1:1: note: scanning from here
# | ; ModuleID = 'demo/wrong.ll'
# | ^
# | <stdin>:5:7: note: possible intended match here
# |  %r = sdiv i32 %x, 4
# |       ^
# | 
# | Input file: <stdin>
# | Check file: demo/wrong.ll
# | 
# | -dump-input=help explains the following input dump.
# | 
# | Input was:
# | <<<<<<
# |            1: ; ModuleID = 'demo/wrong.ll' 
# | check:3'0    {                                                search range start (exclusive)
# | check:3'1                                                     error: no match found in search range
# |            2: source_filename = "demo/wrong.ll" 
# |            3:  
# |            4: define i32 @h(i32 %x) { 
# |            5:  %r = sdiv i32 %x, 4 
# | check:3'2           ?                possible intended match
# |            6:  ret i32 %r 
# |            7: } 
# | check:3'3       } search range end (exclusive)
# | >>>>>>
# `-----------------------------
# error: command failed with exit status: 1
--
********************
********************
Failed Tests (1):
  demo :: wrong.ll
Total Discovered Tests: 3
  Passed           : 1 (33.33%)
  Expectedly Failed: 1 (33.33%)
  Failed           : 1 (33.33%)

What to notice: Definition 12.4.6's verdicts: sdiv.ll fails (InstCombine keeps sdiv, Lesson 12.3) but is marked XFAIL: *, so it counts as expected; wrong.ll fails and lit prints the RUN pipeline, the FileCheck error and the annotated input dump. The suite's exit status is 1 because of that single FAIL.

FileCheck

llvm/lib/FileCheck/FileCheck.cpp — FileCheck::checkInput, FileCheckString::Check, FileCheckString::CheckDag, FileCheckString::CheckNot, FileCheckString::CheckNext, Pattern::match [LLVM-FileCheckSrc] (LLVM 23.1.2); the course's Python re-implementation tools/course/lib/filecheck.py agrees with it on 600 random drill instances (test_ch12.py).

FileCheck's greedy failures and the ordering effect of CHECK-NOT

Reproduce (FileCheck 23.1.2; t runs one check file on one input and prints the first error):

t() { printf "$1" > in.txt; printf "$2" > chk.txt
      FileCheck chk.txt --input-file=in.txt --dump-input=never 2>&1 | head -1; echo "exit $?"; }
t 'a\nb\na\nc\n' 'CHECK: a\nCHECK-NEXT: c\n'
t 'a X a b\n' 'CHECK: a\nCHECK-NOT: X\nCHECK: b\n'
t 'x y\nx\n' 'CHECK-DAG: x\nCHECK-DAG: x y\n'
t 'x y\nx\n' 'CHECK-DAG: x y\nCHECK-DAG: x\n'
t 'ab\n' 'CHECK: {{a.*}}\nCHECK: b\n'
t 'b\na\n' 'CHECK-DAG: a\nCHECK-DAG: b\n'
t 'b\na\n' 'CHECK-DAG: a\nCHECK-NOT: Y\nCHECK-DAG: b\n'

Output:

chk.txt:2:13: error: CHECK-NEXT: is not on the line after the previous match
exit 0
chk.txt:2:12: error: CHECK-NOT: excluded string found in input
exit 0
chk.txt:2:12: error: CHECK-DAG: expected string not found in input
exit 0
exit 0
chk.txt:2:8: error: CHECK: expected string not found in input
exit 0
exit 0
chk.txt:3:12: error: CHECK-DAG: expected string not found in input
exit 0

What to notice: lines 1–5 of the output are Proposition 12.4.11's four counterexamples (the fourth run shows that reordering the DAGs repairs case 3); the last two runs are Theorem 12.4.12: adding a CHECK-NOT for a string that does not occur makes a passing test fail, because it splits the DAG group and orders b after a. (exit 0 is head's status; FileCheck's own is 1 whenever it printed an error.)

Numeric variables: checking register arithmetic

Reproduce (FileCheck 23.1.2):

printf '%%v3 = add i32 %%v2, 1\n%%v4 = mul i32 %%v3, 8\n' > in.txt
printf 'CHECK: %%v[[#N:]] = add\nCHECK-NEXT: %%v[[#N+1]] = mul i32 %%v[[#N]]\n' > ok.txt
printf 'CHECK: %%v[[#N:]] = add\nCHECK-NEXT: %%v[[#N+2]] = mul\n' > bad.txt
FileCheck ok.txt --input-file=in.txt && echo ok
FileCheck bad.txt --input-file=in.txt --dump-input=never 2>&1 | head -2

Output:

ok
bad.txt:2:13: error: CHECK-NEXT: expected string not found in input
CHECK-NEXT: %v[[#N+2]] = mul

What to notice: [[#N:]] captured 3 (Definition 12.4.5), [[#N+1]] required %v4 and [[#N]] reused 3 — a check on the relation between numbers, which a string variable cannot express.

Automatic check generation

llvm/utils/update_test_checks.py and llvm/utils/UpdateTestChecks/common.py (generalize_check_lines, FunctionTestBuilder) [LLVM-UTC] (llvmorg-23.1.2). Most tests under llvm/test/Transforms/InstCombine/ start with its ; NOTE: Assertions have been autogenerated line.

update_test_checks.py writes the CHECK lines

Reproduce (update_test_checks.py from llvmorg-23.1.2, opt 23.1.2 on PATH, Python 3.11):

U=https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/utils
mkdir -p UpdateTestChecks
curl -sSO $U/update_test_checks.py
for f in __init__.py common.py asm.py isel.py mir.py; do curl -sS -o UpdateTestChecks/$f $U/UpdateTestChecks/$f; done
cat > strength.ll <<'EOF'
; RUN: opt -passes=instcombine -S < %s | FileCheck %s
define i32 @mul8(i32 %x) {
  %r = mul i32 %x, 8
  ret i32 %r
}
define i32 @udiv4(i32 %x) {
  %r = udiv i32 %x, 4
  ret i32 %r
}
EOF
python3 update_test_checks.py --version 5 strength.ll && cat strength.ll

Output:

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
; RUN: opt -passes=instcombine -S < %s | FileCheck %s
define i32 @mul8(i32 %x) {
; CHECK-LABEL: define i32 @mul8(
; CHECK-SAME: i32 [[X:%.*]]) {
; CHECK-NEXT:    [[R:%.*]] = shl i32 [[X]], 3
; CHECK-NEXT:    ret i32 [[R]]
;
  %r = mul i32 %x, 8
  ret i32 %r
}
define i32 @udiv4(i32 %x) {
; CHECK-LABEL: define i32 @udiv4(
; CHECK-SAME: i32 [[X:%.*]]) {
; CHECK-NEXT:    [[R1:%.*]] = lshr i32 [[X]], 2
; CHECK-NEXT:    ret i32 [[R1]]
;
  %r = udiv i32 %x, 4
  ret i32 %r
}

What to notice: Algorithm 12.4.8: a LABEL per function, SAME for the signature, one NEXT per line, and every value a capture. [[R1:%.*]] in the second function shows the generator's global naming (a fresh suffix because R was used above); the checks forbid any change but a consistent renaming (Theorem 12.4.14) — maximal strictness, and a regeneration after every intended change.

8. Comparison

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
lit	Runs any shell pipeline; features select configurations; XFAIL for known bugs	Parallel; per-test cost is the tools	PASS/FAIL/XFAIL/XPASS/UNSUPPORTED with the failing command	Low per test (RUN lines); one lit.cfg.py per suite	LLVM, Clang, MLIR, this course
FileCheck	Ordered patterns with NEXT/SAME/NOT/DAG/LABEL, captures, numeric expressions; greedy, sound but incomplete (Theorems 12.4.9, 12.4.10, Prop. 12.4.11)	\(O(m\,n\,\lvert p \rvert)\); fast	Precise error location and an annotated input dump	Low to write, easy to get subtly wrong (NOT ranges, DAG/NOT ordering)	Checking the relevant part of compiler output
Automatic check generation	Checks everything up to consistent renaming (Theorem 12.4.14)	One run per update	Diffs of generated checks in review	Very low per test; one generator per output kind	InstCombine and most IR transformation tests

Choose lit when tests are commands on files; it is the natural runner for a compiler. Choose hand-written FileCheck when the property is local ("this sdiv is gone", "the counter comes after the phis") and the rest of the output should be free to change. Choose generated checks when the whole output of a small function is the property and reviewers will read the diffs — and remember that they then behave like snapshot tests (Lesson 12.5).

9. Assessment

• Quiz: fc-next-greedy, fc-dag-not-order, fc-trace (mapping), fc-first-error (number), fc-label-recovery, lit-verdict (mapping), utc-strictness, llvm-where-checkdag.
• Drill: ./course drill filecheck-match (verdict, first failing directive and match lines).
• Flashcards: tags lit, filecheck, update-test-checks.
• Exercises: the lab's Part A (L1) asks for a FileCheck test of pebble-lab-fold that detects bugs 1, 2, 3 and 5 but not the harmless bug 4 (SPEC.md).
• Find where LLVM does it: in llvm/lib/FileCheck/FileCheck.cpp, which member function of FileCheckString implements the overlap rule of CHECK-DAG?

References

See the chapter references.