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 ----------- @@ -341,6 +348,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 +(abcxyz) +(abcxyz) +(abcxyz >xyz) +(abcxyz no>xyz) +(abcxyz xyz) +(abcxyz cxyz) +(abcxyz abcxyz) +__EndAfterEnd + +; EndAfterEnd: __EndAfterEnd + +; EndAfterEnd: {{^}}( +; EndAfterEnd-DAG: +; EndAfterEnd-DAG: yz +; EndAfterEnd-NOT: {{.}} +; EndAfterEnd-SAME: ){{$}} + +; EndAfterEnd: {{^}}( +; EndAfterEnd-DAG: +; EndAfterEnd-DAG: xyz +; EndAfterEnd-NOT: {{.}} +; EndAfterEnd-SAME: ){{$}} + +; EndAfterEnd: {{^}}( +; EndAfterEnd-DAG: +; EndAfterEnd-DAG: >xyz +; EndAfterEnd-NOT: {{.}} +; EndAfterEnd-SAME: ){{$}} + +; EndAfterEnd: {{^}}( +; EndAfterEnd-DAG: +; EndAfterEnd-DAG: no>xyz +; EndAfterEnd-NOT: {{.}} +; EndAfterEnd-SAME: ){{$}} + +; EndAfterEnd: {{^}}( +; EndAfterEnd-DAG: +; EndAfterEnd-DAG: xyz +; EndAfterEnd-NOT: {{.}} +; EndAfterEnd-SAME: ){{$}} + +; EndAfterEnd: {{^}}( +; EndAfterEnd-DAG: +; EndAfterEnd-DAG: cxyz +; EndAfterEnd-NOT: {{.}} +; EndAfterEnd-SAME: ){{$}} + +; EndAfterEnd: {{^}}( +; EndAfterEnd-DAG: +; EndAfterEnd-DAG: abcxyz +; 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 +(abcxyz) +(abcxyz >x) +(abcxyz no>x) +(abcxyz x) +(abcxyz cx) +(abcxyz abcx) +__EndRightAfterEnd + +; EndRightAfterEnd: __EndRightAfterEnd + +; EndRightAfterEnd: {{^}}( +; EndRightAfterEnd-DAG: +; EndRightAfterEnd-DAG: x +; EndRightAfterEnd-NOT: {{.}} +; EndRightAfterEnd-SAME: yz){{$}} + +; EndRightAfterEnd: {{^}}( +; EndRightAfterEnd-DAG: +; EndRightAfterEnd-DAG: >x +; EndRightAfterEnd-NOT: {{.}} +; EndRightAfterEnd-SAME: ){{$}} + +; EndRightAfterEnd: {{^}}( +; EndRightAfterEnd-DAG: +; EndRightAfterEnd-DAG: no>x +; EndRightAfterEnd-NOT: {{.}} +; EndRightAfterEnd-SAME: ){{$}} + +; EndRightAfterEnd: {{^}}( +; EndRightAfterEnd-DAG: +; EndRightAfterEnd-DAG: x +; EndRightAfterEnd-NOT: {{.}} +; EndRightAfterEnd-SAME: ){{$}} + +; EndRightAfterEnd: {{^}}( +; EndRightAfterEnd-DAG: +; EndRightAfterEnd-DAG: cx +; EndRightAfterEnd-NOT: {{.}} +; EndRightAfterEnd-SAME: ){{$}} + +; EndRightAfterEnd: {{^}}( +; EndRightAfterEnd-DAG: +; EndRightAfterEnd-DAG: abcx +; 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 +(abcxyz >) +(abcxyz no>) +(abcxyz ) +(abcxyz c) +(abcxyz abc) +__EndAtEnd + +; EndAtEnd: __EndAtEnd + +; EndAtEnd: {{^}}( +; EndAtEnd-DAG: +; EndAtEnd-DAG: > +; EndAtEnd-NOT: {{.}} +; EndAtEnd-SAME: ){{$}} + +; EndAtEnd: {{^}}( +; EndAtEnd-DAG: +; EndAtEnd-DAG: no> +; EndAtEnd-NOT: {{.}} +; EndAtEnd-SAME: ){{$}} + +; EndAtEnd: {{^}}( +; EndAtEnd-DAG: +; EndAtEnd-DAG: +; EndAtEnd-NOT: {{.}} +; EndAtEnd-SAME: ){{$}} + +; EndAtEnd: {{^}}( +; EndAtEnd-DAG: +; EndAtEnd-DAG: c +; EndAtEnd-NOT: {{.}} +; EndAtEnd-SAME: ){{$}} + +; EndAtEnd: {{^}}( +; EndAtEnd-DAG: +; EndAtEnd-DAG: abc +; 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 +(abcxyz m) +(abcxyz xyz cxyz abc +; EndWithin-DAG: m +; EndWithin-NOT: {{.}} +; EndWithin-SAME: ){{$}} + +; EndWithin: {{^}}( +; EndWithin-DAG: +; EndWithin-DAG: +; EndWithin-DAG: c +; EndWithin-DAG: abcxyz <) +(abcxyz c<) +(abcxyz abc<) +__EndRightAfterStart + +; EndRightAfterStart: __EndRightAfterStart + +; EndRightAfterStart: {{^}}( +; EndRightAfterStart-DAG: +; EndRightAfterStart-DAG: < +; EndRightAfterStart-NOT: {{.}} +; EndRightAfterStart-SAME: ){{$}} + +; EndRightAfterStart: {{^}}( +; EndRightAfterStart-DAG: +; EndRightAfterStart-DAG: c< +; EndRightAfterStart-NOT: {{.}} +; EndRightAfterStart-SAME: ){{$}} + +; EndRightAfterStart: {{^}}( +; EndRightAfterStart-DAG: +; 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 +(abcxyz) +(abcxyz) +__EndAtStart + +; EndAtStart: __EndAtStart + +; EndAtStart: {{^}}( +; EndAtStart-DAG: +; EndAtStart-DAG: c +; EndAtStart-DAG: xyz +; EndAtStart-NOT: {{.}} +; EndAtStart-SAME: ){{$}} + +; EndAtStart: {{^}}( +; EndAtStart-DAG: +; 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 +(abcxyz) +(abcxyz) +__EndBeforeStart + +; EndBeforeStart: __EndBeforeStart + +; EndBeforeStart: {{^}}( +; EndBeforeStart-DAG: +; EndBeforeStart-DAG: b +; EndBeforeStart-DAG: xyz +; EndBeforeStart-NOT: {{.}} +; EndBeforeStart-SAME: ){{$}} + +; EndBeforeStart: {{^}}( +; EndBeforeStart-DAG: +; 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 +() +__SameSimple + +; SameSimple: {{^}}__SameSimple +; SameSimple: {{^}}( +; SameSimple-DAG: +; SameSimple-DAG: +; SameSimple-DAG: +; SameSimple-NOT: +; 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 #include +#include #include #include #include @@ -82,6 +83,13 @@ "do not start with '$' will be reset at the beginning of\n" "each CHECK-LABEL block.")); +static cl::opt 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::const_iterator prefix_iterator; //===----------------------------------------------------------------------===// @@ -1158,6 +1166,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 Matches; + for (const Pattern &Pat : DagNotStrings) { assert((Pat.getCheckTy() == Check::CheckDAG || Pat.getCheckTy() == Check::CheckNot) && @@ -1170,19 +1185,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) { @@ -1204,8 +1242,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.