[clang][Interp] Support __builtin_clz calls

[tbaeder]

Summary

I was wondering how to best implement builtin function calls, but I don't think actually generating bytecode for them makes much sense.

[tbaeder]

clang/lib/AST/Interp/InterpBuiltin.cpp

16–19

This would also work as:

auto Arg = S.Stk.pop<unsigned int>();
auto Result = __builtin_clz(Arg);
S.Stk.push<int>(Result);
return true;

[erichkeane]

This seems right enough to me, though you might consider CTZ as well since it is equally as easy. A better/more useful attempt is going to be builtin_strlen. Note that with builtins they are going to be particularly difficult because you can't execute them on the local machine, since we have to give the same result as the target machine. Integer sizes can be a problem for that, but a lot of the builtins work differently based on which target you're running on.

clang/lib/AST/Interp/ByteCodeExprGen.cpp

954

Whats happening here? Is this leftover debugging code?

[tbaeder]

In D134958#3827024, @erichkeane wrote:

This seems right enough to me, though you might consider CTZ as well since it is equally as easy. A better/more useful attempt is going to be builtin_strlen. Note that with builtins they are going to be particularly difficult because you can't execute them on the local machine, since we have to give the same result as the target machine. Integer sizes can be a problem for that, but a lot of the builtins work differently based on which target you're running on.

Hmm, I see. Do you know of any existing tests in the clang code base that exercise those differences?

clang/lib/AST/Interp/ByteCodeExprGen.cpp

954

Oh, yep!

[erichkeane]

In D134958#3827038, @tbaeder wrote:

In D134958#3827024, @erichkeane wrote:

This seems right enough to me, though you might consider CTZ as well since it is equally as easy. A better/more useful attempt is going to be builtin_strlen. Note that with builtins they are going to be particularly difficult because you can't execute them on the local machine, since we have to give the same result as the target machine. Integer sizes can be a problem for that, but a lot of the builtins work differently based on which target you're running on.

Hmm, I see. Do you know of any existing tests in the clang code base that exercise those differences?

I don't really know all that well... I don't spend much time in target-specific builtins. I think there are a couple of the floating-point and AVX type builtins that have differences between ARM and x86 though?

[aaron.ballman]

In D134958#3827038, @tbaeder wrote:

In D134958#3827024, @erichkeane wrote:

This seems right enough to me, though you might consider CTZ as well since it is equally as easy. A better/more useful attempt is going to be builtin_strlen. Note that with builtins they are going to be particularly difficult because you can't execute them on the local machine, since we have to give the same result as the target machine. Integer sizes can be a problem for that, but a lot of the builtins work differently based on which target you're running on.

Hmm, I see. Do you know of any existing tests in the clang code base that exercise those differences?

I'm not certain on existing tests, but the kinds of things I'm thinking about are builtins around floating-point (where the host and the target may be using different floating-point semantics entirely), builtin classification functions may be sensitive to compiler options like whether we honor nans or not, security builtins like __builtin_add_overflow which may behave differently on host and target depending on the size of variable-width types like long or __builtin_strlen whose return type is size_t, etc.

[tbaeder]

Let's shelve this until later.

clang/lib/AST/CMakeLists.txt

add_clang_library(clangAST
   Interp/ByteCodeStmtGen.cpp
   Interp/Context.cpp
   Interp/Descriptor.cpp
   Interp/Disasm.cpp
   Interp/EvalEmitter.cpp
   Interp/Frame.cpp
   Interp/Function.cpp
   Interp/Interp.cpp
+  Interp/InterpBuiltin.cpp
   Interp/InterpBlock.cpp
   Interp/InterpFrame.cpp
   Interp/InterpStack.cpp
   Interp/InterpState.cpp
   Interp/Pointer.cpp
   Interp/PrimType.cpp
   Interp/Program.cpp
   Interp/Record.cpp

clang/lib/AST/Interp/ByteCodeExprGen.cpp

if (Optional<unsigned> I = P.createGlobal(VD, Init)) {
     }
   }
 
   return this->bail(VD);
 }
 
 template <class Emitter>
 bool ByteCodeExprGen<Emitter>::VisitCallExpr(const CallExpr *E) {
-  assert(!E->getBuiltinCallee() && "Builtin functions aren't supported yet");
-
   const Decl *Callee = E->getCalleeDecl();
   if (const auto *FuncDecl = dyn_cast_or_null<FunctionDecl>(Callee)) {
+    unsigned BuiltinID = E->getBuiltinCallee();
+    QualType ReturnType = E->getCallReturnType(Ctx.getASTContext());
+    Optional<PrimType> T = classify(ReturnType);
+
+    if (BuiltinID != 0) {
+      assert(*T);
+      FuncDecl->dump();
+
+      // Put arguments on the stack.
+      for (const auto *Arg : E->arguments()) {
+        if (!this->visit(Arg))
+          return false;
+      }
+      return this->emitCallBI(BuiltinID, E);
+
+    } else {
       const Function *Func = getFunction(FuncDecl);
+
       if (!Func)
         return false;
       // If the function is being compiled right now, this is a recursive call.
       // In that case, the function can't be valid yet, even though it will be
       // later.
       // If the function is already fully compiled but not constexpr, it was
       // found to be faulty earlier on, so bail out.
       if (Func->isFullyCompiled() && !Func->isConstexpr())
         return false;
 
-    QualType ReturnType = E->getCallReturnType(Ctx.getASTContext());
-    Optional<PrimType> T = classify(ReturnType);
       // Put arguments on the stack.
       for (const auto *Arg : E->arguments()) {
         if (!this->visit(Arg))
           return false;
       }
 
       // Primitive return value, just call it.
       if (T)
         return this->emitCall(*T, Func, E);
 
       // Void Return value, easy.
       if (ReturnType->isVoidType())
         return this->emitCallVoid(Func, E);
 
       // Non-primitive return value with Return Value Optimization,
       // we already have a pointer on the stack to write the result into.
       // TODO: Is this always the case?
       if (Func->hasRVO())
         return this->emitCallVoid(Func, E);
+    }
   } else {
     assert(false && "We don't support non-FunctionDecl callees right now.");
   }
 
   return false;
 }
 
 template <class Emitter>

clang/lib/AST/Interp/Interp.h

 #include "Opcode.h"
 #include "PrimType.h"
 #include "Program.h"
 #include "State.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/CXXInheritance.h"
 #include "clang/AST/Expr.h"
+#include "clang/Basic/TargetBuiltins.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APSInt.h"
 #include "llvm/Support/Endian.h"
 #include <limits>
 #include <type_traits>
 
 namespace clang {
 namespace interp {

 bool CheckCallable(InterpState &S, CodePtr OpPC, Function *F);
 
 /// Checks the 'this' pointer.
 bool CheckThis(InterpState &S, CodePtr OpPC, const Pointer &This);
 
 /// Checks if a method is pure virtual.
 bool CheckPure(InterpState &S, CodePtr OpPC, const CXXMethodDecl *MD);
 
+/// Prototypes for evaluation of builtin functions.
+/// Implemented in InterpBuiltin.cpp
+bool InterpretBuiltinClz(InterpState &S);
+
 template <typename T> inline bool IsTrue(const T &V) { return !V.isZero(); }
 
 //===----------------------------------------------------------------------===//
 // Add, Sub, Mul
 //===----------------------------------------------------------------------===//
 
 template <typename T, bool (*OpFW)(T, T, unsigned, T *),
           template <typename U> class OpAP>

 }
 
 inline bool ExpandPtr(InterpState &S, CodePtr OpPC) {
   const Pointer &Ptr = S.Stk.pop<Pointer>();
   S.Stk.push<Pointer>(Ptr.expand());
   return true;
 }
 
+inline bool CallBI(InterpState &S, CodePtr OpPC, uint32_t ID) {
+  switch (ID) {
+  case Builtin::BI__builtin_clz:
+    return InterpretBuiltinClz(S);
+
+  default:
+    return false;
+  }
+}
+
 //===----------------------------------------------------------------------===//
 // Read opcode arguments
 //===----------------------------------------------------------------------===//
 
 template <typename T> inline T ReadArg(InterpState &S, CodePtr &OpPC) {
   if constexpr (std::is_pointer<T>::value) {
     uint32_t ID = OpPC.read<uint32_t>();
     return reinterpret_cast<T>(S.P.getNativePointer(ID));

clang/lib/AST/Interp/InterpBuiltin.cpp

+//===----- InterpBuiltin.cpp - Interpret builtin functions ------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Integral.h"
+#include "InterpState.h"
+
+namespace clang {
+namespace interp {
+
+bool InterpretBuiltinClz(InterpState &S) {
+  auto Arg = S.Stk.pop<Integral<32, false>>();
+  auto Result = Arg.countLeadingZeros();
+  S.Stk.push<Integral<32, true>>(Integral<32, true>::from(Result));
+  return true;
+}
+
+} // namespace interp
+} // namespace clang

clang/lib/AST/Interp/Opcodes.td

 
 def CallVoid : Opcode {
   let Args = [ArgFunction];
   let Types = [];
   let ChangesPC = 1;
   let HasCustomEval = 1;
 }
 
+/// Call a builtin function.
+def CallBI : Opcode {
+  let Args = [ArgUint32];
+  let Types = [];
+  let ChangesPC = 1;
+}
+
 //===----------------------------------------------------------------------===//
 // Frame management
 //===----------------------------------------------------------------------===//
 
 // [] -> []
 def Destroy : Opcode {
   let Args = [ArgUint32];
   let HasCustomEval = 1;

clang/test/AST/Interp/builtins.cpp

+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -verify %s
+// RUN: %clang_cc1 -verify=ref %s
+
+// expected-no-diagnostics
+// ref-no-diagnostics
+
+
+static_assert(__builtin_clz(10) == 28, "");