Add 'CHECK-DAG' support

Refer to 'FileCheck.rst'f for details of 'CHECK-DAG'.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181827 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 306 insertions, 23 deletions

diff --git a/docs/CommandGuide/FileCheck.rst b/docs/CommandGuide/FileCheck.rst
index fce63ba688..0d9834918a 100644
--- a/docs/CommandGuide/FileCheck.rst
+++ b/docs/CommandGuide/FileCheck.rst
@@ -194,6 +194,55 @@ can be used:
    ; CHECK: ret i8
    }
 
+The "CHECK-DAG:" directive
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+If it's necessary to match strings that don't occur in a strictly sequential
+order, "``CHECK-DAG:``" could be used to verify them between two matches (or
+before the first match, or after the last match). For example, clang emits
+vtable globals in reverse order. Using ``CHECK-DAG:``, we can keep the checks
+in the natural order:
+
+.. code-block:: c++
+
+    // RUN: %clang_cc1 %s -emit-llvm -o - | FileCheck %s
+
+    struct Foo { virtual void method(); };
+    Foo f;  // emit vtable
+    // CHECK-DAG: @_ZTV3Foo =
+
+    struct Bar { virtual void method(); };
+    Bar b;
+    // CHECK-DAG: @_ZTV3Bar =
+
+
+With captured variables, ``CHECK-DAG:`` is able to match valid topological
+orderings of a DAG with edges from the definition of a variable to its use.
+It's useful, e.g., when your test cases need to match different output
+sequences from the instruction scheduler. For example,
+
+.. code-block:: llvm
+
+   ; CHECK-DAG: add [[REG1:r[0-9]+]], r1, r2
+   ; CHECK-DAG: add [[REG2:r[0-9]+]], r3, r4
+   ; CHECK:     mul r5, [[REG1]], [[REG2]]
+
+In this case, any order of that two ``add`` instructions will be allowed.
+
+``CHECK-NOT:`` directives could be mixed with ``CHECK-DAG:`` directives to
+exclude strings between the surrounding ``CHECK-DAG:`` directives. As a result,
+the surrounding ``CHECK-DAG:`` directives cannot be reordered, i.e. all
+occurrences matching ``CHECK-DAG:`` before ``CHECK-NOT:`` must not fall behind
+occurrences matching ``CHECK-DAG:`` after ``CHECK-NOT:``. For example,
+
+.. code-block:: llvm
+
+   ; CHECK-DAG: BEFORE
+   ; CHECK-NOT: NOT
+   ; CHECK-DAG: AFTER
+
+This case will reject input strings where ``BEFORE`` occurs after ``AFTER``.
+
 FileCheck Pattern Matching Syntax
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
diff --git a/test/FileCheck/check-dag-xfails.txt b/test/FileCheck/check-dag-xfails.txt
new file mode 100644
index 0000000000..3f4f98e348
--- /dev/null
+++ b/test/FileCheck/check-dag-xfails.txt
@@ -0,0 +1,85 @@
+; RUN: not FileCheck -check-prefix=X1 -input-file %s %s
+; RUN: not FileCheck -check-prefix=X2 -input-file %s %s
+; RUN: not FileCheck -check-prefix=X3 -input-file %s %s
+; RUN: not FileCheck -check-prefix=X4 -input-file %s %s
+; RUN: not FileCheck -check-prefix=X5 -input-file %s %s
+; RUN: not FileCheck -check-prefix=X6 -input-file %s %s
+
+__x1
+add r10, r1, r2
+add r11, r3, r4
+mul r5, r10, r12
+__x1
+
+; X1: __x1
+; X1-DAG: add [[REG1:r[0-9]+]], r1, r2
+; X1-DAG: add [[REG2:r[0-9]+]], r3, r4
+; X1: mul r5, [[REG1]], [[REG2]]
+; X1: __x1
+
+__x2
+mul r11, r3, r4
+mul r10, r1, r2
+add r5, r11, r11
+__x2
+
+; X2: __x2
+; X2-DAG: mul [[REG1:r[0-9]+]], r1, r2
+; X2-DAG: mul [[REG2:r[0-9]+]], r3, r4
+; X2: add r5, [[REG1]], [[REG2]]
+; X2: __x2
+
+__x3
+add r11, r3, r4
+add r12, r1, r2
+mul r5, r10, r11
+__x3
+
+; X3: __x3
+; X3-DAG: add [[REG1:r[0-9]+]], r1, r2
+; X3-DAG: add [[REG2:r[0-9]+]], r3, r4
+; X3-DAG: mul r5, [[REG1]], [[REG2]]
+; X3: __x3
+
+__x4
+add r11, r3, r4
+add r12, r1, r2
+not
+mul r5, r12, r11
+__x4
+
+; X4: __x4
+; X4-DAG: add [[REG1:r[0-9]+]], r1, r2
+; X4-DAG: add [[REG2:r[0-9]+]], r3, r4
+; X4-NOT: not
+; X4-DAG: mul r5, [[REG1]], [[REG2]]
+; X4: __x4
+
+__x5
+mul r5, r12, r11
+add r11, r3, r4
+add r12, r1, r2
+not
+__x5
+
+; X5: __x5
+; X5-DAG: add [[REG1:r[0-9]+]], r1, r2
+; X5-DAG: add [[REG2:r[0-9]+]], r3, r4
+; X5-NOT: not
+; X5-DAG: mul r5, [[REG1]], [[REG2]]
+; X5: __x5
+
+__x6
+add r11, r3, r4
+mul r6, r12, r11
+add r12, r1, r2
+mul r5, r12, r11
+__x6
+
+; X6: __x6
+; X6-DAG: add [[REG1:r[0-9]+]], r1, r2
+; X6-DAG: add [[REG2:r[0-9]+]], r3, r4
+; X6-NOT: not
+; X6-DAG: mul r5, [[REG1]], [[REG2]]
+; X6-DAG: mul r6, [[REG1]], [[REG2]]
+; X6: __x6
diff --git a/test/FileCheck/check-dag.txt b/test/FileCheck/check-dag.txt
new file mode 100644
index 0000000000..6325e06e5a
--- /dev/null
+++ b/test/FileCheck/check-dag.txt
@@ -0,0 +1,25 @@
+; RUN: FileCheck -input-file %s %s
+
+add r10, r1, r2
+add r11, r3, r4
+mul r5, r10, r11
+
+mul r11, r3, r4
+mul r10, r1, r2
+add r5, r10, r11
+
+add r11, r3, r4
+add r10, r1, r2
+mul r5, r10, r11
+
+; CHECK-DAG: add [[REG1:r[0-9]+]], r1, r2
+; CHECK-DAG: add [[REG2:r[0-9]+]], r3, r4
+; CHECK: mul r5, [[REG1]], [[REG2]]
+
+; CHECK-DAG: mul [[REG1:r[0-9]+]], r1, r2
+; CHECK-DAG: mul [[REG2:r[0-9]+]], r3, r4
+; CHECK: add r5, [[REG1]], [[REG2]]
+
+; CHECK-DAG: add [[REG1:r[0-9]+]], r1, r2
+; CHECK-DAG: add [[REG2:r[0-9]+]], r3, r4
+; CHECK-DAG: mul r5, [[REG1]], [[REG2]]
diff --git a/utils/FileCheck/FileCheck.cpp b/utils/FileCheck/FileCheck.cpp
index 44a078374c..07294a3b63 100644
--- a/utils/FileCheck/FileCheck.cpp
+++ b/utils/FileCheck/FileCheck.cpp
@@ -60,6 +60,12 @@ class Pattern {
   /// used for trailing CHECK-NOTs.
   bool MatchEOF;
 
+  /// MatchNot
+  bool MatchNot;
+
+  /// MatchDag
+  bool MatchDag;
+
   /// FixedStr - If non-empty, this pattern is a fixed string match with the
   /// specified fixed string.
   StringRef FixedStr;
@@ -83,7 +89,8 @@ class Pattern {
 
 public:
 
-  Pattern(bool matchEOF = false) : MatchEOF(matchEOF) { }
+  Pattern(bool matchEOF = false)
+    : MatchEOF(matchEOF), MatchNot(false), MatchDag(false) { }
 
   /// getLoc - Return the location in source code.
   SMLoc getLoc() const { return PatternLoc; }
@@ -108,6 +115,12 @@ public:
   void PrintFailureInfo(const SourceMgr &SM, StringRef Buffer,
                         const StringMap<StringRef> &VariableTable) const;
 
+  void setMatchNot(bool Not) { MatchNot = Not; }
+  bool getMatchNot() const { return MatchNot; }
+
+  void setMatchDag(bool Dag) { MatchDag = Dag; }
+  bool getMatchDag() const { return MatchDag; }
+
 private:
   static void AddFixedStringToRegEx(StringRef FixedStr, std::string &TheStr);
   bool AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM);
@@ -581,15 +594,15 @@ struct CheckString {
   /// to a CHECK: directive.
   bool IsCheckNext;
 
-  /// NotStrings - These are all of the strings that are disallowed from
+  /// DagNotStrings - These are all of the strings that are disallowed from
   /// occurring between this match string and the previous one (or start of
   /// file).
-  std::vector<Pattern> NotStrings;
+  std::vector<Pattern> DagNotStrings;
 
   CheckString(const Pattern &P, SMLoc L, bool isCheckNext)
     : Pat(P), Loc(L), IsCheckNext(isCheckNext) {}
 
-  /// Check - Match check string and its "not strings".
+  /// Check - Match check string and its "not strings" and/or "dag strings".
   size_t Check(const SourceMgr &SM, StringRef Buffer, size_t &MatchLen,
                StringMap<StringRef> &VariableTable) const;
 
@@ -598,7 +611,13 @@ struct CheckString {
 
   /// CheckNot - Verify there's no "not strings" in the given buffer.
   bool CheckNot(const SourceMgr &SM, StringRef Buffer,
+                const std::vector<const Pattern *> &NotStrings,
                 StringMap<StringRef> &VariableTable) const;
+
+  /// CheckDag - Match "dag strings" and their mixed "not strings".
+  size_t CheckDag(const SourceMgr &SM, StringRef Buffer,
+                  std::vector<const Pattern *> &NotStrings,
+                  StringMap<StringRef> &VariableTable) const;
 };
 
 /// Canonicalize whitespaces in the input file. Line endings are replaced
@@ -663,7 +682,7 @@ static bool ReadCheckFile(SourceMgr &SM,
 
   // Find all instances of CheckPrefix followed by : in the file.
   StringRef Buffer = F->getBuffer();
-  std::vector<Pattern> NotMatches;
+  std::vector<Pattern> DagNotMatches;
 
   // LineNumber keeps track of the line on which CheckPrefix instances are
   // found.
@@ -684,7 +703,7 @@ static bool ReadCheckFile(SourceMgr &SM,
 
     // When we find a check prefix, keep track of whether we find CHECK: or
     // CHECK-NEXT:
-    bool IsCheckNext = false, IsCheckNot = false;
+    bool IsCheckNext = false, IsCheckNot = false, IsCheckDag = false;
 
     // Verify that the : is present after the prefix.
     if (Buffer[CheckPrefix.size()] == ':') {
@@ -697,6 +716,10 @@ static bool ReadCheckFile(SourceMgr &SM,
                memcmp(Buffer.data()+CheckPrefix.size(), "-NOT:", 5) == 0) {
       Buffer = Buffer.substr(CheckPrefix.size()+5);
       IsCheckNot = true;
+    } else if (Buffer.size() > CheckPrefix.size()+5 &&
+               memcmp(Buffer.data()+CheckPrefix.size(), "-DAG:", 5) == 0) {
+      Buffer = Buffer.substr(CheckPrefix.size()+5);
+      IsCheckDag = true;
     } else {
       Buffer = Buffer.substr(1);
       continue;
@@ -717,6 +740,9 @@ static bool ReadCheckFile(SourceMgr &SM,
     if (P.ParsePattern(Buffer.substr(0, EOL), SM, LineNumber))
       return true;
 
+    P.setMatchNot(IsCheckNot);
+    P.setMatchDag(IsCheckDag);
+
     Buffer = Buffer.substr(EOL);
 
     // Verify that CHECK-NEXT lines have at least one CHECK line before them.
@@ -728,9 +754,9 @@ static bool ReadCheckFile(SourceMgr &SM,
       return true;
     }
 
-    // Handle CHECK-NOT.
-    if (IsCheckNot) {
-      NotMatches.push_back(P);
+    // Handle CHECK-DAG/-NOT.
+    if (IsCheckDag || IsCheckNot) {
+      DagNotMatches.push_back(P);
       continue;
     }
 
@@ -738,15 +764,15 @@ static bool ReadCheckFile(SourceMgr &SM,
     CheckStrings.push_back(CheckString(P,
                                        PatternLoc,
                                        IsCheckNext));
-    std::swap(NotMatches, CheckStrings.back().NotStrings);
+    std::swap(DagNotMatches, CheckStrings.back().DagNotStrings);
   }
 
-  // Add an EOF pattern for any trailing CHECK-NOTs.
-  if (!NotMatches.empty()) {
+  // Add an EOF pattern for any trailing CHECK-DAG/-NOTs.
+  if (!DagNotMatches.empty()) {
     CheckStrings.push_back(CheckString(Pattern(true),
                                        SMLoc::getFromPointer(Buffer.data()),
                                        false));
-    std::swap(NotMatches, CheckStrings.back().NotStrings);
+    std::swap(DagNotMatches, CheckStrings.back().DagNotStrings);
   }
 
   if (CheckStrings.empty()) {
@@ -758,11 +784,11 @@ static bool ReadCheckFile(SourceMgr &SM,
   return false;
 }
 
-static void PrintCheckFailed(const SourceMgr &SM, const CheckString &CheckStr,
-                             StringRef Buffer,
+static void PrintCheckFailed(const SourceMgr &SM, const SMLoc &Loc,
+                             const Pattern &Pat, StringRef Buffer,
                              StringMap<StringRef> &VariableTable) {
   // Otherwise, we have an error, emit an error message.
-  SM.PrintMessage(CheckStr.Loc, SourceMgr::DK_Error,
+  SM.PrintMessage(Loc, SourceMgr::DK_Error,
                   "expected string not found in input");
 
   // Print the "scanning from here" line.  If the current position is at the
@@ -773,7 +799,13 @@ static void PrintCheckFailed(const SourceMgr &SM, const CheckString &CheckStr,
                   "scanning from here");
 
   // Allow the pattern to print additional information if desired.
-  CheckStr.Pat.PrintFailureInfo(SM, Buffer, VariableTable);
+  Pat.PrintFailureInfo(SM, Buffer, VariableTable);
+}
+
+static void PrintCheckFailed(const SourceMgr &SM, const CheckString &CheckStr,
+                             StringRef Buffer,
+                             StringMap<StringRef> &VariableTable) {
+  PrintCheckFailed(SM, CheckStr.Loc, CheckStr.Pat, Buffer, VariableTable);
 }
 
 /// CountNumNewlinesBetween - Count the number of newlines in the specified
@@ -799,13 +831,24 @@ static unsigned CountNumNewlinesBetween(StringRef Range) {
 size_t CheckString::Check(const SourceMgr &SM, StringRef Buffer,
                           size_t &MatchLen,
                           StringMap<StringRef> &VariableTable) const {
-  size_t MatchPos = Pat.Match(Buffer, MatchLen, VariableTable);
+  size_t LastPos = 0;
+  std::vector<const Pattern *> NotStrings;
+
+  // Match "dag strings" (with mixed "not strings" if any).
+  LastPos = CheckDag(SM, Buffer, NotStrings, VariableTable);
+  if (LastPos == StringRef::npos)
+    return StringRef::npos;
+
+  // Match itself from the last position after matching CHECK-DAG.
+  StringRef MatchBuffer = Buffer.substr(LastPos);
+  size_t MatchPos = Pat.Match(MatchBuffer, MatchLen, VariableTable);
   if (MatchPos == StringRef::npos) {
-    PrintCheckFailed(SM, *this, Buffer, VariableTable);
+    PrintCheckFailed(SM, *this, MatchBuffer, VariableTable);
     return StringRef::npos;
   }
+  MatchPos += LastPos;
 
-  StringRef SkippedRegion = Buffer.substr(0, MatchPos);
+  StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);
 
   // If this check is a "CHECK-NEXT", verify that the previous match was on
   // the previous line (i.e. that there is one newline between them).
@@ -814,7 +857,7 @@ size_t CheckString::Check(const SourceMgr &SM, StringRef Buffer,
 
   // If this match had "not strings", verify that they don't exist in the
   // skipped region.
-  if (CheckNot(SM, SkippedRegion, VariableTable))
+  if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable))
     return StringRef::npos;
 
   return MatchPos;
@@ -857,18 +900,22 @@ bool CheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {
 }
 
 bool CheckString::CheckNot(const SourceMgr &SM, StringRef Buffer,
+                           const std::vector<const Pattern *> &NotStrings,
                            StringMap<StringRef> &VariableTable) const {
   for (unsigned ChunkNo = 0, e = NotStrings.size();
        ChunkNo != e; ++ChunkNo) {
+    const Pattern *Pat = NotStrings[ChunkNo];
+    assert(Pat->getMatchNot() && "Expect CHECK-NOT!");
+
     size_t MatchLen = 0;
-    size_t Pos = NotStrings[ChunkNo].Match(Buffer, MatchLen, VariableTable);
+    size_t Pos = Pat->Match(Buffer, MatchLen, VariableTable);
 
     if (Pos == StringRef::npos) continue;
 
     SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()+Pos),
                     SourceMgr::DK_Error,
                     CheckPrefix+"-NOT: string occurred!");
-    SM.PrintMessage(NotStrings[ChunkNo].getLoc(), SourceMgr::DK_Note,
+    SM.PrintMessage(Pat->getLoc(), SourceMgr::DK_Note,
                     CheckPrefix+"-NOT: pattern specified here");
     return true;
   }
@@ -876,6 +923,83 @@ bool CheckString::CheckNot(const SourceMgr &SM, StringRef Buffer,
   return false;
 }
 
+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;
+
+  for (unsigned ChunkNo = 0, e = DagNotStrings.size();
+       ChunkNo != e; ++ChunkNo) {
+    const Pattern &Pat = DagNotStrings[ChunkNo];
+
+    assert((Pat.getMatchDag() ^ Pat.getMatchNot()) &&
+           "Invalid CHECK-DAG or CHECK-NOT!");
+
+    if (Pat.getMatchNot()) {
+      NotStrings.push_back(&Pat);
+      continue;
+    }
+
+    assert(Pat.getMatchDag() && "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;
+    }
+    // Re-calc it as the offset relative to the start of the original string.
+    MatchPos += StartPos;
+
+    if (!NotStrings.empty()) {
+      if (MatchPos < LastPos) {
+        // Reordered?
+        SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + MatchPos),
+                        SourceMgr::DK_Error,
+                        CheckPrefix+"-DAG: found a match of CHECK-DAG"
+                        " reordering across a CHECK-NOT");
+        SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + LastPos),
+                        SourceMgr::DK_Note,
+                        CheckPrefix+"-DAG: the farthest match of CHECK-DAG"
+                        " is found here");
+        SM.PrintMessage(NotStrings[0]->getLoc(), SourceMgr::DK_Note,
+                        CheckPrefix+"-NOT: the crossed pattern specified"
+                        " here");
+        SM.PrintMessage(Pat.getLoc(), SourceMgr::DK_Note,
+                        CheckPrefix+"-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.)
+      StartPos = LastPos;
+      // 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.substr(LastPos, MatchPos);
+      size_t Pos = CheckNot(SM, SkippedRegion, NotStrings, VariableTable);
+      if (Pos != StringRef::npos)
+        return StringRef::npos;
+      // Clear "not strings".
+      NotStrings.clear();
+    }
+
+    // Update the last position with CHECK-DAG matches.
+    LastPos = std::max(MatchPos + MatchLen, LastPos);
+  }
+
+  return LastPos;
+}
+
 int main(int argc, char **argv) {
   sys::PrintStackTraceOnErrorSignal();
   PrettyStackTraceProgram X(argc, argv);