Index: docs/CommandGuide/FileCheck.rst
===================================================================
--- docs/CommandGuide/FileCheck.rst
+++ docs/CommandGuide/FileCheck.rst
@@ -95,6 +95,13 @@
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
-----------
@@ -360,6 +367,25 @@
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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Index: test/FileCheck/check-dag-overlap-torture.txt
===================================================================
--- /dev/null
+++ test/FileCheck/check-dag-overlap-torture.txt
@@ -0,0 +1,304 @@
+;---------------------------------------------------------------------
+; 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
Index: test/FileCheck/check-dag-overlap.txt
===================================================================
--- /dev/null
+++ test/FileCheck/check-dag-overlap.txt
@@ -0,0 +1,220 @@
+;---------------------------------------------------------------------
+; 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
Index: utils/FileCheck/FileCheck.cpp
===================================================================
--- utils/FileCheck/FileCheck.cpp
+++ utils/FileCheck/FileCheck.cpp
@@ -28,6 +28,7 @@
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cctype>
+#include <list>
#include <map>
#include <string>
#include <system_error>
@@ -82,6 +83,13 @@
"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;
//===----------------------------------------------------------------------===//
@@ -1192,6 +1200,13 @@
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) &&
@@ -1204,19 +1219,42 @@
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);
- // With a group of CHECK-DAGs, a single mismatching means the match on
- // that group of CHECK-DAGs fails immediately.
- if (MatchPos == StringRef::npos) {
- PrintCheckFailed(SM, Pat.getLoc(), Pat, MatchBuffer, VariableTable);
- return StringRef::npos;
+ 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 (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 += 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;
}
- // Re-calc it as the offset relative to the start of the original string.
- MatchPos += StartPos;
if (!NotStrings.empty()) {
if (MatchPos < LastPos) {
@@ -1238,8 +1276,11 @@
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.