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.txt =================================================================== --- /dev/null +++ test/FileCheck/check-dag-overlap.txt @@ -0,0 +1,466 @@ +;--------------------------------------------------------------------- +; 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=Torture +; RUN: FileCheck -input-file %s %s -check-prefix=Torture + +__Torture +end after old match end +(abcxyz) +(abcxyz) +(abcxyz >xyz) +(abcxyz no>xyz) +(abcxyz xyz) +(abcxyz cxyz) +(abcxyz abcxyz) + +end right after old match end +(abcxyz) +(abcxyz >x) +(abcxyz no>x) +(abcxyz x) +(abcxyz cx) +(abcxyz abcx) + +end at old match end +(abcxyz >) +(abcxyz no>) +(abcxyz ) +(abcxyz c) +(abcxyz abc) + +end within old match +(abcxyz m) +(abcxyz xyz cxyz abcxyz <) +(abcxyz c<) +(abcxyz abc<) + +end at old match start +(abcxyz) +(abcxyz) + +end before old match start +(abcxyz) +(abcxyz) +__Torture + +; Torture: {{^}}__Torture + +end after old match end + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: yz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: xyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: >xyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: no>xyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: xyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: cxyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: abcxyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +end right after old match end + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: x +; Torture-NOT: {{.}} +; Torture-SAME: yz){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: >x +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: no>x +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: x +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: cx +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: abcx +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +end at old match end + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: > +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: no> +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: c +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: abc +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +end within old match + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: m +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: +; Torture-DAG: c +; Torture-DAG: abc +; Torture-DAG: < +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: c< +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: abc< +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +end at old match start + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: c +; Torture-DAG: xyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: abc +; Torture-DAG: xyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +end before old match start + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: b +; Torture-DAG: xyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}( +; Torture-DAG: +; Torture-DAG: ab +; Torture-DAG: xyz +; Torture-NOT: {{.}} +; Torture-SAME: ){{$}} + +; Torture: {{^}}__Torture + +;--------------------------------------------------------------------- +; 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 \ No newline at end of file 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.