FileCheck: Allow CHECK-{SAME,NEXT,EMPTY} after initial CHECK-DAG

[thopre]

Summary

When following a CHECK-DAG block, FileCheck correctly matches
CHECK-NEXT, CHECK-SAME and CHECK-EMPTY relative to the CHECK-DAG that
matches the latest line in the input file, as one would expect. However,
FileCheck refuses to run if the CHECK-DAG directives are the first in
the file. This commit lift this restriction.

Note: there is debate in the comments over whether the inconsistency should be fixed by forbidding CHECK-DAG before a CHECK-EMPTY, CHECK-SAME or CHECK-NEXT always. More opinions welcome.

[thopre]

Ping?

[probinson]

The revision title and summary contradict each other. The title says to allow something, but the summary says that already works; then the summary says CHECK-DAG can't be first, while the check-dag.txt test clearly already has CHECK-DAG as the first directive.
Please fix up the title and summary so that they correctly describe what you are trying to accomplish. This will help reviewers to make sure the patch does what you want.

[jdenny]

Hi Thomas,

Thanks for working to clean up this area.

As I understand it, CHECK-NEXT, CHECK-SAME, and CHECK-EMPTY currently can appear after non-initial CHECK-DAG blocks, and this patch intends to permit them after initial CHECK-DAG blocks as well. I agree with Paul that the title should be adjusted to reflect that.

However, I remember some disagreement in the past as to whether these directives should be permitted after any CHECK-DAG at all. We should probably resolve any remaining disagreement before relaxing things further.

Consider the example that this patch adds to the docs:

// CHECK-DAG: mov r0, #0
// CHECK-DAG: mov r1, #1
// CHECK-NEXT: add r2, r0, r1

Unmatched lines are permitted to appear between CHECK-DAG matches, but unmatched lines are not permitted to appear between whichever CHECK-DAG match happens to occur last and the CHECK-NEXT match. Is that a realistic use case?

A realistic use case would probably involve something like a CHECK-DAG-NEXT directive that doesn't permit intervening lines anywhere in the block. Or should the above example actually indicate exactly that?

Do you have a use case from a real test to inform this discussion?

llvm/docs/CommandGuide/FileCheck.rst

255–259

"ie." -> "i.e.,"

If "ie." is common in some context, please give me a pointer.

284–287

"ie." -> "i.e.,"

452

"word" -> "words"

llvm/lib/Support/FileCheck.cpp

845

"ie." -> "i.e.,"

[thopre]

In D56789#1368287, @jdenny wrote:

Hi Thomas,

Thanks for working to clean up this area.

As I understand it, CHECK-NEXT, CHECK-SAME, and CHECK-EMPTY currently can appear after non-initial CHECK-DAG blocks, and this patch intends to permit them after initial CHECK-DAG blocks as well. I agree with Paul that the title should be adjusted to reflect that.

Correct.

However, I remember some disagreement in the past as to whether these directives should be permitted after any CHECK-DAG at all. We should probably resolve any remaining disagreement before relaxing things further.

Indeed, I was not aware of the disagreement.

Consider the example that this patch adds to the docs:

// CHECK-DAG: mov r0, #0
// CHECK-DAG: mov r1, #1
// CHECK-NEXT: add r2, r0, r1

Unmatched lines are permitted to appear between CHECK-DAG matches, but unmatched lines are not permitted to appear between whichever CHECK-DAG match happens to occur last and the CHECK-NEXT match. Is that a realistic use case?

Fair enough, any clobber can happen between the two, forgot about that. Note that I can see several existing tests in the testsuite that have CHECK-NEXT right after CHECK-DAG which are probably not as strict in terms of testing as their author were expecting, e.g.

test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll
test/Bitcode/thinlto-function-summary-originalnames.ll
test/CodeGen/AArch64/arm64-ccmp.ll
test/CodeGen/AArch64/arm64-indexed-vector-ldst.ll (though it's a single DAG between a CHECK and CHECK-NEXT so it's a special case)
test/CodeGen/AArch64/f16-instructions.ll

and many more.

A realistic use case would probably involve something like a CHECK-DAG-NEXT directive that doesn't permit intervening lines anywhere in the block. Or should the above example actually indicate exactly that?

Do you have a use case from a real test to inform this discussion?

Agreed, something like CHECK-DAG-NEXT would be better suited. The requirement of CHECK-DAG with CHECK-NEXT was mentioned to me by a coworker and I noticed the weird inconsistency regarding whether CHECK-DAG is the first check directives or not and thought I'd fix it. The behaviour we need is indeed reordering without any line not checked for in between using CHECK-DAG is not the right solution. So I guess the correct approach would be to error out on CHECK-DAG with CHECK-NEXT, CHECK-SAME or CHECK-EMPTY, probably with some flag to enable the old behavior while tests are updated.

Regarding CHECK-DAG-NEXT, I wonder how it would interact with CHECK-DAG? Perhaps we should introduce some sort of only-tested region (e.g. CHECK-ONLY-START and CHECK-ONLY-END with better name) where CHECK-DAG inside would still be able to be reordered but only what is tested by a CHECK-DAG is allowed. It could also allow CHECK directive inside which would behave as CHECK-NEXT. How does that sound?

[thopre]

Fix typos and improve title

[jdenny]

In D56789#1371821, @thopre wrote:

Fair enough, any clobber can happen between the two, forgot about that. Note that I can see several existing tests in the testsuite that have CHECK-NEXT right after CHECK-DAG which are probably not as strict in terms of testing as their author were expecting, e.g.

test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll
test/Bitcode/thinlto-function-summary-originalnames.ll
test/CodeGen/AArch64/arm64-ccmp.ll
test/CodeGen/AArch64/arm64-indexed-vector-ldst.ll (though it's a single DAG between a CHECK and CHECK-NEXT so it's a special case)
test/CodeGen/AArch64/f16-instructions.ll

and many more.

Not surprising. I remember now that I've put a CHECK-SAME after a CHECK-DAG because I wanted to look for items that could occur in any order on a single line. I don't remember now if I did that as a best approximation of what I wanted or if I mistakenly thought it already achieved what I wanted.

A realistic use case would probably involve something like a CHECK-DAG-NEXT directive that doesn't permit intervening lines anywhere in the block. Or should the above example actually indicate exactly that?

Do you have a use case from a real test to inform this discussion?

Agreed, something like CHECK-DAG-NEXT would be better suited. The requirement of CHECK-DAG with CHECK-NEXT was mentioned to me by a coworker and I noticed the weird inconsistency regarding whether CHECK-DAG is the first check directives or not and thought I'd fix it. The behaviour we need is indeed reordering without any line not checked for in between using CHECK-DAG is not the right solution. So I guess the correct approach would be to error out on CHECK-DAG with CHECK-NEXT, CHECK-SAME or CHECK-EMPTY, probably with some flag to enable the old behavior while tests are updated.

Possibly so. Given that many of those existing cases were probably intending the stricter behavior, let's first create a better solution for the stricter behavior.

Regarding CHECK-DAG-NEXT, I wonder how it would interact with CHECK-DAG?

I think that any kind of CHECK-DAG* following a different kind of CHECK-DAG* would start a new block such that there's no reordering among blocks. Otherwise, the semantics become very unclear to me.

It seems intuitive that the first match in a CHECK-DAG-NEXT block would have to appear on the line after whatever match came before the block. However, if you don't want that behavior, then I'm not sure how you would express that.

Perhaps we should introduce some sort of only-tested region (e.g. CHECK-ONLY-START and CHECK-ONLY-END with better name) where CHECK-DAG inside would still be able to be reordered but only what is tested by a CHECK-DAG is allowed. It could also allow CHECK directive inside which would behave as CHECK-NEXT. How does that sound?

Or would that CHECK inside behave as a CHECK-SAME? In general, how would whitespace be handled? Error or ignored?

What you propose sounds very similar to something I suggested at one point: CHECK-NOT-PUSH and CHECK-NOT-POP. The idea is you would push a pattern into -implicit-check-not so the pattern would be rejected among matches between the push and the pop. This would be useful in any context where you want -implicit-check-not but don't want it for the entire input.

To achieve something like CHECK-DAG-SAME, the pattern would specify a single newline, and you'd put CHECK-DAG directives in between the push and pop. To achieve something like CHECK-DAG-NEXT, you'd do the same but each CHECK-DAG's pattern would be specified to gobble up the next newline. Then again, those two cases might be easier to write and diagnostics might be clearer if we created special-purpose directives, but they could probably be built on the same infrastructure.

If all that makes sense to you, there are some details we could discuss about how CHECK-NOT-PUSH and CHECK-NOT-POP would interact with neighboring CHECK-NOT directives and neighboring matches.

[jdenny]

I've thought about these ideas some more. While ideas like CHECK-NOT-{PUSH,POP} might be more general, I'm inclined to believe that CHECK-DAG-NEXT blocks and CHECK-DAG-SAME blocks could be significantly more user-friendly for the use cases we've been discussing. In any case, before anyone starts implementing one of these ideas, we should probably discuss the details and reach an agreement.

[thopre]

In D56789#1371929, @jdenny wrote:

In D56789#1371821, @thopre wrote:

[SNIP]

Agreed, something like CHECK-DAG-NEXT would be better suited. The requirement of CHECK-DAG with CHECK-NEXT was mentioned to me by a coworker and I noticed the weird inconsistency regarding whether CHECK-DAG is the first check directives or not and thought I'd fix it. The behaviour we need is indeed reordering without any line not checked for in between using CHECK-DAG is not the right solution. So I guess the correct approach would be to error out on CHECK-DAG with CHECK-NEXT, CHECK-SAME or CHECK-EMPTY, probably with some flag to enable the old behavior while tests are updated.

Possibly so. Given that many of those existing cases were probably intending the stricter behavior, let's first create a better solution for the stricter behavior.

Regarding CHECK-DAG-NEXT, I wonder how it would interact with CHECK-DAG?

I think that any kind of CHECK-DAG* following a different kind of CHECK-DAG* would start a new block such that there's no reordering among blocks. Otherwise, the semantics become very unclear to me.

It seems intuitive that the first match in a CHECK-DAG-NEXT block would have to appear on the line after whatever match came before the block. However, if you don't want that behavior, then I'm not sure how you would express that.

No that makes sense.

Perhaps we should introduce some sort of only-tested region (e.g. CHECK-ONLY-START and CHECK-ONLY-END with better name) where CHECK-DAG inside would still be able to be reordered but only what is tested by a CHECK-DAG is allowed. It could also allow CHECK directive inside which would behave as CHECK-NEXT. How does that sound?

Or would that CHECK inside behave as a CHECK-SAME? In general, how would whitespace be handled? Error or ignored?

Whatever is consistent with the concept of CHECK-DAG-NEXT I guess. Am suddenly wondering whether 2 CHECK-DAG can match on the same line if they don't overlap? Anyway, this is just an idea, we should have a discussion on llvm-dev to gather requirements from people who used CHECK-DAG when they wanted something else and come up with a good design.

What you propose sounds very similar to something I suggested at one point: CHECK-NOT-PUSH and CHECK-NOT-POP. The idea is you would push a pattern into -implicit-check-not so the pattern would be rejected among matches between the push and the pop. This would be useful in any context where you want -implicit-check-not but don't want it for the entire input.

Oh nice, it would be useful indeed.

To achieve something like CHECK-DAG-SAME, the pattern would specify a single newline, and you'd put CHECK-DAG directives in between the push and pop. To achieve something like CHECK-DAG-NEXT, you'd do the same but each CHECK-DAG's pattern would be specified to gobble up the next newline. Then again, those two cases might be easier to write and diagnostics might be clearer if we created special-purpose directives, but they could probably be built on the same infrastructure.

If all that makes sense to you, there are some details we could discuss about how CHECK-NOT-PUSH and CHECK-NOT-POP would interact with neighboring CHECK-NOT directives and neighboring matches.

I'd love to participate in the discussion yes. If you create a thread please Cc me.

[jdenny]

In D56789#1377922, @thopre wrote:

Perhaps we should introduce some sort of only-tested region (e.g. CHECK-ONLY-START and CHECK-ONLY-END with better name) where CHECK-DAG inside would still be able to be reordered but only what is tested by a CHECK-DAG is allowed. It could also allow CHECK directive inside which would behave as CHECK-NEXT. How does that sound?

Or would that CHECK inside behave as a CHECK-SAME? In general, how would whitespace be handled? Error or ignored?

Whatever is consistent with the concept of CHECK-DAG-NEXT I guess. Am suddenly wondering whether 2 CHECK-DAG can match on the same line if they don't overlap?

Yep:

$ cat check 
CHECK-DAG: abc
CHECK-DAG: def
$ echo 'def abc' | ./bin/FileCheck -v -dump-input=always check |& tail -5
<<<<<<
       1: def abc
dag:1         ^~~
dag:2     ^~~
>>>>>>

Anyway, this is just an idea, we should have a discussion on llvm-dev to gather requirements from people who used CHECK-DAG when they wanted something else and come up with a good design.

Agreed. Would you like to lead that discussion? While I'm happy to comment, I don't have time for much more here at the moment.

[thopre]

As suggested by Joel, I'll start a discussion on llvm-dev to solve the real issue.

llvm/docs/CommandGuide/FileCheck.rst

 In this case, we're testing that we get the expected code generation with
 both 32-bit and 64-bit code generation.
 
 The "CHECK-NEXT:" directive
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Sometimes you want to match lines and would like to verify that matches
 happen on exactly consecutive lines with no other lines in between them.  In
-this case, you can use "``CHECK:``" and "``CHECK-NEXT:``" directives to specify
-this.  If you specified a custom check prefix, just use "``<PREFIX>-NEXT:``".
-For example, something like this works as you'd expect:
+this case, you can use "``CHECK-NEXT:``" directives to specify this.  If you
+specified a custom check prefix, just use "``<PREFIX>-NEXT:``". For example,
+something like this works as you'd expect:
 
 .. code-block:: llvm
 
    define void @t2(<2 x double>* %r, <2 x double>* %A, double %B) {
    %tmp3 = load <2 x double>* %A, align 16
    %tmp7 = insertelement <2 x double> undef, double %B, i32 0
    %tmp9 = shufflevector <2 x double> %tmp3,
                                <2 x double> %tmp7,
                                <2 x i32> < i32 0, i32 2 >
    store <2 x double> %tmp9, <2 x double>* %r, align 16
   ret void
 
    ; CHECK:          t2:
    ; CHECK:           movl  8(%esp), %eax
    ; CHECK-NEXT:  movapd  (%eax), %xmm0
    ; CHECK-NEXT:  movhpd  12(%esp), %xmm0
    ; CHECK-NEXT:  movl  4(%esp), %eax
    ; CHECK-NEXT:  movapd  %xmm0, (%eax)
    ; CHECK-NEXT:  ret
    }
 
 "``CHECK-NEXT:``" directives reject the input unless there is exactly one
 newline between it and the previous directive.  A "``CHECK-NEXT:``" cannot be
-the first directive in a file.
+the first positive directive (i.e. if removing all "``CHECK-NOT``" directives)
+in a file.
+
+If the previous directive is a "``CHECK-DAG``", the "``CHECK-NEXT``" will be
+relative to the "``CHECK-DAG``" that was matched last in the input file.
 
 The "CHECK-SAME:" directive
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Sometimes you want to match lines and would like to verify that matches happen
-on the same line as the previous match.  In this case, you can use "``CHECK:``"
-and "``CHECK-SAME:``" directives to specify this.  If you specified a custom
+on the same line as the previous match.  In this case, you can use
+"``CHECK-SAME:``" directives to specify this.  If you specified a custom
 check prefix, just use "``<PREFIX>-SAME:``".
 
 "``CHECK-SAME:``" is particularly powerful in conjunction with "``CHECK-NOT:``"
 (described below).
 
 For example, the following works like you'd expect:
 
 .. code-block:: llvm
 
    !0 = !DILocation(line: 5, scope: !1, inlinedAt: !2)
 
    ; CHECK:       !DILocation(line: 5,
    ; CHECK-NOT:               column:
    ; CHECK-SAME:              scope: ![[SCOPE:[0-9]+]]
 
 "``CHECK-SAME:``" directives reject the input if there are any newlines between
 it and the previous directive.  A "``CHECK-SAME:``" cannot be the first
-directive in a file.
+positive directive (i.e. if removing all "``CHECK-NOT``" directives) in a file.
+
+If the previous directive is a "``CHECK-DAG``", the "``CHECK-SAME``" will be
+relative to the "``CHECK-DAG``" that was matched last in the input file.
 
 The "CHECK-EMPTY:" directive
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 If you need to check that the next line has nothing on it, not even whitespace,
 you can use the "``CHECK-EMPTY:``" directive.
 
 .. code-block:: llvm
 
    declare void @foo()
 
    declare void @bar()
    ; CHECK: foo
    ; CHECK-EMPTY:
    ; CHECK-NEXT: bar
 
 Just like "``CHECK-NEXT:``" the directive will fail if there is more than one
 newline before it finds the next blank line, and it cannot be the first
-directive in a file.
+positive directive in a file.
 
 The "CHECK-NOT:" directive
 ~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 The "``CHECK-NOT:``" directive is used to verify that a string doesn't occur
 between two matches (or before the first match, or after the last match).  For
 example, to verify that a load is removed by a transformation, a test like this
 can be used:
.. code-block:: text
     //
     // CHECK-DAG: [[THREAD_ID:[0-9]+]]: task_begin
     // CHECK-DAG: [[THREAD_ID]]: task_end
 
 The second pair of directives is guaranteed not to match the same log entries
 as the first pair even though the patterns are identical and even if the text
 of the log entries is identical because the thread ID manages to be reused.
 
+When a DAG block is followed by a ``CHECK-SAME``, ``CHECK-NEXT`` or
+``CHECK-EMPTY`` directive, those will search relative to the DAG directive that
+matches last in the input file. In other words:
+
+.. code-block:: text
+
+    // CHECK-DAG: mov r0, #0
+    // CHECK-DAG: mov r1, #1
+    // CHECK-NEXT: add r2, r0, r1
+
+will successfully match with the input:
+
+.. code-block:: text
+
+    mov r1, #1
+    mov r0, #0
+    add r2, r0, r1
+
+``CHECK-DAG: mov r0, #0`` is the last DAG line from the DAG block matched in
+the input file so the CHECK-NEXT is relative to that line.
+
 The "CHECK-LABEL:" directive
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Sometimes in a file containing multiple tests divided into logical blocks, one
 or more ``CHECK:`` directives may inadvertently succeed by matching lines in a
 later block. While an error will usually eventually be generated, the check
 flagged as causing the error may not actually bear any relationship to the
 actual source of the problem.

llvm/lib/Support/FileCheck.cpp

if ((CheckTy == Check::CheckLabel) && P.hasVariable()) {
           SMLoc::getFromPointer(UsedPrefixStart), SourceMgr::DK_Error,
           "found '" + UsedPrefix + "-LABEL:'"
                                    " with variable definition or use");
       return true;
     }
 
     Buffer = Buffer.substr(EOL);
 
-    // Verify that CHECK-NEXT/SAME/EMPTY lines have at least one CHECK line before them.
+    // Verify that CHECK-NEXT/SAME/EMPTY lines have at least one positive CHECK
+    // line (i.e. something else than CHECK-NOT) before them.
     if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckSame ||
          CheckTy == Check::CheckEmpty) &&
-        CheckStrings.empty()) {
+        CheckStrings.empty() &&
+        std::none_of(DagNotMatches.begin(), DagNotMatches.end(),
+                     [](FileCheckPattern DagNotMatch) {
+                       return DagNotMatch.getCheckTy() == Check::CheckDAG;
+                     })) {
       StringRef Type = CheckTy == Check::CheckNext
                            ? "NEXT"
                            : CheckTy == Check::CheckEmpty ? "EMPTY" : "SAME";
       SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
                       SourceMgr::DK_Error,
                       "found '" + UsedPrefix + "-" + Type +
                           "' without previous '" + UsedPrefix + ": line");
       return true;

llvm/test/FileCheck/check-dag.txt

-; RUN: FileCheck -input-file %s %s
+; RUN: FileCheck -check-prefixes CHECK,STD -input-file %s %s
+; RUN: FileCheck -check-prefixes CHECK,SAME -input-file %s %s
+; RUN: FileCheck -check-prefixes CHECK,NEXT -input-file %s %s
 
 add r10, r1, r2
 add r11, r3, r4
 mul r5, r10, r11
 
 mul r11, r3, r4
 mul r10, r1, r2
 add r5, r10, r11
 
 add r11, r3, r4
 add r10, r1, r2
 mul r5, r10, r11
 
 # begin
 # end
 xor
 
 ; CHECK-DAG: add [[REG1:r[0-9]+]], r1, r2
-; CHECK-DAG: add [[REG2:r[0-9]+]], r3, r4
-; CHECK: mul r5, [[REG1]], [[REG2]]
+; CHECK-DAG: add [[REG2:r[0-9]+]], r3,
+; STD: mul r5, [[REG1]], [[REG2]]
+; SAME-SAME: r4
+; NEXT-NEXT: mul r5, [[REG1]], [[REG2]]
 
-; CHECK-DAG: mul [[REG1:r[0-9]+]], r1, r2
+; CHECK-DAG: mul [[REG1:r[0-9]+]], r1,
 ; CHECK-DAG: mul [[REG2:r[0-9]+]], r3, r4
-; CHECK: add r5, [[REG1]], [[REG2]]
+; STD: add r5, [[REG1]], [[REG2]]
+; SAME-SAME: r2
+; NEXT-NEXT: add r5, [[REG1]], [[REG2]]
 
 ; CHECK-DAG: add [[REG1:r[0-9]+]], r1, r2
 ; CHECK-DAG: add [[REG2:r[0-9]+]], r3, r4
 ; CHECK-NOT: xor
 ; CHECK-DAG: mul r5, [[REG1]], [[REG2]]
 
 ; CHECK-DAG: begin
 ; CHECK-NOT: xor
 ; CHECK-DAG: end
 ; CHECK: xor