[FileCheck] Fix search ranges for DAG-NOT-DAG

A DAG-NOT-DAG is a CHECK-DAG group, X, followed by a CHECK-NOT group,
N, followed by a CHECK-DAG group, Y.  Let y be the initial directive
of Y.  This patch makes the following changes to the behavior:

    1. Directives in N can no longer match within part of Y's match
       range just because y happens not to be the earliest match from
       Y.  Specifically, this patch withdraws N's search range end
       from y's match range start to Y's match range start.

    2. y can no longer match within X's match range, where a y match
       produced a reordering complaint, which is thus no longer
       possible.  Specifically, this patch withdraws y's search range
       start from X's permitted range start to X's match range end,
       which was already the search range start for other members of
       Y.

Both of these changes can only increase the number of test passes: #1
constrains the ability of CHECK-NOTs to match, and #2 expands the
ability of CHECK-DAGs to match without complaints.

These changes are based on discussions at:

   <http://lists.llvm.org/pipermail/llvm-dev/2018-May/123550.html>
   <https://reviews.llvm.org/D47106>

which conclude that:

    1. These changes simplify the FileCheck conceptual model.  First,
       it makes search ranges for DAG-NOT-DAG more consistent with
       other cases.  Second, it was confusing that y was treated
       differently from the rest of Y.

    2. These changes add theoretical use cases for DAG-NOT-DAG that
       had no obvious means to be expressed otherwise.  We can justify
       the first half of this assertion with the observation that
       these changes can only increase the number of test passes.

    3. Reordering detection for DAG-NOT-DAG had no obvious real
       benefit.

We don't have evidence from real uses cases to help us debate
conclusions #2 and #3, but #1 at least seems intuitive.

Reviewed By: probinson

Differential Revision: https://reviews.llvm.org/D48986

llvm-svn: 337605

2 files changed, 78 insertions, 1 deletions

diff --git a/llvm/test/FileCheck/check-dag-not-dag.txt b/llvm/test/FileCheck/check-dag-not-dag.txt
new file mode 100644
index 00000000000..68c376ab3b4
--- /dev/null
+++ b/llvm/test/FileCheck/check-dag-not-dag.txt
@@ -0,0 +1,76 @@
+;---------------------------------------------------------------------
+; RUN: FileCheck -input-file %s %s -check-prefix=NotSearchEnd
+
+The search range for the NOTs used to end at the start of the match range for
+the first DAG in the following DAG group.  Now it ends at the start of the
+match range for the entire following DAG group.
+
+__NotSearchEnd
+x0
+x1
+
+y1
+foobar
+y0
+
+z2
+foobar
+z1
+foobar
+z0
+__NotSearchEnd
+
+; NotSearchEnd:     {{^}}__NotSearchEnd
+; NotSearchEnd-DAG: {{^}}x0
+; NotSearchEnd-DAG: {{^}}x1
+; NotSearchEnd-NOT: {{^}}foobar
+; NotSearchEnd-DAG: {{^}}y0
+; NotSearchEnd-DAG: {{^}}y1
+; NotSearchEnd-NOT: {{^}}foobar
+; NotSearchEnd-DAG: {{^}}z0
+; NotSearchEnd-DAG: {{^}}z1
+; NotSearchEnd-DAG: {{^}}z2
+; NotSearchEnd:     {{^}}__NotSearchEnd
+
+;---------------------------------------------------------------------
+; RUN: FileCheck -input-file %s %s -check-prefix=Dag2SearchStart
+
+The start of the search range for the second or later DAG group used to be
+different for its first DAG than its other DAGs.  For the first DAG, it was
+the start of the permitted range for the preceding DAG group, and there was a
+reordering complaint if the match range was in the first DAG group's match
+range.  For the other DAGs, it was the end of the match range for the
+preceding DAG group, so reordering detection wasn't possible.  Now, the
+first DAG behaves like the others, and so reordering detection is no longer
+implemented.  As a result, matches that used to produce the reordering
+complaint are now skipped, permitting later matches to succeed.
+
+__Dag2SearchStart
+y0
+y1
+x0
+y0
+y1
+x1
+
+z1
+z0
+y1
+z1
+z0
+y0
+
+z0
+z1
+__Dag2SearchStart
+
+; Dag2SearchStart:     {{^}}__Dag2SearchStart
+; Dag2SearchStart-DAG: {{^}}x0
+; Dag2SearchStart-DAG: {{^}}x1
+; Dag2SearchStart-NOT: {{^}}foobar
+; Dag2SearchStart-DAG: {{^}}y0
+; Dag2SearchStart-DAG: {{^}}y1
+; Dag2SearchStart-NOT: {{^}}foobar
+; Dag2SearchStart-DAG: {{^}}z0
+; Dag2SearchStart-DAG: {{^}}z1
+; Dag2SearchStart:     {{^}}__Dag2SearchStart
\ No newline at end of file
diff --git a/llvm/test/FileCheck/check-dag-overlap.txt b/llvm/test/FileCheck/check-dag-overlap.txt
index a94c6679ee6..027a243b955 100644
--- a/llvm/test/FileCheck/check-dag-overlap.txt
+++ b/llvm/test/FileCheck/check-dag-overlap.txt
@@ -168,7 +168,8 @@ 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.
+1. X.  Otherwise, we used to get a spurious reordering complaint (back
+   when reordering complaints on DAG-NOT-DAG were still implemented).
 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.