[TableGen] Add the !find bang operator

[Paul-C-Anagnostopoulos]

Summary

This revision adds the !find bang operator, which searches a source string for a target string.

I updated the TableGen Programmer's Reference and added a test.

[dblaikie]

Do you have a use case in mind for this feature? (will it help tidy up existing tblgen files significantly? is it necessary to support some use case that's not possible to express currently but that's needed by you or others?)

[Paul-C-Anagnostopoulos]

I added !find() to complement !substr(), so that TableGen would have the two most common string functions. I believe !find will be helpful with 'assert' as people begin adding assertions to TableGen files.

[dblaikie]

In D101318#2717830, @Paul-C-Anagnostopoulos wrote:

I added !find() to complement !substr(), so that TableGen would have the two most common string functions. I believe !find will be helpful with 'assert' as people begin adding assertions to TableGen files.

Fair enough - a general suggestion that these sort of tools aren't necessarily the place for adding a lot of speculative features. Usually we expect some in-tree motivating use case (one that you might/would implement/use) (potentially being used in a fairly-shortly-after follow-up commit) rather than building things that might be nice to have at some point.

So perhaps if you're adding features you could use them in the existing tablegen files to clean them up/improve them in some way to motivate the work, demonstrate how to use the features, and evangelize them (having the existing files using the new features as intended helps other people pick up on them when they go to modify/add/etc to the existing usage).

[Paul-C-Anagnostopoulos]

It makes good sense to spend some time now on additional TableGen file cleanup. There is one file with TODOs for assert, so I will start there.

[Paul-C-Anagnostopoulos]

I will push this on Wednesday.

@dblaikie: What is your opinion on adding an assertion to a TableGen file when the backend(s) are already checking the condition? I think putting the checking closer to the problem is a good thing, and may result in more specific error messages. But, on the other hand, one could argue that it's pointless work.

[dblaikie]

In D101318#2720374, @Paul-C-Anagnostopoulos wrote:

I will push this on Wednesday.

@dblaikie: What is your opinion on adding an assertion to a TableGen file when the backend(s) are already checking the condition? I think putting the checking closer to the problem is a good thing, and may result in more specific error messages. But, on the other hand, one could argue that it's pointless work.

Seems plausibly useful - though no doubt send such changes for review by the specific tblgen authors to see what they think (I've never written/modified target tblgens - so I'm on the fringes of this work at best).

llvm/docs/TableGen/ProgRef.rst

 Bang operators
 --------------
 
 TableGen provides "bang operators" that have a wide variety of uses:
 
 .. productionlist::
    BangOperator: one of
                : !add        !and         !cast        !con         !dag 
-               : !empty      !eq          !foldl       !foreach     !filter
-               : !ge         !getdagop    !gt          !head        !if
-               : !interleave !isa         !le          !listconcat  !listsplat
-               : !lt         !mul         !ne          !not         !or
-               : !setdagop   !shl         !size        !sra         !srl
-               : !strconcat  !sub         !subst       !substr      !tail
-               : !xor
+               : !empty      !eq          !filter      !find        !foldl
+               : !foreach    !ge          !getdagop    !gt          !head
+               : !if         !interleave  !isa         !le          !listconcat
+               : !listsplat  !lt          !mul         !ne          !not
+               : !or         !setdagop    !shl         !size        !sra
+               : !srl        !strconcat   !sub         !subst       !substr
+               : !tail       !xor
 
 The ``!cond`` operator has a slightly different
 syntax compared to other bang operators, so it is defined separately:
 
 .. productionlist::
    CondOperator: !cond
 
 See `Appendix A: Bang Operators`_ for a description of each bang operator.
``!filter(``\ *var*\ ``,`` *list*\ ``,`` *predicate*\ ``)``
     *list*. To perform the filtering, TableGen binds the variable *var* to each
     element and then evaluates the *predicate* expression, which presumably
     refers to *var*. The predicate must
     produce a boolean value (``bit``, ``bits``, or ``int``). The value is
     interpreted as with ``!if``:
     if the value is 0, the element is not included in the new list. If the value
     is anything else, the element is included.
 
+``!find(``\ *string1*\ ``,`` *string2*\ [``,`` *start*]\ ``)``
+    This operator searches for *string2* in *string1* and produces its
+    position. The starting position of the search may be specified by *start*,
+    which can range between 0 and the length of *string1*; the default is 0.
+    If the string is not found, the result is -1.
+
 ``!foldl(``\ *init*\ ``,`` *list*\ ``,`` *acc*\ ``,`` *var*\ ``,`` *expr*\ ``)``
     This operator performs a left-fold over the items in *list*. The
     variable *acc* acts as the accumulator and is initialized to *init*.
     The variable *var* is bound to each element in the *list*. The
     expression is evaluated for each element and presumably uses *acc* and
     *var* to calculate the accumulated value, which ``!foldl`` stores back in
     *acc*. The type of *acc* is the same as *init*; the type of *var* is the
     same as the elements of *list*; *expr* must have the same type as *init*.

llvm/include/llvm/TableGen/Record.h

public:
   Init *resolveReferences(Resolver &R) const override;
 
   std::string getAsString() const override;
 };
 
 /// !op (X, Y, Z) - Combine two inits.
 class TernOpInit : public OpInit, public FoldingSetNode {
 public:
-  enum TernaryOp : uint8_t { SUBST, FOREACH, FILTER, IF, DAG, SUBSTR };
+  enum TernaryOp : uint8_t { SUBST, FOREACH, FILTER, IF, DAG, SUBSTR, FIND };
 
 private:
   Init *LHS, *MHS, *RHS;
 
   TernOpInit(TernaryOp opc, Init *lhs, Init *mhs, Init *rhs,
              RecTy *Type) :
       OpInit(IK_TernOpInit, Type, opc), LHS(lhs), MHS(mhs), RHS(rhs) {}
 

llvm/lib/TableGen/Record.cpp

if (LHSs && MHSi && RHSi) {
                        std::to_string(Start));
       if (Length < 0)
         PrintError(CurRec->getLoc(), "!substr length must be nonnegative");
       return StringInit::get(LHSs->getValue().substr(Start, Length),
                              LHSs->getFormat());
     }
     break;
   }
+
+  case FIND: {
+    StringInit *LHSs = dyn_cast<StringInit>(LHS);
+    StringInit *MHSs = dyn_cast<StringInit>(MHS);
+    IntInit *RHSi = dyn_cast<IntInit>(RHS);
+    if (LHSs && MHSs && RHSi) {
+      int64_t SourceSize = LHSs->getValue().size();
+      int64_t Start = RHSi->getValue();
+      if (Start < 0 || Start > SourceSize)
+        PrintError(CurRec->getLoc(),
+                   Twine("!find start position is out of range 0...") +
+                       std::to_string(SourceSize) + ": " +
+                       std::to_string(Start));
+      auto I = LHSs->getValue().find(MHSs->getValue(), Start);
+      if (I == std::string::npos)
+        return IntInit::get(-1);
+      return IntInit::get(I);
+    }
+    break;
+  }
   }
 
   return const_cast<TernOpInit *>(this);
 }
 
 Init *TernOpInit::resolveReferences(Resolver &R) const {
   Init *lhs = LHS->resolveReferences(R);
 
std::string TernOpInit::getAsString() const {
   bool UnquotedLHS = false;
   switch (getOpcode()) {
   case DAG: Result = "!dag"; break;
   case FILTER: Result = "!filter"; UnquotedLHS = true; break;
   case FOREACH: Result = "!foreach"; UnquotedLHS = true; break;
   case IF: Result = "!if"; break;
   case SUBST: Result = "!subst"; break;
   case SUBSTR: Result = "!substr"; break;
+  case FIND: Result = "!find"; break;
   }
   return (Result + "(" +
           (UnquotedLHS ? LHS->getAsUnquotedString() : LHS->getAsString()) +
           ", " + MHS->getAsString() + ", " + RHS->getAsString() + ")");
 }
 
 static void ProfileFoldOpInit(FoldingSetNodeID &ID, Init *A, Init *B,
                               Init *Start, Init *List, Init *Expr,

llvm/lib/TableGen/TGLexer.h

enum TokKind {
     // Reserved keywords. ('ElseKW' is named to distinguish it from the
     // existing 'Else' that means the preprocessor #else.)
     Assert, Bit, Bits, Class, Code, Dag, Def, Defm, Defset, Defvar, ElseKW,
     FalseKW, Field, Foreach, If, In, Include, Int, Let, List, MultiClass,
     String, Then, TrueKW,
 
     // Bang operators.
     XConcat, XADD, XSUB, XMUL, XNOT, XAND, XOR, XXOR, XSRA, XSRL, XSHL,
-    XListConcat, XListSplat, XStrConcat, XInterleave, XSubstr, XCast,
+    XListConcat, XListSplat, XStrConcat, XInterleave, XSubstr, XFind, XCast,
     XSubst, XForEach, XFilter, XFoldl, XHead, XTail, XSize, XEmpty, XIf,
     XCond, XEq, XIsA, XDag, XNe, XLe, XLt, XGe, XGt, XSetDagOp, XGetDagOp,
 
     // Boolean literals.
     TrueVal, FalseVal,
 
     // Integer value.
     IntVal,

llvm/lib/TableGen/TGLexer.cpp

tgtok::TokKind Kind =
     .Case("foldl", tgtok::XFoldl)
     .Case("foreach", tgtok::XForEach)
     .Case("filter", tgtok::XFilter)
     .Case("listconcat", tgtok::XListConcat)
     .Case("listsplat", tgtok::XListSplat)
     .Case("strconcat", tgtok::XStrConcat)
     .Case("interleave", tgtok::XInterleave)
     .Case("substr", tgtok::XSubstr)
+    .Case("find", tgtok::XFind)
     .Cases("setdagop", "setop", tgtok::XSetDagOp) // !setop is deprecated.
     .Cases("getdagop", "getop", tgtok::XGetDagOp) // !getop is deprecated.
     .Default(tgtok::Error);
 
   return Kind != tgtok::Error ? Kind : ReturnError(Start-1, "Unknown operator");
 }
 
 bool TGLexer::prepExitInclude(bool IncludeStackMustBeEmpty) {

llvm/lib/TableGen/TGParser.h

private:  // Parser methods.
   bool ParseOptionalRangeList(SmallVectorImpl<unsigned> &Ranges);
   bool ParseOptionalBitList(SmallVectorImpl<unsigned> &Ranges);
   void ParseRangeList(SmallVectorImpl<unsigned> &Result);
   bool ParseRangePiece(SmallVectorImpl<unsigned> &Ranges,
                        TypedInit *FirstItem = nullptr);
   RecTy *ParseType();
   Init *ParseOperation(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationSubstr(Record *CurRec, RecTy *ItemType);
+  Init *ParseOperationFind(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationForEachFilter(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationCond(Record *CurRec, RecTy *ItemType);
   RecTy *ParseOperatorType();
   Init *ParseObjectName(MultiClass *CurMultiClass);
   Record *ParseClassID();
   MultiClass *ParseMultiClassID();
   bool ApplyLetStack(Record *CurRec);
   bool ApplyLetStack(RecordsEntry &Entry);
   bool CheckTemplateArgValues(SmallVectorImpl<llvm::Init *> &Values,
                               SMLoc Loc, Record *ArgsRec);
 };
 
 } // end namespace llvm
 
 #endif

llvm/lib/TableGen/TGParser.cpp

case tgtok::XSubst: { // Value ::= !ternop '(' Value ',' Value ',' Value ')'
     }
     }
     return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
   }
 
   case tgtok::XSubstr:
     return ParseOperationSubstr(CurRec, ItemType);
 
+  case tgtok::XFind:
+    return ParseOperationFind(CurRec, ItemType);
+
   case tgtok::XCond:
     return ParseOperationCond(CurRec, ItemType);
 
   case tgtok::XFoldl: {
     // Value ::= !foldl '(' Value ',' Value ',' Id ',' Id ',' Expr ')'
     Lex.Lex(); // eat the operation
     if (!consume(tgtok::l_paren)) {
       TokError("expected '(' after !foldl");
if (RHSt && !isa<IntRecTy>(RHSt->getType())) {
                RHSt->getType()->getAsString() + "'");
       return nullptr;
     }
   }
 
   return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
 }
 
+/// Parse the !find operation. Return null on error.
+///
+/// Substr ::= !find(string, string [, start-int]) => int
+Init *TGParser::ParseOperationFind(Record *CurRec, RecTy *ItemType) {
+  TernOpInit::TernaryOp Code = TernOpInit::FIND;
+  RecTy *Type = IntRecTy::get();
+
+  Lex.Lex(); // eat the operation
+
+  if (!consume(tgtok::l_paren)) {
+    TokError("expected '(' after !find operator");
+    return nullptr;
+  }
+
+  Init *LHS = ParseValue(CurRec);
+  if (!LHS)
+    return nullptr;
+
+  if (!consume(tgtok::comma)) {
+    TokError("expected ',' in !find operator");
+    return nullptr;
+  }
+
+  SMLoc MHSLoc = Lex.getLoc();
+  Init *MHS = ParseValue(CurRec);
+  if (!MHS)
+    return nullptr;
+
+  SMLoc RHSLoc = Lex.getLoc();
+  Init *RHS;
+  if (consume(tgtok::comma)) {
+    RHSLoc = Lex.getLoc();
+    RHS = ParseValue(CurRec);
+    if (!RHS)
+      return nullptr;
+  } else {
+    RHS = IntInit::get(0);
+  }
+
+  if (!consume(tgtok::r_paren)) {
+    TokError("expected ')' in !find operator");
+    return nullptr;
+  }
+
+  if (ItemType && !Type->typeIsConvertibleTo(ItemType)) {
+    Error(RHSLoc, Twine("expected value of type '") +
+                  ItemType->getAsString() + "', got '" +
+                  Type->getAsString() + "'");
+  }
+
+  TypedInit *LHSt = dyn_cast<TypedInit>(LHS);
+  if (!LHSt && !isa<UnsetInit>(LHS)) {
+    TokError("could not determine type of the source string in !find");
+    return nullptr;
+  }
+  if (LHSt && !isa<StringRecTy>(LHSt->getType())) {
+    TokError(Twine("expected string, got type '") +
+             LHSt->getType()->getAsString() + "'");
+    return nullptr;
+  }
+
+  TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
+  if (!MHSt && !isa<UnsetInit>(MHS)) {
+    TokError("could not determine type of the target string in !find");
+    return nullptr;
+  }
+  if (MHSt && !isa<StringRecTy>(MHSt->getType())) {
+    Error(MHSLoc, Twine("expected string, got type '") +
+                      MHSt->getType()->getAsString() + "'");
+    return nullptr;
+  }
+
+  if (RHS) {
+    TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
+    if (!RHSt && !isa<UnsetInit>(RHS)) {
+      TokError("could not determine type of the start position in !find");
+      return nullptr;
+    }
+    if (RHSt && !isa<IntRecTy>(RHSt->getType())) {
+      TokError(Twine("expected int, got type '") +
+               RHSt->getType()->getAsString() + "'");
+      return nullptr;
+    }
+  }
+
+  return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
+}
+
 /// Parse the !foreach and !filter operations. Return null on error.
 ///
 /// ForEach ::= !foreach(ID, list-or-dag, expr) => list<expr type>
 /// Filter  ::= !foreach(ID, list, predicate) ==> list<list type>
 Init *TGParser::ParseOperationForEachFilter(Record *CurRec, RecTy *ItemType) { 
   SMLoc OpLoc = Lex.getLoc();
   tgtok::TokKind Operation = Lex.getCode();
   Lex.Lex(); // eat the operation
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   case tgtok::XInterleave:
   case tgtok::XSetDagOp: // Value ::= !binop '(' Value ',' Value ')'
   case tgtok::XIf:
   case tgtok::XCond:
   case tgtok::XFoldl:
   case tgtok::XForEach:
   case tgtok::XFilter:
   case tgtok::XSubst:
-  case tgtok::XSubstr: { // Value ::= !ternop '(' Value ',' Value ',' Value ')'
+  case tgtok::XSubstr:
+  case tgtok::XFind: { // Value ::= !ternop '(' Value ',' Value ',' Value ')'
     return ParseOperation(CurRec, ItemType);
   }
   }
 
   return R;
 }
 
 /// ParseValue - Parse a TableGen value. This returns null on error.

llvm/test/TableGen/find.td

+// RUN: llvm-tblgen %s | FileCheck %s
+// RUN: not llvm-tblgen -DERROR1 %s 2>&1 | FileCheck --check-prefix=ERROR1 %s
+
+// This file contains tests for the !find bang operator.
+
+defvar Sentence = "This is the end of the world.";
+
+// CHECK: def Rec01
+// CHECK-NEXT:   int FirstThe = 8
+// CHECK-NEXT:   int SameThe = 8
+// CHECK-NEXT:   int SecondThe = 19
+// CHECK-NEXT:   int ThirdThe = -1
+
+def Rec01 {
+  int FirstThe = !find(Sentence, "the");
+  int SameThe = !find(Sentence, "the", FirstThe);
+  int SecondThe = !find(Sentence, "the", !add(FirstThe, 1));
+  int ThirdThe = !find(Sentence, "the", !add(SecondThe, 1));
+}
+
+class C1<string name> {
+  string Name = name;
+  bit IsJr = !ne(!find(name, "Jr"), -1);
+}
+
+// CHECK: def Rec02
+// CHECK-NEXT:   string Name = "Sally Smith"
+// CHECK-NEXT:   bit IsJr = 0
+// CHECK: def Rec03
+// CHECK-NEXT:   string Name = "Fred Jones, Jr."
+// CHECK-NEXT:   bit IsJr = 1
+
+def Rec02 : C1<"Sally Smith">;
+def Rec03 : C1<"Fred Jones, Jr.">;
+
+// CHECK: def Rec04
+// CHECK-NEXT:   int ThisPos = 0
+// CHECK-NEXT:   int WorldPos = 23
+// CHECK-NEXT:   int TooLong = -1
+
+def Rec04 {
+  int ThisPos = !find(Sentence, "This");
+  int WorldPos = !find(Sentence, "world.");
+  int TooLong = !find(Sentence, "world.country");
+}
+
+// CHECK: def Rec05
+// CHECK-NEXT:   string Name = "Pat Snork"
+// CHECK-NEXT:   bit IsJr = 0
+// CHECK-NEXT:   bit JrOrSnork = 1
+
+def Rec05 : C1<"Pat Snork"> {
+  bit JrOrSnork = !or(IsJr, !ne(!find(Name, "Snork"), -1));
+}
+
+#ifdef ERROR1
+
+// ERROR1: !find start position is out of range 0...29: 100
+
+def Rec06 {
+  int Test1 = !find(Sentence, "the", 100);
+}
+#endif
+