[FileCheck] Make CHECK-DAG non-overlapping

[jdenny]

Summary

That is, make CHECK-DAG skip matches that overlap the matches of any
preceding consecutive CHECK-DAG directives. This change makes
CHECK-DAG more consistent with other directives, and there is evidence
it makes CHECK-DAG more intuitive and less error-prone. See the RFC
discussion starting at:

http://lists.llvm.org/pipermail/llvm-dev/2018-May/123010.html

Moreover, this behavior enables CHECK-DAG groups for unordered,
non-unique strings or patterns. For example, it is useful for
verifying output or logs from a parallel program, such as the OpenMP
runtime.

This patch also implements the command-line option
-allow-deprecated-dag-overlap, which reverts CHECK-DAG to the old
overlapping behavior. This option should not be used in new tests.
It is meant only for the existing tests that are broken by this change
and that need time to update.

See the following bugzilla issue for tracking of such tests:

https://bugs.llvm.org/show_bug.cgi?id=37532

This patch should not be committed until we have patches ready to add
-allow-deprecated-dag-overlap to those tests.

[jdenny]

Fixed some minor typos.

I still need to add -allow-deprecated-dag-overlap to tests. I'm going to create separate patches for that so that this patch stays readable.

[probinson]

test/FileCheck/check-dag-overlap.txt

12 ↗

(On Diff #147664)

Ordinarily these delimiters would be using -LABEL; is there some reason not to?

34 ↗

(On Diff #147664)

Normally I'd say a single DAG after a NOT is more misleading than helpful; unless you changed some behavior here?

165 ↗

(On Diff #147664)

Please move the Torture part into its own test file. I'm finding it hard to keep track well enough to review.

467 ↗

(On Diff #147664)

Reading this in the overlapping mode: The X set of DAGs will all match on line 424, the Y set will all match on line 425, therefore the NOTs for rule 1 will correctly not match anything. The Z set of DAGs will all match on line 428, therefore the NOTs for rule 2 will correctly not match anything. Then the NOTs for rule 3 will match, making the run fail.

Is that what you intended? Naively I would have thought you'd try to break each of the rules, but that's not what the test does.

[jdenny]

test/FileCheck/check-dag-overlap.txt

12 ↗

(On Diff #147664)

I was mimicking check-dag-xfails.txt. I was thinking -LABEL wouldn't work well because each RUN would see only one -LABEL, but I suppose all RUNs could share a common CHECK prefix for -LABEL. I'll work on that. Thanks.

34 ↗

(On Diff #147664)

I was just trying to prove that this case is handled sanely when overlapping matches must be skipped. I don't mean to imply anything about whether it's a good way to write test cases.

165 ↗

(On Diff #147664)

Will do.

467 ↗

(On Diff #147664)

Reading this in the overlapping mode: The X set of DAGs will all match on line 424,

Yes.

the Y set will all match on line 425

No. y also matches on line 424 because overlapping is permitted, so we get a reordering complaint. You can confirm this with the -vv option.

Is that what you intended? Naively I would have thought you'd try to break each of the rules, but that's not what the test does.

It breaks the first rule because of -allow-deprecated-dag-overlap.

With non-overlapping matches, it breaks the second rule if I remove the following line from CheckString::CheckDag:

Matches.push_back(Match{MatchPos, MatchPos + MatchLen})

(I had that bug at one point.)

While rule 3 is exercised, I don't know how to break it without breaking rule 1 or 2 because it's a consequence of rules 1 and 2.

[probinson]

test/FileCheck/check-dag-overlap.txt

12 ↗

(On Diff #147664)

Oh, makes sense, yes. Never mind the -LABEL stuff if you haven't already done it. The test will be easier to read if you don't mix CHECK in with the run-specific prefix names.

34 ↗

(On Diff #147664)

OK.

467 ↗

(On Diff #147664)

the Y set will all match on line 425

No. y also matches on line 424 because overlapping is permitted, so we get a reordering complaint. You can confirm this with the -vv option.

Huh. I would have expected the -NOT directives for rule 1 to break up the DAG lines into separate X and Y groups, and the Y group's starting position would necessarily have been the end of the X group's last match.
At least, that appears to be the intended behavior of the IdentPatNot part of the test?
I admit I have not downloaded and applied the patches, I'll try to do that tomorrow.

[jdenny]

test/FileCheck/check-dag-overlap.txt

12 ↗

(On Diff #147664)

No, I haven't started. I'll skip this one then.

467 ↗

(On Diff #147664)

The reordering check is a bit odd, regardless of my patch. It looks for y from the start of X, but it looks for the rest of Y from the end of X. My patch makes sure y doesn't overlap with members of X.

[jdenny]

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

Speaking of the reordering check, we should discuss this comment change.

I made this change to reflect the implementation, but now I'm wondering if the comment described the desired behavior and the implementation was wrong. I'm not really sure. Moreover, this comment change does not reflect any change made by this patch, so perhaps it should be in a separate patch.

The implementation works as follows (with or without this patch as there's no overlapping here). Using the X-Y model from earlier, the implementation seeks non-initial members of Y from the end of X rather than the start of Y. For example, the following succeeds even though the second member of Y matches before the first member of Y:

X:
abc

Y:
ghi
def
foo
jkl

X:
CHECK-DAG: {{^}}abc

CHECK-NOT: {{^}}foo

Y:
CHECK-DAG: {{^}}def
CHECK-DAG: {{^}}ghi
CHECK-DAG: {{^}}jkl

To make things more confusing, if I move the occurrence of foo right before the occurrence of def, the CHECK-NOT fails. That is, the CHECK-NOTs are sought before the first member of Y, but the other members of Y are sought both before and after Y. It might be more intuitive if the first member of Y marks the beginning of Y (as the comment originally claimed) so that CHECK-NOTs are sought strictly between all of X and all of Y.

[probinson]

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

My understanding of putting NOT between DAGs is this:

X:
abc
Y:
ghi
def
foo
jkl

X:
CHECK-DAG: b
CHECK-DAG: a

CHECK-NOT: foo

Y:
CHECK-DAG: def
CHECK-DAG: ghi

First the X group of DAGs runs, over the entire input text. The farthest-forward match (here 'b') is remembered.
Then the Y group of DAGs runs, from the farthest-forward X match (i.e., after 'b') to the end of the input text. The earliest match (here 'ghi') is remembered.
Finally the NOT runs, in the range from the end of the X matches (after 'b') to the beginning of the earliest Y match (before 'ghi').

The X matches and the Y matches can never overlap, even though they are both DAG groups they are separated by the NOT. Therefore the search range of the Y group is constrained to start after the latest match of the X group.

Is that not what happens? Even with overlapping DAG matches enabled? Your explanation made it sound as if you expected the order of DAG directives in Y to make a difference to the NOT directive, when I think it should not.

[jdenny]

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

First the X group of DAGs runs, over the entire input text. The farthest-forward match (here 'b') is remembered.

Agreed.

Then the Y group of DAGs runs, from the farthest-forward X match (i.e., after 'b') to the end of the input text.
The earliest match (here 'ghi') is remembered.

Only the first DAG in Y runs at this point, so 'def' is remembered.

Finally the NOT runs, in the range from the end of the X matches (after 'b') to the beginning of the earliest Y match (before 'ghi').

Before 'def'.

The X matches and the Y matches can never overlap, even though they are both DAG groups they are separated by the NOT. Therefore the search range of the Y group is constrained to start after the latest match of the X group.

Agreed.

Is that not what happens? Even with overlapping DAG matches enabled?

My patch and -allow-deprecated-dag-overlap shouldn't affect these examples as there is no overlapping.

Your explanation made it sound as if you expected the order of DAG directives in Y to make a difference to the NOT directive, when I think it should not.

It does make a difference, and I agree it's not intuitive.

[probinson]

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

It is so unintuitive that I would call it a bug. The question is whether to fix that first, before doing the no-overlapping bit. Do you think it would be straightforward, or a big deal?

[jdenny]

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

I see two possible fixes:

1. One approach is what the original comment here suggested: make the first DAG in Y mark the beginning of all Y matches. Basically, for that first directive in Y, CHECK-DAG becomes CHECK. This approach seems very quick to implement. However, it constrains what DAGs in Y can match, so it might break existing tests.

2. Another approach is to do what you described: match all DAGs in Y and then make the earliest match delimit the end of the preceding NOTs. That will require more work to implement, I think. However, it doesn't constrain what DAGs in Y can match. Instead, it constrains what the preceding NOTs can match, and constraining NOTs helps tests pass not fail. The question is whether they will be false passes that we'll never hear about. My hunch is no.

While #2 seems harder to implement, it seems like it wouldn't causes tests to fail, and I think it produces more intuitive behavior. What do you think?

Therefore the search range of the Y group is constrained to start after the latest match of the X group.

Agreed.

I got confused here. The search range of the first DAG in Y starts where X's search range starts not where X's matches end. Otherwise, there would be no possibility of a reordering complaint.

[probinson]

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

While #2 seems harder to implement, it seems like it wouldn't causes tests to fail, and I think it produces more intuitive behavior. What do you think?

I think a group of DAGs should not behave differently just because it is preceded by a NOT, and so I still prefer #2.

I got confused here. The search range of the first DAG in Y starts where X's search range starts not where X's matches end. Otherwise, there would be no possibility of a reordering complaint.

That suggests that the first DAG in Y is being mis-handled as part of the X group. I don't think that makes any sense at all. Either a NOT cleanly separates the surrounding DAGs into two groups, or they are all part of one bigger group. Taking the lexically first DAG from the second group and moving it to the first group is just wrong.

[jdenny]

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

I think a group of DAGs should not behave differently just because it is preceded by a NOT, and so I still prefer #2.

Agreed. I'll look into it. If it doesn't break anything, we can put it in before this patch.

So that I can keep this straight: The above is about the search range end for the NOTs before Y. The below is about the search range start for Y and thus reordering detection.

I got confused here. The search range of the first DAG in Y starts where X's search range starts not where X's matches end. Otherwise, there would be no possibility of a reordering complaint.

That suggests that the first DAG in Y is being mis-handled as part of the X group. I don't think that makes any sense at all. Either a NOT cleanly separates the surrounding DAGs into two groups, or they are all part of one bigger group. Taking the lexically first DAG from the second group and moving it to the first group is just wrong.

I agree the current reordering detection is broken. I think the two options you are proposing are the following:

1. Search for every DAG in Y from the end of X's matches until EOF. That would make reordering detection impossible, so we could just get rid of it.

2. Search for every DAG in Y from the start of X's matches until EOF. That way, reordering is detected for any Y member not just the first.

Is that what you mean? Which do you prefer?

[jdenny]

This splits the test case, as requested.

[probinson]

(Replying here instead of inline as the thread is getting kind of long.)

Sorry, I didn't realize FileCheck would try to detect and explicitly diagnose reordering DAG across NOT. That seems like more trouble than it's worth. NOT is documented to enforce ordering, and we can make it just do that, and if you mess up then your test fails by not matching rather than telling you something is in the wrong order. (Then you can use -v or -vv to work out what happened, if you need to.)

Once we define the DAGs as separated into distinct groups by a NOT, I think it's conceptually straightforward to say each DAG group has a "matching range" from the start of the earliest match to the end of the latest match. Two DAG groups can't have overlapping match ranges (just like you are making individual DAG matches not overlap).

Defining the search range of a DAG group does get a little fuzzy when it's not bounded by a normal CHECK. I think when that happens, we say it goes to the next LABEL, or start/end of file.

Similarly, if you have a NOT group, its range is bounded by the previous match (or last match of a preceding DAG group), and the following match (or first match of a following DAG group).

At that point, I think the behavior becomes tractable. The first DAG group finds what it finds, the NOT forces no reordering therefore the second DAG group's range starts at the endpoint of the first group's matches. After the second DAG group runs, the NOT's range is from the endpoint of the first group's matches to the earliest of the second group's matches.

How does that all sound? If we can agree on this behavior, then probably I should write it up for the dev list to get a broader audience, before launching ahead with the implementation. But (if I do say so myself) I think this kind of conceptual model has been lacking in FileCheck as it has grown new features, and it's worth laying it out explicitly.

[jdenny]

In D47106#1110240, @probinson wrote:

(Replying here instead of inline as the thread is getting kind of long.)

Sorry, I didn't realize FileCheck would try to detect and explicitly diagnose reordering DAG across NOT. That seems like more trouble than it's worth. NOT is documented to enforce ordering, and we can make it just do that, and if you mess up then your test fails by not matching rather than telling you something is in the wrong order. (Then you can use -v or -vv to work out what happened, if you need to.)

Once we define the DAGs as separated into distinct groups by a NOT, I think it's conceptually straightforward to say each DAG group has a "matching range" from the start of the earliest match to the end of the latest match. Two DAG groups can't have overlapping match ranges (just like you are making individual DAG matches not overlap).

I think we should try to understand why reordering detection was implemented in the first place. I've imagined hypothetical examples where it could help, but I don't know if they occur in real tests. I generally have a hard time knowing what the right use cases for DAG-NOT-DAG are, and I imagine that's part of the motivation of the reordering detection: to help people not use it incorrectly. All of that can be part of the llvm-dev discussion you suggest.

Defining the search range of a DAG group does get a little fuzzy when it's not bounded by a normal CHECK. I think when that happens, we say it goes to the next LABEL, or start/end of file.

Yes, I believe that's what happens now.

Similarly, if you have a NOT group, its range is bounded by the previous match (or last match of a preceding DAG group), and the following match (or first match of a following DAG group).

Yes, we've agreed on that, and I've tinkered some with fixing the end of the range when followed by a DAG group. I think knowing whether that breaks existing tests would be helpful in any further discussion on that point.

At that point, I think the behavior becomes tractable. The first DAG group finds what it finds, the NOT forces no reordering therefore the second DAG group's range starts at the endpoint of the first group's matches. After the second DAG group runs, the NOT's range is from the endpoint of the first group's matches to the earliest of the second group's matches.

How does that all sound?

The main question remaining for me is about the start of the second DAG group's match range and thus whether reordering detection happens.

If we can agree on this behavior, then probably I should write it up for the dev list to get a broader audience, before launching ahead with the implementation.

I'm certainly fine with an llvm-dev discussion.

But (if I do say so myself) I think this kind of conceptual model has been lacking in FileCheck as it has grown new features, and it's worth laying it out explicitly.

Agreed.

[jdenny]

Ping.

Rebased. The number of tests broken by this change in functionality continues to grow. Can we move forward?

[probinson]

Sorry, will get back to the FileCheck stuff first thing tomorrow.

[probinson]

Regarding the DAG-NOT-DAG reordering diagnostic: Rereading the comments, and the llvm-dev discussion, are we agreed that we can eliminate it? That is, the first DAG group defines some match range, the second DAG group defines a disjoint match range, and the NOT group looks at the text from the end of the first match range to the start of the second match range. No attempt to diagnose ordering problems.

I also have some fussy comments about the torture test inline.

test/FileCheck/check-dag-overlap-torture.txt

24 ↗

(On Diff #153774)

The latest revision of the conceptual model says we won't allow SAME or NEXT after DAG. For purposes of determining valid/invalid directive sequences, the NOT wouldn't count. I think you still get the intended result without the SAME suffix.
I see you're wanting to (in effect) have intra-line DAG, but DAG doesn't provide that guarantee.

36 ↗

(On Diff #153774)

This is the first set of checks where there's a difference in behavior depending on overlap or not. Given the test is trying to exercise exactly that, the first two sets of checks aren't useful. (They might be appropriate for a general DAG functionality test, but not here.)

42 ↗

(On Diff #153774)

This set of checks appears to be redundant with the previous >xyz set (the overlap is 3 characters instead of 1 but so what).

60 ↗

(On Diff #153774)

This set of checks appears to be redundant with the previous c<mno>xyz set.

67 ↗

(On Diff #153774)

I skimmed the rest of the checks, and offhand the comments on the EndAfterEnd part likely apply to the other parts: (a) don't bother with sets of checks that don't overlap; (b) don't bother with redundant sets of checks that vary only in the number of overlapping characters.

[jdenny]

In D47106#1150943, @probinson wrote:

Regarding the DAG-NOT-DAG reordering diagnostic: Rereading the comments, and the llvm-dev discussion, are we agreed that we can eliminate it? That is, the first DAG group defines some match range, the second DAG group defines a disjoint match range, and the NOT group looks at the text from the end of the first match range to the start of the second match range. No attempt to diagnose ordering problems.

Agreed. I have a patch to implement that. I'll clean it up and post it after we've cleared some of the existing queue. It applies afterward.

I also have some fussy comments about the torture test inline.

Thanks for the review. I'm replying inline.

test/FileCheck/check-dag-overlap-torture.txt

24 ↗

(On Diff #153774)

The latest revision of the conceptual model says we won't allow SAME or NEXT after DAG. For purposes of determining valid/invalid directive sequences, the NOT wouldn't count. I think you still get the intended result without the SAME suffix.

Generally speaking, CHECK and CHECK-SAME always behave the same when the output is as expected for CHECK-SAME, right? When the output is not as expected for CHECK-SAME, CHECK could match the same text on a later line, potentially delaying or eliminating the desired diagnostic.

I see you're wanting to (in effect) have intra-line DAG, but DAG doesn't provide that guarantee.

Yes, that's what I want. We don't have it, so I went for the next best thing.

Until we have an intra-line DAG, I'd like to request that we don't implement the restriction for SAME after DAG.

Even if we do implement an intra-line DAG, my gut says the SAME/NEXT after DAG restrictions eliminate reasonable use cases, but I don't have real-world examples right now, so I won't oppose the restrictions unless I come up with some examples.

36 ↗

(On Diff #153774)

I intended for this test file to exhaustively exercise overlap detection. That includes checking for both false positives and false negatives.

I see no reason to eliminate checking for false positives just because those cases behaved the same when we permitted overlaps. I want to check that overlap detection works correctly in all cases now.

42 ↗

(On Diff #153774)

I'm just doing boundary testing. None is a different class than one is a different class than multiple. Why is one different than multiple? Because off-by-one is a common bug that might cause incorrect behavior or mask another bug.

I don't see the advantage of removing this.

60 ↗

(On Diff #153774)

Again, I'm doing boundary testing, but on the match start: 44-48 (none past the start), 50-54 (one past the start), 56-60 (multiple past the start).

[probinson]

test/FileCheck/check-dag-overlap-torture.txt

24 ↗

(On Diff #153774)

Regarding SAME/NEXT after DAG, I do not have a strong opinion. The question is mainly whether it will make sense to people who do not spend a lot of time studying how FileCheck works. I'm okay with leaving them in.

36 ↗

(On Diff #153774)

Do you anticipate deleting this test when the overlap feature is removed? If so, I won't argue about its content (much).

42 ↗

(On Diff #153774)

In the case of string pattern matching I disagree that one is a different class than multiple. I see it as a ternary <=> result, and it doesn't matter how far unequal the substring boundaries are.
The advantage to removing it is that it's one less case for a human to understand when reading the test.

[jdenny]

test/FileCheck/check-dag-overlap-torture.txt

24 ↗

(On Diff #153774)

Regarding SAME/NEXT after DAG, I do not have a strong opinion. The question is mainly whether it will make sense to people who do not spend a lot of time studying how FileCheck works.

Your formalized description is what gives me hope that we can describe these behaviors in a way that people will understand, but I agree it's better if it's just intuitive without studying documentation.

I'm okay with leaving them in.

In that case, I say we let it be for now. We can revisit after we finish this series of patches and after we consider an intra-line DAG. By then, more concrete examples might arise.

36 ↗

(On Diff #153774)

No, I primarily mean for this test to exercise overlap detection for DAG, which is important as long as non-overlapping is enforced.

42 ↗

(On Diff #153774)

In the case of string pattern matching I disagree that one is a different class than multiple. I see it as a ternary <=> result, and it doesn't matter how far unequal the substring boundaries are.

It might not matter in one particular correct implementation, but it can matter in subtle ways as implementations evolve clever new techniques and break.

The advantage to removing it is that it's one less case for a human to understand when reading the test.

I don't agree that removing the tests for the "multiple cases" is going to make this test file substantially easier to understand. Once you understand the general sequence of tests here, understanding the difference between one and many seems like very little more to ask. I'm happy to add comments if you feel that would help.

Obviously, there are no hard rules on how to design test cases effectively, so we write them based on our own experiences and on general guidelines about things like off-by-one. In the past, I've spent a lot of time writing tests for parsers, and I've found that carefully testing boundary conditions in this way is important.

I feel pretty strongly about this, but I don't want to have to stall this patch indefinitely because we have different views on proper testing. If you're adamant, I'll defer. Alternatively, we could invite a third opinion to break the tie. You can pick whomever.

[probinson]

test/FileCheck/check-dag-overlap-torture.txt

36 ↗

(On Diff #153774)

That's fine (clearly we'd remove the RUN lines with the deprecated switch, when that gets removed).
But in that case, there are already a bunch of tests for non-overlapping DAG lines in other check-dag*.txt tests, and it distracts from the focus of this test to repeat them here. That would be the first two sets of checks in EndAfterEnd, and corresponding sets in the other cases.
(Or if you think the existing DAG tests in the other files are inadequate, beef up those tests, and keep this one focused on overlap.)

[jdenny]

test/FileCheck/check-dag-overlap-torture.txt

36 ↗

(On Diff #153774)

That's fine (clearly we'd remove the RUN lines with the deprecated switch, when that gets removed).

Right.

But in that case, there are already a bunch of tests for non-overlapping DAG lines in other check-dag*.txt tests, and it distracts from the focus of this test to repeat them here. That would be the first two sets of checks in EndAfterEnd, and corresponding sets in the other cases.
(Or if you think the existing DAG tests in the other files are inadequate, beef up those tests, and keep this one focused on overlap.)

I see check-dag-overlap-torture.txt as a careful, organized sweep through all the various cases basic overlap detection must handle. In my opinion, dropping chunks of it that happen to be covered for some other purpose elsewhere makes this test more confusing, and it makes the overall testing of overlap detection less maintainable. I don't think those chunks distract from the focus of this test because the focus of this test is the correct behavior of the overlapping detection mechanism, and that includes no false positives, especially at boundary conditions.

As in the discussion of one vs. multiple, I'm pretty adamant, and I don't feel like we're converging. Just give me the word, and I'll yield, or you can invite a third opinion if you know someone who might offer another perspective.

I'm not trying to be difficult on these points. I just disagree. But I'd still like us to find a path forward. A third person might help.

[jdenny]

In D47106#1110343, @jdenny wrote:

In D47106#1110240, @probinson wrote:

At that point, I think the behavior becomes tractable. The first DAG group finds what it finds, the NOT forces no reordering therefore the second DAG group's range starts at the endpoint of the first group's matches. After the second DAG group runs, the NOT's range is from the endpoint of the first group's matches to the earliest of the second group's matches.

How does that all sound?

The main question remaining for me is about the start of the second DAG group's match range and thus whether reordering detection happens.

For the record, I'm pretty sure I meant search range here. We didn't have formal definitions for that terminology yet, and I must have gotten it confused.

test/FileCheck/check-dag-overlap-torture.txt

42 ↗

(On Diff #153774)

To be clear, when I say "I'll yield" or "I'll defer", I mean that I'm willing to do as you ask in order to proceed. Of course, I'd rather us reach agreement on what's right, but it doesn't seem like we're making arguments that are persuasive to each other, so I suggested the alternative of inviting a third person, and I'm hoping you know someone.

test/FileCheck/check-dag-overlap.txt

467 ↗

(On Diff #147664)

We never really resolved this issue. Given our agreement about how DAG-NOT-DAG will work in the future (as described in your formal model, and as I've implemented in a patch I still need to post), I believe the only aspects of this test that must change are the comments about reordering detection... because there will be no more reordering detection.

Otherwise, I'm inclined to think this test still makes sense because it exercises overlapping cases that used to be mishandled. Does that make sense to you?

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

I think the only issues left to address in this thread are: (1) remove reordering detection and fix search ranges, and (2) update accordingly the comment that this thread was originally discussing. Again, #1 happens in a later patch I still need to post, and #2 will be addressed there too. Before that patch, the comment change as it appears above is accurate, so I think I should just leave it be for now. For those reasons, I'm marking these comments as done, but let me know if you disagree.

[probinson]

Given that you feel so very strongly about it, and that this is a tool that really has absolutely zero exposure outside our own test system, I'm willing to say that erring on the side of extra testing is acceptable here.

test/FileCheck/check-dag-overlap-torture.txt

42 ↗

(On Diff #153774)

Actually I appreciate the devotion to thorough testing.

test/FileCheck/check-dag-overlap.txt

467 ↗

(On Diff #147664)

Okay, sounds good.

utils/FileCheck/FileCheck.cpp

1245 ↗

(On Diff #147918)

No, that's fair.

[jdenny]

In D47106#1156353, @probinson wrote:

Given that you feel so very strongly about it, and that this is a tool that really has absolutely zero exposure outside our own test system, I'm willing to say that erring on the side of extra testing is acceptable here.

Hi Paul. Thanks very much for your consideration. I apologize for being difficult.

There are 3 more patches that this patch depends upon:

https://reviews.llvm.org/D47326
https://reviews.llvm.org/D47172
https://reviews.llvm.org/D47171

Those need to be committed at the same time as this one to avoid lots of buildbot failures. They're large but simple-minded patches: I just blindly added -allow-deprecated-dag-overlap to tests that break after adding this patch. Given that there are many run lines per test, it's possible that some additions weren't actually necessary, but they don't cause new unexpected failures for me, and our plan was to investigate these tests one by one afterward anyway. I'm currently pulling, rebasing, and re-running tests locally. I'll extend those patches for any new failures afterward.

Would you please accept those patches as well? Combing through every line might be a lot to ask, so you could accept on the condition that I actually did what I said I did, and I'll take responsibility for any problems.

Thanks again.

[probinson]

The mechanical changes to the tests are actually pretty easy to skim through, given the way Phabricator's web interface does change highlighting. The three you cited are all fine.

[jdenny]

In D47106#1157397, @probinson wrote:

The mechanical changes to the tests are actually pretty easy to skim through, given the way Phabricator's web interface does change highlighting. The three you cited are all fine.

Thanks! I'll commit once I get a successful build and test suite run, hopefully today.

llvm/trunk/docs/CommandGuide/FileCheck.rst

.. option:: -D<VAR=VALUE>
 
   Sets a filecheck variable ``VAR`` with value ``VALUE`` that can be used in
   ``CHECK:`` lines.
 
 .. option:: -version
 
  Show the version number of this program.
 
+.. option:: --allow-deprecated-dag-overlap
+
+  Enable overlapping among matches in a group of consecutive ``CHECK-DAG:``
+  directives.  This option is deprecated and is only provided for convenience
+  as old tests are migrated to the new non-overlapping ``CHECK-DAG:``
+  implementation.
+
 EXIT STATUS
 -----------
 
 If :program:`FileCheck` verifies that the file matches the expected contents,
 it exits with 0.  Otherwise, if not, or if an error occurs, it will exit with a
 non-zero value.
 
 TUTORIAL

 While this can be very useful, it's also dangerous, because in the case of
 register sequence, you must have a strong order (read before write, copy before
 use, etc). If the definition your test is looking for doesn't match (because
 of a bug in the compiler), it may match further away from the use, and mask
 real bugs away.
 
 In those cases, to enforce the order, use a non-DAG directive between DAG-blocks.
 
+A ``CHECK-DAG:`` directive skips matches that overlap the matches of any
+preceding ``CHECK-DAG:`` directives in the same ``CHECK-DAG:`` block.  Not only
+is this non-overlapping behavior consistent with other directives, but it's
+also necessary to handle sets of non-unique strings or patterns.  For example,
+the following directives look for unordered log entries for two tasks in a
+parallel program, such as the OpenMP runtime:
+
+.. code-block:: text
+
+    // CHECK-DAG: [[THREAD_ID:[0-9]+]]: task_begin
+    // CHECK-DAG: [[THREAD_ID]]: task_end
+    //
+    // 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.
+
 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/trunk/test/FileCheck/check-dag-overlap-torture.txt

+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=EndAfterEnd
+; RUN: FileCheck -input-file %s %s -check-prefix=EndAfterEnd
+
+new match end after old match end
+
+__EndAfterEnd
+(abc<mno>xyz)
+(abc<mno>xyz)
+(abc<mno>xyz  >xyz)
+(abc<mno>xyz  no>xyz)
+(abc<mno>xyz  <mno>xyz)
+(abc<mno>xyz  c<mno>xyz)
+(abc<mno>xyz  abc<mno>xyz)
+__EndAfterEnd
+
+; EndAfterEnd:      __EndAfterEnd
+
+; EndAfterEnd:      {{^}}(
+; EndAfterEnd-DAG:  <mno>
+; EndAfterEnd-DAG:  yz
+; EndAfterEnd-NOT:  {{.}}
+; EndAfterEnd-SAME: ){{$}}
+
+; EndAfterEnd:      {{^}}(
+; EndAfterEnd-DAG:  <mno>
+; EndAfterEnd-DAG:  xyz
+; EndAfterEnd-NOT:  {{.}}
+; EndAfterEnd-SAME: ){{$}}
+
+; EndAfterEnd:      {{^}}(
+; EndAfterEnd-DAG:  <mno>
+; EndAfterEnd-DAG:  >xyz
+; EndAfterEnd-NOT:  {{.}}
+; EndAfterEnd-SAME: ){{$}}
+
+; EndAfterEnd:      {{^}}(
+; EndAfterEnd-DAG:  <mno>
+; EndAfterEnd-DAG:  no>xyz
+; EndAfterEnd-NOT:  {{.}}
+; EndAfterEnd-SAME: ){{$}}
+
+; EndAfterEnd:      {{^}}(
+; EndAfterEnd-DAG:  <mno>
+; EndAfterEnd-DAG:  <mno>xyz
+; EndAfterEnd-NOT:  {{.}}
+; EndAfterEnd-SAME: ){{$}}
+
+; EndAfterEnd:      {{^}}(
+; EndAfterEnd-DAG:  <mno>
+; EndAfterEnd-DAG:  c<mno>xyz
+; EndAfterEnd-NOT:  {{.}}
+; EndAfterEnd-SAME: ){{$}}
+
+; EndAfterEnd:      {{^}}(
+; EndAfterEnd-DAG:  <mno>
+; EndAfterEnd-DAG:  abc<mno>xyz
+; EndAfterEnd-NOT:  {{.}}
+; EndAfterEnd-SAME: ){{$}}
+
+; EndAfterEnd:      __EndAfterEnd
+
+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=EndRightAfterEnd
+; RUN: FileCheck -input-file %s %s -check-prefix=EndRightAfterEnd
+
+new match end right after old match end
+
+__EndRightAfterEnd
+(abc<mno>xyz)
+(abc<mno>xyz  >x)
+(abc<mno>xyz  no>x)
+(abc<mno>xyz  <mno>x)
+(abc<mno>xyz  c<mno>x)
+(abc<mno>xyz  abc<mno>x)
+__EndRightAfterEnd
+
+; EndRightAfterEnd:      __EndRightAfterEnd
+
+; EndRightAfterEnd:      {{^}}(
+; EndRightAfterEnd-DAG:  <mno>
+; EndRightAfterEnd-DAG:  x
+; EndRightAfterEnd-NOT:  {{.}}
+; EndRightAfterEnd-SAME: yz){{$}}
+
+; EndRightAfterEnd:      {{^}}(
+; EndRightAfterEnd-DAG:  <mno>
+; EndRightAfterEnd-DAG:  >x
+; EndRightAfterEnd-NOT:  {{.}}
+; EndRightAfterEnd-SAME: ){{$}}
+
+; EndRightAfterEnd:      {{^}}(
+; EndRightAfterEnd-DAG:  <mno>
+; EndRightAfterEnd-DAG:  no>x
+; EndRightAfterEnd-NOT:  {{.}}
+; EndRightAfterEnd-SAME: ){{$}}
+
+; EndRightAfterEnd:      {{^}}(
+; EndRightAfterEnd-DAG:  <mno>
+; EndRightAfterEnd-DAG:  <mno>x
+; EndRightAfterEnd-NOT:  {{.}}
+; EndRightAfterEnd-SAME: ){{$}}
+
+; EndRightAfterEnd:      {{^}}(
+; EndRightAfterEnd-DAG:  <mno>
+; EndRightAfterEnd-DAG:  c<mno>x
+; EndRightAfterEnd-NOT:  {{.}}
+; EndRightAfterEnd-SAME: ){{$}}
+
+; EndRightAfterEnd:      {{^}}(
+; EndRightAfterEnd-DAG:  <mno>
+; EndRightAfterEnd-DAG:  abc<mno>x
+; EndRightAfterEnd-NOT:  {{.}}
+; EndRightAfterEnd-SAME: ){{$}}
+
+; EndRightAfterEnd:      __EndRightAfterEnd
+
+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=EndAtEnd
+; RUN: FileCheck -input-file %s %s -check-prefix=EndAtEnd
+
+new match end at old match end
+
+__EndAtEnd
+(abc<mno>xyz  >)
+(abc<mno>xyz  no>)
+(abc<mno>xyz  <mno>)
+(abc<mno>xyz  c<mno>)
+(abc<mno>xyz  abc<mno>)
+__EndAtEnd
+
+; EndAtEnd:      __EndAtEnd
+
+; EndAtEnd:      {{^}}(
+; EndAtEnd-DAG:  <mno>
+; EndAtEnd-DAG:  >
+; EndAtEnd-NOT:  {{.}}
+; EndAtEnd-SAME: ){{$}}
+
+; EndAtEnd:      {{^}}(
+; EndAtEnd-DAG:  <mno>
+; EndAtEnd-DAG:  no>
+; EndAtEnd-NOT:  {{.}}
+; EndAtEnd-SAME: ){{$}}
+
+; EndAtEnd:      {{^}}(
+; EndAtEnd-DAG:  <mno>
+; EndAtEnd-DAG:  <mno>
+; EndAtEnd-NOT:  {{.}}
+; EndAtEnd-SAME: ){{$}}
+
+; EndAtEnd:      {{^}}(
+; EndAtEnd-DAG:  <mno>
+; EndAtEnd-DAG:  c<mno>
+; EndAtEnd-NOT:  {{.}}
+; EndAtEnd-SAME: ){{$}}
+
+; EndAtEnd:      {{^}}(
+; EndAtEnd-DAG:  <mno>
+; EndAtEnd-DAG:  abc<mno>
+; EndAtEnd-NOT:  {{.}}
+; EndAtEnd-SAME: ){{$}}
+
+; EndAtEnd:      __EndAtEnd
+
+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=EndWithin
+; RUN: FileCheck -input-file %s %s -check-prefix=EndWithin
+
+new match end within old match
+
+__EndWithin
+(abc<mno>xyz  m)
+(abc<mno>xyz  <m)
+(abc<mno>xyz  c<m)
+(abc<mno>xyz  abc<m)
+__EndWithin
+
+; EndWithin:      __EndWithin
+
+; EndWithin:      {{^}}(
+; EndWithin-DAG:  <mno>
+; EndWithin-DAG:  m
+; EndWithin-NOT:  {{.}}
+; EndWithin-SAME: ){{$}}
+
+; EndWithin:      {{^}}(
+; EndWithin-DAG:  <mno>
+; EndWithin-DAG:  <m
+; EndWithin-NOT:  {{.}}
+; EndWithin-SAME: ){{$}}
+
+; EndWithin:      {{^}}(
+; EndWithin-DAG:  <mno>
+; EndWithin-DAG:  c<m
+; EndWithin-NOT:  {{.}}
+; EndWithin-SAME: ){{$}}
+
+; EndWithin:      {{^}}(
+; EndWithin-DAG:  <mno>
+; EndWithin-DAG:  abc<m
+; EndWithin-NOT:  {{.}}
+; EndWithin-SAME: ){{$}}
+
+; EndWithin:      __EndWithin
+
+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=EndRightAfterStart
+; RUN: FileCheck -input-file %s %s -check-prefix=EndRightAfterStart
+
+new match end right after old match start
+
+__EndRightAfterStart
+(abc<mno>xyz  <)
+(abc<mno>xyz  c<)
+(abc<mno>xyz  abc<)
+__EndRightAfterStart
+
+; EndRightAfterStart:      __EndRightAfterStart
+
+; EndRightAfterStart:      {{^}}(
+; EndRightAfterStart-DAG:  <mno>
+; EndRightAfterStart-DAG:  <
+; EndRightAfterStart-NOT:  {{.}}
+; EndRightAfterStart-SAME: ){{$}}
+
+; EndRightAfterStart:      {{^}}(
+; EndRightAfterStart-DAG:  <mno>
+; EndRightAfterStart-DAG:  c<
+; EndRightAfterStart-NOT:  {{.}}
+; EndRightAfterStart-SAME: ){{$}}
+
+; EndRightAfterStart:      {{^}}(
+; EndRightAfterStart-DAG:  <mno>
+; EndRightAfterStart-DAG:  abc<
+; EndRightAfterStart-NOT:  {{.}}
+; EndRightAfterStart-SAME: ){{$}}
+
+; EndRightAfterStart:      __EndRightAfterStart
+
+;---------------------------------------------------------------------
+; RUN: FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:           -check-prefix=EndAtStart
+; RUN: FileCheck -input-file %s %s -check-prefix=EndAtStart
+
+new match end at old match start
+
+__EndAtStart
+(abc<mno>xyz)
+(abc<mno>xyz)
+__EndAtStart
+
+; EndAtStart:      __EndAtStart
+
+; EndAtStart:      {{^}}(
+; EndAtStart-DAG:  <mno>
+; EndAtStart-DAG:  c
+; EndAtStart-DAG:  xyz
+; EndAtStart-NOT:  {{.}}
+; EndAtStart-SAME: ){{$}}
+
+; EndAtStart:      {{^}}(
+; EndAtStart-DAG:  <mno>
+; EndAtStart-DAG:  abc
+; EndAtStart-DAG:  xyz
+; EndAtStart-NOT:  {{.}}
+; EndAtStart-SAME: ){{$}}
+
+; EndAtStart:      __EndAtStart
+
+;---------------------------------------------------------------------
+; RUN: FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:           -check-prefix=EndBeforeStart
+; RUN: FileCheck -input-file %s %s -check-prefix=EndBeforeStart
+
+new match end before old match start
+
+__EndBeforeStart
+(abc<mno>xyz)
+(abc<mno>xyz)
+__EndBeforeStart
+
+; EndBeforeStart:      __EndBeforeStart
+
+; EndBeforeStart:      {{^}}(
+; EndBeforeStart-DAG:  <mno>
+; EndBeforeStart-DAG:  b
+; EndBeforeStart-DAG:  xyz
+; EndBeforeStart-NOT:  {{.}}
+; EndBeforeStart-SAME: ){{$}}
+
+; EndBeforeStart:      {{^}}(
+; EndBeforeStart-DAG:  <mno>
+; EndBeforeStart-DAG:  ab
+; EndBeforeStart-DAG:  xyz
+; EndBeforeStart-NOT:  {{.}}
+; EndBeforeStart-SAME: ){{$}}
+
+; EndBeforeStart:      __EndBeforeStart

llvm/trunk/test/FileCheck/check-dag-overlap.txt

+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=IdentPat
+; RUN: FileCheck -input-file %s %s -check-prefix=IdentPat
+
+__IdentPat
+add r10, r1, r2
+add r11, r3, r4
+mul r5, r10, r11
+__IdentPat
+
+; IdentPat:     {{^}}__IdentPat
+; IdentPat-DAG: {{^}}add [[REG1:r[0-9]+]], {{r[0-9]+}}, {{r[0-9]+}}
+; IdentPat-DAG: {{^}}add [[REG2:r[0-9]+]], {{r[0-9]+}}, {{r[0-9]+}}
+; IdentPat:     {{^}}mul r5, [[REG1]], [[REG2]]
+; IdentPat:     {{^}}__IdentPat
+
+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=IdentPatNot
+; RUN: FileCheck -input-file %s %s -check-prefix=IdentPatNot
+
+__IdentPatNot
+add r11, r1, r2
+xor r12, r1, r2
+add r10, r3, r4
+mul r5, r10, r11
+__IdentPatNot
+
+; IdentPatNot:     {{^}}__IdentPatNot
+; IdentPatNot-DAG: {{^}}add {{r[0-9]+}}, {{r[0-9]+}}, {{r[0-9]+}}
+; IdentPatNot-DAG: {{^}}add {{r[0-9]+}}, {{r[0-9]+}}, {{r[0-9]+}}
+; IdentPatNot-NOT: {{^}}xor
+; IdentPatNot-DAG: {{^}}mul r5, r10, r11
+; IdentPatNot:     {{^}}__IdentPatNot
+
+;---------------------------------------------------------------------
+; RUN: FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:           -check-prefix=IdentPatVarDiff
+; RUN: FileCheck -input-file %s %s -check-prefix=IdentPatVarDiff
+
+__IdentPatVarDiff
+call void @foo(), !dbg !0
+call void @bar(), !dbg !1
+!1 = !DILocation(line: 1,
+!0 = !DILocation(line: 1,
+__IdentPatVarDiff
+
+; IdentPatVarDiff:     {{^}}__IdentPatVarDiff
+; IdentPatVarDiff:     {{^}}call void @foo(), !dbg [[DBG0:![0-9]+]]
+; IdentPatVarDiff:     {{^}}call void @bar(), !dbg [[DBG1:![0-9]+]]
+; IdentPatVarDiff-DAG: {{^}}[[DBG0]] = !DILocation(line: 1,
+; IdentPatVarDiff-DAG: {{^}}[[DBG1]] = !DILocation(line: 1,
+; IdentPatVarDiff:     {{^}}__IdentPatVarDiff
+
+;---------------------------------------------------------------------
+; RUN: FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:           -check-prefix=IdentPatVarSame
+; RUN: not FileCheck -input-file %s %s -check-prefix=IdentPatVarSame
+
+__IdentPatVarSame
+call void @foo(), !dbg !0
+call void @bar(), !dbg !0
+!1 = !DILocation(line: 1,
+!0 = !DILocation(line: 1,
+__IdentPatVarSame
+
+; IdentPatVarSame:     {{^}}__IdentPatVarSame
+; IdentPatVarSame:     {{^}}call void @foo(), !dbg [[DBG0:![0-9]+]]
+; IdentPatVarSame:     {{^}}call void @bar(), !dbg [[DBG1:![0-9]+]]
+; IdentPatVarSame-DAG: {{^}}[[DBG0]] = !DILocation(line: 1,
+; IdentPatVarSame-DAG: {{^}}[[DBG1]] = !DILocation(line: 1,
+; IdentPatVarSame:     {{^}}__IdentPatVarSame
+
+;---------------------------------------------------------------------
+; RUN: FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:           -check-prefix=SupSubSet
+; RUN: not FileCheck -input-file %s %s -check-prefix=SupSubSet
+
+__SupSubSet
+store i64 8, i64* %a
+store i64 4, i64* %a
+store i64 4, i64* %b
+store i64 8, i64* %b
+__SupSubSet
+
+; SupSubSet:     {{^}}__SupSubSet
+; SupSubSet-DAG: {{^}}store i64 {{4|8}}, i64* %a
+; SupSubSet-DAG: {{^}}store i64 4, i64* %a
+; SupSubSet-DAG: {{^}}store i64 {{4|8}}, i64* %b
+; SupSubSet-DAG: {{^}}store i64 4, i64* %b
+; SupSubSet:     {{^}}__SupSubSet
+
+;---------------------------------------------------------------------
+; RUN: FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:           -check-prefix=SubSupSet
+; RUN: FileCheck -input-file %s %s -check-prefix=SubSupSet
+
+__SubSupSet
+store i64 8, i64* %a
+store i64 4, i64* %a
+store i64 4, i64* %b
+store i64 8, i64* %b
+__SubSupSet
+
+; SubSupSet:     {{^}}__SubSupSet
+; SubSupSet-DAG: {{^}}store i64 4, i64* %a
+; SubSupSet-DAG: {{^}}store i64 {{4|8}}, i64* %a
+; SubSupSet-DAG: {{^}}store i64 4, i64* %b
+; SubSupSet-DAG: {{^}}store i64 {{4|8}}, i64* %b
+; SubSupSet:     {{^}}__SubSupSet
+
+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefixes=WrongNumReps
+; RUN: not FileCheck -input-file %s %s -check-prefixes=WrongNumReps
+;
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefixes=WrongNumReps,WrongNumReps2
+; RUN: FileCheck -input-file %s %s \
+; RUN:           -check-prefixes=WrongNumReps,WrongNumReps2
+;
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefixes=WrongNumReps,WrongNumReps2,WrongNumReps3
+; RUN: not FileCheck -input-file %s %s \
+; RUN:               -check-prefixes=WrongNumReps,WrongNumReps2,WrongNumReps3
+
+__WrongNumReps
+0: task_begin
+1: task_begin
+0: barrier_begin
+1: barrier_begin
+__WrongNumReps
+
+; WrongNumReps:      {{^}}__WrongNumReps
+; WrongNumReps-DAG:  {{^}}[[THID:[0-9]+]]: task_begin
+; WrongNumReps-DAG:  {{^}}[[THID]]: barrier_begin
+; WrongNumReps2-DAG: {{^}}[[THID:[0-9]+]]: task_begin
+; WrongNumReps2-DAG: {{^}}[[THID]]: barrier_begin
+; WrongNumReps3-DAG: {{^}}[[THID:[0-9]+]]: task_begin
+; WrongNumReps3-DAG: {{^}}[[THID]]: barrier_begin
+; WrongNumReps-NEXT: {{^}}__WrongNumReps
+
+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=SameSimple
+; RUN: FileCheck -input-file %s %s -check-prefix=SameSimple
+
+__SameSimple
+(<foo><bar><foo>)
+__SameSimple
+
+; SameSimple:      {{^}}__SameSimple
+; SameSimple:      {{^}}(
+; SameSimple-DAG:  <foo>
+; SameSimple-DAG:  <foo>
+; SameSimple-DAG:  <bar>
+; SameSimple-NOT:  <foo>
+; SameSimple-SAME: ){{$}}
+; SameSimple:      {{^}}__SameSimple
+
+;---------------------------------------------------------------------
+; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
+; RUN:               -check-prefix=DagNotDag
+; RUN: FileCheck -input-file %s %s -check-prefix=DagNotDag
+
+Assume we have DAGs, NOTs, DAGs, NOTs, and then DAGs.  Let X, Y, and Z be
+the DAG groups such that the leading DAGs are x, y, and z.  y won't match
+overlaps with matches from:
+
+1. X.  Otherwise, we could get a spurious reordering complaint.
+2. Y, because y is in Y.  To prevent these overlaps, the implementation must be
+   careful not to drop y's match from the previous matches list when it drops
+   matches from X to save search time.
+3. z.  This follows by applying rule #1 for z instead of y.
+
+__DagNotDag
+abcdefgh
+abcd
+efgh
+
+abcd
+ab
+cd
+
+abcd
+cd
+ab
+__DagNotDag
+
+; DagNotDag:     {{^}}__DagNotDag
+;
+; X:
+;   x:DagNotDag-DAG: {{^}}abcdefgh
+;     DagNotDag-DAG: {{^}}abcd
+;     DagNotDag-DAG: efgh{{$}}
+;
+; Reordering complaint if rule #1 is broken.
+; DagNotDag-NOT: abcd
+; DagNotDag-NOT: efgh
+;
+; Y:
+;   y:DagNotDag-DAG: {{^}}abcd
+;     DagNotDag-DAG: {{^}}ab
+;     DagNotDag-DAG: cd{{$}}
+;
+; Matches if rule #2 is broken.
+; DagNotDag-NOT: ab
+; DagNotDag-NOT: cd
+;
+; Z:
+;   z:DagNotDag-DAG: {{^}}abcd
+;     DagNotDag-DAG: {{^}}ab
+;     DagNotDag-DAG: cd{{$}}
+;
+; Matches if rule #3 is broken.
+; DagNotDag-NOT: {{^}}ab
+; DagNotDag-NOT: {{^}}cd
+;
+; DagNotDag:     {{^}}__DagNotDag

llvm/trunk/utils/FileCheck/FileCheck.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/InitLLVM.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cctype>
+#include <list>
 #include <map>
 #include <string>
 #include <system_error>
 #include <vector>
 using namespace llvm;
 
 static cl::opt<std::string>
     CheckFilename(cl::Positional, cl::desc("<check-file>"), cl::Required);
cl::desc("Require all positive matches to cover an entire input line.\n"
              "is not also passed."));
 
 static cl::opt<bool> EnableVarScope(
     "enable-var-scope", cl::init(false),
     cl::desc("Enables scope for regex variables. Variables with names that\n"
              "do not start with '$' will be reset at the beginning of\n"
              "each CHECK-LABEL block."));
 
+static cl::opt<bool> AllowDeprecatedDagOverlap(
+    "allow-deprecated-dag-overlap", cl::init(false),
+    cl::desc("Enable overlapping among matches in a group of consecutive\n"
+             "CHECK-DAG directives.  This option is deprecated and is only\n"
+             "provided for convenience as old tests are migrated to the new\n"
+             "non-overlapping CHECK-DAG implementation.\n"));
+
 typedef cl::list<std::string>::const_iterator prefix_iterator;
 
 //===----------------------------------------------------------------------===//
 // Pattern Handling Code.
 //===----------------------------------------------------------------------===//
 
 namespace Check {
 enum CheckType {
size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
                              std::vector<const Pattern *> &NotStrings,
                              StringMap<StringRef> &VariableTable) const {
   if (DagNotStrings.empty())
     return 0;
 
   size_t LastPos = 0;
   size_t StartPos = LastPos;
 
+  // A sorted list of ranges for non-overlapping dag matches.
+  struct Match {
+    size_t Pos;
+    size_t End;
+  };
+  std::list<Match> Matches;
+
   for (const Pattern &Pat : DagNotStrings) {
     assert((Pat.getCheckTy() == Check::CheckDAG ||
             Pat.getCheckTy() == Check::CheckNot) &&
            "Invalid CHECK-DAG or CHECK-NOT!");
 
     if (Pat.getCheckTy() == Check::CheckNot) {
       NotStrings.push_back(&Pat);
       continue;
     }
 
     assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");
 
-    size_t MatchLen = 0, MatchPos;
-
     // CHECK-DAG always matches from the start.
-    StringRef MatchBuffer = Buffer.substr(StartPos);
-    MatchPos = Pat.Match(MatchBuffer, MatchLen, VariableTable);
+    size_t MatchLen = 0, MatchPos = StartPos;
+
+    // Search for a match that doesn't overlap a previous match in this
+    // CHECK-DAG group.
+    for (auto MI = Matches.begin(), ME = Matches.end(); true; ++MI) {
+      StringRef MatchBuffer = Buffer.substr(MatchPos);
+      size_t MatchPosBuf = Pat.Match(MatchBuffer, MatchLen, VariableTable);
       // With a group of CHECK-DAGs, a single mismatching means the match on
       // that group of CHECK-DAGs fails immediately.
-    if (MatchPos == StringRef::npos) {
+      if (MatchPosBuf == StringRef::npos) {
         PrintCheckFailed(SM, Pat.getLoc(), Pat, MatchBuffer, VariableTable);
         return StringRef::npos;
       }
       // Re-calc it as the offset relative to the start of the original string.
-    MatchPos += StartPos;
+      MatchPos += MatchPosBuf;
+      if (AllowDeprecatedDagOverlap)
+        break;
+      // Iterate previous matches until overlapping match or insertion point.
+      Match M{MatchPos, MatchPos + MatchLen};
+      bool Overlap = false;
+      for (; MI != ME; ++MI) {
+        if (M.Pos < MI->End) {
+          // !Overlap => New match has no overlap and is before this old match.
+          // Overlap => New match overlaps this old match.
+          Overlap = MI->Pos < M.End;
+          break;
+        }
+      }
+      if (!Overlap) {
+        // Insert non-overlapping match into list.
+        Matches.insert(MI, M);
+        break;
+      }
+      MatchPos = MI->End;
+    }
 
     if (!NotStrings.empty()) {
       if (MatchPos < LastPos) {
         // Reordered?
         SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + MatchPos),
                         SourceMgr::DK_Error,
                         Prefix + "-DAG: found a match of CHECK-DAG"
                                  " reordering across a CHECK-NOT");
         SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + LastPos),
                         SourceMgr::DK_Note,
                         Prefix + "-DAG: the farthest match of CHECK-DAG"
                                  " is found here");
         SM.PrintMessage(NotStrings[0]->getLoc(), SourceMgr::DK_Note,
                         Prefix + "-NOT: the crossed pattern specified"
                                  " here");
         SM.PrintMessage(Pat.getLoc(), SourceMgr::DK_Note,
                         Prefix + "-DAG: the reordered pattern specified"
                                  " here");
         return StringRef::npos;
       }
       // All subsequent CHECK-DAGs should be matched from the farthest
-      // position of all precedent CHECK-DAGs (including this one.)
+      // position of all precedent CHECK-DAGs (not including this one).
       StartPos = LastPos;
+      // Don't waste time checking for (impossible) overlaps before that.
+      Matches.clear();
+      Matches.push_back(Match{MatchPos, MatchPos + MatchLen});
       // If there's CHECK-NOTs between two CHECK-DAGs or from CHECK to
       // CHECK-DAG, verify that there's no 'not' strings occurred in that
       // region.
       StringRef SkippedRegion = Buffer.slice(LastPos, MatchPos);
       if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable))
         return StringRef::npos;
       // Clear "not strings".
       NotStrings.clear();