[TableGen] Add logtwo bang operator

[michaelmaitland]

Summary

This patch adds base 2 logarithm that returns integer result. I initially wanted to name it !log2,
but numbers are not permitted in the name. The documentation makes sure to clarify that it is
base 2 since it is not explicit in the operator name.

I also used ERROR3 and ERROR4 in the test files since there is another patch that has not
landed yet that uses ERROR1 and ERROR2: https://reviews.llvm.org/D134001

[craig.topper]

llvm/docs/TableGen/ProgRef.rst

1744

I find myself wondering if logtwo would be a better name?

[michaelmaitland]

Rename log -> logtwo

[craig.topper]

llvm/lib/TableGen/Record.cpp

899

Reuse LHsv here

[michaelmaitland]

Reused LHSv

[michaelmaitland]

Rebase main to resolve conflicts from revision D134001

[barannikov88]

llvm/docs/TableGen/ProgRef.rst

1745

Worth noting that this is a flooring operation?

[nhaehnle]

Agree that the flooring should be noted in the document for completeness. Apart from that this LGTM.

llvm/docs/TableGen/ProgRef.rst

 TableGen provides "bang operators" that have a wide variety of uses:
 
 .. productionlist::
    BangOperator: one of
                : !add        !and         !cast        !con         !dag
                : !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
+               : !listsplat  !log         !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.
``!listconcat(``\ *list1*\ ``,`` *list2*\ ``, ...)``
     This operator concatenates the list arguments *list1*, *list2*, etc., and
     produces the resulting list. The lists must have the same element type.
 
 ``!listsplat(``\ *value*\ ``,`` *count*\ ``)``
     This operator produces a list of length *count* whose elements are all
     equal to the *value*. For example, ``!listsplat(42, 3)`` results in
     ``[42, 42, 42]``.
 
+``!log(``\ *a*\ ``)``
+    This operator produces the base 2 log of *a* and produces the integer
+    result. The log of 0 or a negative number produces an error.
+
 ``!lt(``\ *a*\ `,` *b*\ ``)``
     This operator produces 1 if *a* is less than *b*; 0 otherwise.
     The arguments must be ``bit``, ``bits``, ``int``, or ``string`` values.
 
 ``!mul(``\ *a*\ ``,`` *b*\ ``, ...)``
     This operator multiplies *a*, *b*, etc., and produces the product.
 
 ``!ne(``\ *a*\ `,` *b*\ ``)``

llvm/include/llvm/TableGen/Record.h

public:
 
   Init *getBit(unsigned Bit) const override;
 };
 
 /// !op (X) - Transform an init.
 ///
 class UnOpInit : public OpInit, public FoldingSetNode {
 public:
-  enum UnaryOp : uint8_t { CAST, NOT, HEAD, TAIL, SIZE, EMPTY, GETDAGOP };
+  enum UnaryOp : uint8_t { CAST, NOT, HEAD, TAIL, SIZE, EMPTY, GETDAGOP, LOG2 };
 
 private:
   Init *LHS;
 
   UnOpInit(UnaryOp opc, Init *lhs, RecTy *Type)
     : OpInit(IK_UnOpInit, Type, opc), LHS(lhs) {}
 
 public:

llvm/lib/TableGen/Record.cpp

 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Support/SMLoc.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Error.h"
 #include <cassert>
 #include <cstdint>
 #include <map>
 #include <memory>
 #include <string>
if (DagInit *Dag = dyn_cast<DagInit>(LHS)) {
                         getType()->getAsString() + "', got '" +
                         DI->getType()->getAsString() + "' in: " +
                         getAsString() + "\n");
       } else {
         return DI;
       }
     }
     break;
+
+  case LOG2:
+    if (IntInit *LHSi = dyn_cast_or_null<IntInit>(
+            LHS->convertInitializerTo(IntRecTy::get(RK)))) {
+      int64_t LHSv = LHSi->getValue();
+      if (LHSv <= 0) {
+        PrintFatalError(CurRec->getLoc(),
+                        "Illegal operation: log is undefined "
+                        "on arguments less than or equal to 0");
+      } else {
+        uint64_t Log = Log2_64(LHSi->getValue());
+        assert(Log <= INT64_MAX &&
+               "Log of an int64_t must be smaller than INT64_MAX");
+        return IntInit::get(RK, static_cast<int64_t>(Log));
+      }
+    }
+    break;
   }
   return const_cast<UnOpInit *>(this);
 }
 
 Init *UnOpInit::resolveReferences(Resolver &R) const {
   Init *lhs = LHS->resolveReferences(R);
 
   if (LHS != lhs || (R.isFinal() && getOpcode() == CAST))
     return (UnOpInit::get(getOpcode(), lhs, getType()))
         ->Fold(R.getCurrentRecord(), R.isFinal());
   return const_cast<UnOpInit *>(this);
 }
 
 std::string UnOpInit::getAsString() const {
   std::string Result;
   switch (getOpcode()) {
   case CAST: Result = "!cast<" + getType()->getAsString() + ">"; break;
   case NOT: Result = "!not"; break;
   case HEAD: Result = "!head"; break;
   case TAIL: Result = "!tail"; break;
   case SIZE: Result = "!size"; break;
   case EMPTY: Result = "!empty"; break;
   case GETDAGOP: Result = "!getdagop"; break;
+  case LOG2 : Result = "!log"; break;
   }
   return Result + "(" + LHS->getAsString() + ")";
 }
 
 static void
 ProfileBinOpInit(FoldingSetNodeID &ID, unsigned Opcode, Init *LHS, Init *RHS,
                  RecTy *Type) {
   ID.AddInteger(Opcode);

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,
+    XConcat, XADD, XSUB, XMUL, XNOT, XLOG2, XAND, XOR, XXOR, XSRA, XSRL, XSHL,
     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,
     XExists,
 
     // Boolean literals.
     TrueVal, FalseVal,
 

llvm/lib/TableGen/TGLexer.cpp

tgtok::TokKind Kind =
     .Case("tail", tgtok::XTail)
     .Case("size", tgtok::XSize)
     .Case("con", tgtok::XConcat)
     .Case("dag", tgtok::XDag)
     .Case("add", tgtok::XADD)
     .Case("sub", tgtok::XSUB)
     .Case("mul", tgtok::XMUL)
     .Case("not", tgtok::XNOT)
+    .Case("log", tgtok::XLOG2)
     .Case("and", tgtok::XAND)
     .Case("or", tgtok::XOR)
     .Case("xor", tgtok::XXOR)
     .Case("shl", tgtok::XSHL)
     .Case("sra", tgtok::XSRA)
     .Case("srl", tgtok::XSRL)
     .Case("cast", tgtok::XCast)
     .Case("empty", tgtok::XEmpty)

llvm/lib/TableGen/TGParser.cpp

 /// Operation ::= XOperator ['<' Type '>'] '(' Args ')'
 ///
 Init *TGParser::ParseOperation(Record *CurRec, RecTy *ItemType) {
   switch (Lex.getCode()) {
   default:
     TokError("unknown bang operator");
     return nullptr;
   case tgtok::XNOT:
+  case tgtok::XLOG2:
   case tgtok::XHead:
   case tgtok::XTail:
   case tgtok::XSize:
   case tgtok::XEmpty:
   case tgtok::XCast:
   case tgtok::XGetDagOp: { // Value ::= !unop '(' Value ')'
     UnOpInit::UnaryOp Code;
     RecTy *Type = nullptr;
case tgtok::XCast:
       }
 
       break;
     case tgtok::XNOT:
       Lex.Lex();  // eat the operation
       Code = UnOpInit::NOT;
       Type = IntRecTy::get(Records);
       break;
+    case tgtok::XLOG2:
+      Lex.Lex();  // eat the operation
+      Code = UnOpInit::LOG2;
+      Type = IntRecTy::get(Records);
+      break;
     case tgtok::XHead:
       Lex.Lex();  // eat the operation
       Code = UnOpInit::HEAD;
       break;
     case tgtok::XTail:
       Lex.Lex();  // eat the operation
       Code = UnOpInit::TAIL;
       break;
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   case tgtok::XExists:
   case tgtok::XIsA:
   case tgtok::XConcat:
   case tgtok::XDag:
   case tgtok::XADD:
   case tgtok::XSUB:
   case tgtok::XMUL:
   case tgtok::XNOT:
+  case tgtok::XLOG2:
   case tgtok::XAND:
   case tgtok::XOR:
   case tgtok::XXOR:
   case tgtok::XSRA:
   case tgtok::XSRL:
   case tgtok::XSHL:
   case tgtok::XEq:
   case tgtok::XNe:

llvm/test/TableGen/math.td

 // RUN: llvm-tblgen %s | FileCheck %s
+// RUN: not llvm-tblgen -DERROR3 %s 2>&1 | FileCheck --check-prefix=ERROR3 %s
+// RUN: not llvm-tblgen -DERROR4 %s 2>&1 | FileCheck --check-prefix=ERROR4 %s
 // XFAIL: vg_leak
 
 // CHECK: def shifts
 // CHECK: shifted_b = 8
 // CHECK: shifted_i = 8
 def shifts {
     bits<2> b = 0b10;
     int i = 2;

 // CHECK: def v924
 // CHECK: Value = 924
 def v924   : Int<!mul(v84.Value, 11)>;
 
 // CHECK: def v925
 // CHECK: Value = 925
 def v925 : Int<!sub(v924.Value, -1)>;
 
+// CHECK: def v950
+// CHECK: Value = 4
+def v950: Int<!log(16)>;
+
+// CHECK: def v951
+// CHECK: Value = 10
+def v951 : Int<!log(1024)>;
+
+// CHECK: def v952
+// CHECK: Value = 10
+def v952 : Int<!log(1025)>;
+
+#ifdef ERROR3
+// ERROR3: error: Illegal operation: log is undefined on arguments less than or equal to 0
+def v953 : Int<!log(0)>;
+#endif
+
+#ifdef ERROR4
+// ERROR4: error: Illegal operation: log is undefined on arguments less than or equal to 0
+def v954 : Int<!log(-1)>;
+#endif
+
 // CHECK: def vneg
 // CHECK: Value = -2
-def vneg : Int<!sub(v925.Value, 927)>;
+def vneg : Int<!sub(v925.Value, 927)>;