Pattern Matching with FileCheck

What is FileCheck?

At its core, FileCheck is a sophisticated pattern-matching tool. You can think of it as a super-powered grep designed specifically for testing compilers. While grep can tell you if a string exists in a file, FileCheck can verify that multiple strings appear in a specific order, on consecutive lines, or not at all between two points. This ability to check for structure and sequence is what makes it so effective for verifying compiler output.

The Anatomy of a FileCheck Test

As you've seen, FileCheck works by scanning its input for patterns specified by CHECK: directives in the test file. The power of FileCheck comes from its rich set of directives that let you define exactly what the output should look like.

Let's explore the most common directives you'll use.

• CHECK-LABEL:: This is one of the most important directives for writing clean tests. It acts like a CHECK, but it also logically divides the input file into separate blocks. This ensures that a check for one function won't accidentally match something in another function. All your tests for a specific function should start with a CHECK-LABEL: for that function's name.

• CHECK:: This is the basic building block. It finds the next occurrence of its pattern in the input. A sequence of CHECK: lines must match in order.

• CHECK-NEXT:: This is stricter than CHECK:. It asserts that the pattern is found on the very next line of the input after the previous match.

• CHECK-SAME:: This asserts that the pattern is found on the same line as the previous match.

• CHECK-NOT:: This is crucial for proving that an optimization worked. It asserts that a given pattern does not appear in the input between the previous match and the next one. For example, after an optimization that removes a load instruction, you would use CHECK-NOT: load to verify it's gone.

• CHECK-DAG:: This directive is for "Directed Acyclic Graph" matching. It allows you to check for several patterns that can appear in any order relative to each other. This is useful when a compiler pass might emit instructions in a non-deterministic order.

Making Tests Flexible: Regex and Variables

Hardcoding exact strings in your checks makes for brittle tests. A change in a register allocator might change %r5 to %r6, which would break your test even if the logic is still correct. FileCheck provides powerful features to handle this.

Regular Expressions

You can embed regular expressions inside {{...}} to match patterns instead of fixed strings. For example, to match any x86 GPR register, you could write {{%e[a-d]x}}. This makes your test independent of the specific register chosen.

String Variables

Even better than regex is the ability to capture and reuse values. This is FileCheck's most powerful feature.
The syntax [[VARNAME:pattern]] matches a pattern (which can be a regex) and stores the matched text in the variable VARNAME. You can then use [[VARNAME]] later in your checks to assert that the exact same text appears again.

Consider this example:

; CHECK: [[REG:%.*]] = load i32, i32* %p
; CHECK: store i32 [[REG]], i32* %q

This test does two things:

1. It looks for a load instruction and captures the name of the destination register (e.g., %0, %v5) into the variable REG. The %.* is a simple regex that matches any sequence of characters.
2. It then asserts that a store instruction uses the exact same register captured in REG as its source.

This allows you to write tests that verify data flow without caring about the specific names of temporary values, which are highly volatile.

The Modern Workflow: Automating Check Generation

Writing all these CHECK lines by hand, especially for large functions, would be incredibly tedious. Fortunately, you don't have to. The standard LLVM contribution workflow is to let a script do it for you.

The llvm/utils/ directory contains a set of update_*_test_checks.py scripts. The most common one is update_test_checks.py for optimizer passes. The workflow looks like this:

1. Write your input code in a .ll or .c file.
2. Write the RUN line that invokes the tool you are testing (e.g., opt -passes=instcombine).
3. Add empty CHECK-LABEL: lines for the functions you want to test.
4. Run the script: python3 llvm/utils/update_test_checks.py your_test_file.ll
5. The script runs the command from your RUN line, captures the output, and automatically inserts the correct CHECK-, CHECK-NEXT-, etc., lines into your test file.

When you fix a bug, you first add a test that fails (or shows the non-optimal code). Then, after implementing your fix, you re-run the update_test_checks.py script. The "diff" of the test file will now clearly show the "before" and "after" of your optimization, which is exactly what code reviewers want to see.

What Makes a Good Test?

Getting a test to pass is easy. Writing a good test that thoroughly validates an optimization and prevents future regressions is an art. A bug fix is only as good as the test that accompanies it. When you submit a patch, reviewers will scrutinize your test as much as your code.

Here are some categories of tests you should always consider, especially for an optimization pass like InstCombine:

1. Positive Tests: Ensure the transform triggers when it should.

   • Commuted Patterns: If your pattern matches A + B, does it also match B + A?
   • Multi-Use: What if an intermediate value in your pattern has other uses? Should the transform still happen? Often, transforms only apply if the intermediate values are dead after the transform, to avoid increasing instruction count.
   • Vector Types: Does your scalar optimization (i32) also work for vectors (<4 x i32>)?

2. Negative Tests: Ensure the transform does not trigger when it shouldn't. This is a common blind spot for new contributors.

   • Wrong Constant: If your transform matches x * 4, add a test for x * 5 to ensure it doesn't match.
   • Wrong Type: If your transform is for integers, test it with floating-point types to ensure it's not applied incorrectly.
   • Wrong Opcode: If you match add and sub, test with add and mul.

3. Edge Cases:

   • Weird Types: Test with i1 (a single bit) or non-power-of-2 types like i17.
   • Constants: What happens if one of the operands is a constant?

Let's Put It All Together

Imagine you've discovered a bug: opt -passes=instcombine fails to optimize the expression (x << 1) + x into x * 3. Let's write a test.

1. Create the file: touch llvm/test/Transforms/InstCombine/mul-by-3.ll

2. Write the IR:

   ; Initially, the file contains the input and the RUN line.
   ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
   
   define i32 @fold_mul_by_3(i32 %x) {
     ; CHECK-LABEL: @fold_mul_by_3
     %shl = shl i32 %x, 1
     %add = add i32 %shl, %x
     ret i32 %add
   }
   

3. Generate initial checks: Without our fix, running utils/update_test_checks.py would generate this:

   define i32 @fold_mul_by_3(i32 %x) {
   ; CHECK-LABEL: @fold_mul_by_3(
   ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 1
   ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SHL]], [[X]]
   ; CHECK-NEXT:    ret i32 [[ADD]]
   ;
     %shl = shl i32 %x, 1
     %add = add i32 %shl, %x
     ret i32 %add
   }
   

   The checks simply reflect the unoptimized input. This is the "before" state.

4. Apply the fix: (Hypothetically, we write C++ code in InstCombine.cpp to fix this).

5. Update the checks: We run utils/update_test_checks.py again. Now, with our fix active, it produces the desired "after" state:

   define i32 @fold_mul_by_3(i32 %x) {
   ; CHECK-LABEL: @fold_mul_by_3(
   ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], 3
   ; CHECK-NEXT:    ret i32 [[MUL]]
   ;
     %shl = shl i32 %x, 1
     %add = add i32 %shl, %x
     ret i32 %add
   }
   

This test now serves as proof that your optimization works and will be run forevermore to ensure no one breaks it.

Conclusion

You now have the theoretical and practical knowledge to write robust regression tests for LLVM. This skill is your entry ticket to fixing bugs. You know how to define expected output, handle variations with variables and regex, and automate the process using standard project scripts.

Key Takeaways:

• FileCheck is a powerful verifier that checks for ordered, structured patterns in text output.
• The main directives are CHECK-LABEL, CHECK, CHECK-NEXT, and CHECK-NOT.
• Use string variables ([[VAR]]) and regex ({{...}}) to make tests flexible and robust.
• The standard workflow is to write the input and RUN line, then use update_test_checks.py to generate the CHECK lines.
• A good test suite includes positive, negative, and edge case tests to be comprehensive.

In this lesson, you learned to write a test for a given piece of code. But where does that code come from? Often, a bug report contains a massive program, and your first job is to shrink it down to the smallest possible example that still shows the bug. Our next lesson will tackle exactly that: you will learn techniques for extracting a minimal reproducible example from a complex bug report.