[clang][Interp] Implement function calls

[tbaeder]

Summary

Add a Call op and use the existing infrastructure for parameters and return values.

[tbaeder]

clang/lib/AST/Interp/Interp.cpp

60

This patch adds two const_casts. They aren't strictly necessary, since the InterpFrame doesn't need to modify the function. I have a local NFC patch to add const to a few places to make this work.

[shafik]

clang/test/AST/Interp/functions.cpp

39

I would expect a lot more test cases: trailing return types, default arguments, overloads etc...

[tbaeder]

clang/test/AST/Interp/functions.cpp

39

Things like trailing return types shouldn't make a difference here, provided they result in the same FunctionDecl. I've added support for CXXDefaultArgExprs.

[aaron.ballman]

clang/lib/AST/Interp/ByteCodeExprGen.cpp

603

614

Should this be using CallExpr::getCallReturnType() instead? (with test cases demonstrating the difference between getType() and this call)

clang/lib/AST/Interp/Interp.cpp

60

Thanks! FWIW, because this is an entirely new interface for the compiler, I'm hoping we can force some better const correctness in this part of the code base.

421–428

Spurious whitespace change?

clang/lib/AST/Interp/InterpFrame.cpp

174 ↗

(On Diff #454389)

Can you add a message to this assert so folks know what broke when you got here. Also, what about functions with no arguments?

clang/lib/AST/Interp/PrimType.h

85 ↗

(On Diff #454389)

Spurious whitespace change?

clang/test/AST/Interp/functions.cpp

2–3

I don't think we need to limit the testing to just c++14

9–10

Why testing twice?

49

It's a bit fuzzy where to draw the line on test coverage as this example is partially about function calls and partially about reference tracking. But I think we need more complex tests than what we've got so far.

constexpr void func(int &ref) {
  ref = 12;
}
constexpr int do_it() {
  int mutate_me = 0;
  func(mutate_me);
  return mutate_me;
}
static_assert(do_it() == 12, "");

constexpr int &get_ref(int &i) {
  return i;
}
constexpr int do_it_again() {
  int i = 0;
  get_ref(i) = 12;
  return i;
}
static_assert(do_it_again() == 12, "");

(Also, while working on this interpreter, please keep in mind that C is also looking to add support for constant expressions; C2x will have constexpr object definitions and we expect to widen that functionality for C2y. But this means you should keep in mind the crazy things that C can do too, like:

int oh_god_this_hurts(struct { int a; } s) {
  return s.a;
}

which could someday get a constexpr slapped in front of it.)

Speaking of C, remember that we also have C extensions, like using VM types, that should have test coverage:

constexpr int func(int n, int array[static n], int m) {
  return array[m];
}

constexpr int do_it() {
  int array[] = { 0, 1, 2, 3, 4 };
  return func(5, array, 1);
}

static_assert(do_it() == 1, "");

[tbaeder]

clang/lib/AST/Interp/ByteCodeExprGen.cpp

614

Pretty sure yes, I just didn't know about it. Can the difference only be demonstrated by using references?

clang/lib/AST/Interp/Interp.cpp

421–428

Yes, but again on purpose.

clang/lib/AST/Interp/InterpFrame.cpp

174 ↗

(On Diff #454389)

I'll move it into stackRef(), where the problem happened and where it's clear that Args should really be set at this point.

clang/lib/AST/Interp/PrimType.h

85 ↗

(On Diff #454389)

It's on purpose, I was just trying to improve this part. But I can remove it.

clang/test/AST/Interp/functions.cpp

2–3

Isn't it now just testing whatever the default is when the test is run?

9–10

The first call will compile the function in ByteCodeExprGen::VisitCallExpr() and execute it, the second one checks that visiting the same call again works. I can't test that the result is actually cached and that the compilation only happens once.

49

TBH I think references can be implemented and tested in a separate, later patch. Since I haven't tested them at all until now.

[tbaeder]

I noticed two problems:

1. Calls returning void didn't work. That needed another new opcode
2. When creating a new stackframe and running Intepret()... there's nothing actually stopping the interpreter after that stack frame. This triggered the assert(VoidResult.isAbsent()) assert I added. I modified the opcode generator to return from the enclosing function if CanReturn = 1.

[aaron.ballman]

It looks like precommit CI found some relevant failures.

clang/lib/AST/Interp/ByteCodeExprGen.cpp

614

I believe it's just references, but would have to go trace the logic through the compiler to be sure.

clang/lib/AST/Interp/PrimType.h

85 ↗

(On Diff #454389)

It's the only change to the file, so it should be removed (you can make an NFC commit to fix all the whitespace issues though!)

clang/test/AST/Interp/functions.cpp

2–3

It is, but that's our preference for tests when possible because we don't want to lose testing in newer language modes by pegging the test to an older language mode (note, we're currently exploring changes to this so you can specify a range of standards: https://reviews.llvm.org/D131464).

9–10

Ah, that's good to know! That might be worth leaving a commend in the file so nobody thinks it's redundant.

49

That's fine by me!

[aaron.ballman]

LGTM aside from some small nits you can fix when landing.

clang/lib/AST/Interp/ByteCodeExprGen.cpp

607–610

626–627

clang/lib/AST/Interp/ByteCodeExprGen.h

public:
   ByteCodeExprGen(Context &Ctx, Program &P, Tys &&... Args)
       : Emitter(Ctx, P, Args...), Ctx(Ctx), P(P) {}
 
   // Expression visitors - result returned on stack.
   bool VisitCastExpr(const CastExpr *E);
   bool VisitIntegerLiteral(const IntegerLiteral *E);
   bool VisitParenExpr(const ParenExpr *E);
   bool VisitBinaryOperator(const BinaryOperator *E);
+  bool VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E);
+  bool VisitCallExpr(const CallExpr *E);
   bool VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *E);
   bool VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *E);
   bool VisitUnaryOperator(const UnaryOperator *E);
   bool VisitDeclRefExpr(const DeclRefExpr *E);
 
 protected:
   bool visitExpr(const Expr *E) override;
   bool visitDecl(const VarDecl *VD) override;

clang/lib/AST/Interp/ByteCodeExprGen.cpp

 //===--- ByteCodeExprGen.cpp - Code generator for expressions ---*- 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 "ByteCodeExprGen.h"
 #include "ByteCodeEmitter.h"
 #include "ByteCodeGenError.h"
+#include "ByteCodeStmtGen.h"
 #include "Context.h"
 #include "Function.h"
 #include "PrimType.h"
 #include "Program.h"
 #include "State.h"
 
 using namespace clang;
 using namespace clang::interp;
if (Optional<PrimType> T = classify(VD->getType())) {
       return this->emitRetValue(VD);
     }
   }
 
   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)) {
+    const Function *Func = P.getFunction(FuncDecl);
+
+    // Templated functions might not have been compiled yet, so do it now.
+    if (!Func) {
+      if (auto R =
+              ByteCodeStmtGen<ByteCodeEmitter>(Ctx, P).compileFunc(FuncDecl))
+        Func = *R;
+    }
+    assert(Func);
+
+    QualType ReturnType = E->getCallReturnType(Ctx.getASTContext());
+    Optional<PrimType> T = classify(ReturnType);
+
+    if (T || ReturnType->isVoidType()) {
+      // Put arguments on the stack.
+      for (const auto *Arg : E->arguments()) {
+        if (!this->visit(Arg))
+          return false;
+      }
+
+      if (T)
+        return this->emitCall(*T, Func, E);
+      return this->emitCallVoid(Func, E);
+    } else {
+      assert(false && "Can't classify function return type");
+    }
+
+  } else {
+    assert(false && "We don't support non-FunctionDecl callees right now.");
+  }
+
+  return false;
+}
+
+template <class Emitter>
+bool ByteCodeExprGen<Emitter>::VisitCXXDefaultArgExpr(
+    const CXXDefaultArgExpr *E) {
+  return this->visit(E->getExpr());
+}
+
+template <class Emitter>
 bool ByteCodeExprGen<Emitter>::VisitCXXBoolLiteralExpr(
     const CXXBoolLiteralExpr *E) {
   if (DiscardResult)
     return true;
 
   return this->emitConstBool(E->getValue(), E);
 }
 

clang/lib/AST/Interp/EvalEmitter.cpp

 
 template <PrimType OpType> bool EvalEmitter::emitRet(const SourceInfo &Info) {
   if (!isActive())
     return true;
   using T = typename PrimConv<OpType>::T;
   return ReturnValue<T>(S.Stk.pop<T>(), Result);
 }
 
+template <PrimType OpType>
+bool EvalEmitter::emitCall(const Function *Func, const SourceInfo &Info) {
+
+  S.Current =
+      new InterpFrame(S, const_cast<Function *>(Func), S.Current, {}, {});
+  // Result of call will be on the stack and needs to be handled by the caller.
+  return Interpret(S, Result);
+}
+
+bool EvalEmitter::emitCallVoid(const Function *Func, const SourceInfo &Info) {
+  APValue VoidResult;
+  S.Current =
+      new InterpFrame(S, const_cast<Function *>(Func), S.Current, {}, {});
+  bool Success = Interpret(S, VoidResult);
+  assert(VoidResult.isAbsent());
+  return Success;
+}
+
 bool EvalEmitter::emitRetVoid(const SourceInfo &Info) { return true; }
 
 bool EvalEmitter::emitRetValue(const SourceInfo &Info) {
   // Method to recursively traverse composites.
   std::function<bool(QualType, const Pointer &, APValue &)> Composite;
   Composite = [this, &Composite](QualType Ty, const Pointer &Ptr, APValue &R) {
     if (auto *AT = Ty->getAs<AtomicType>())
       Ty = AT->getValueType();

clang/lib/AST/Interp/Function.h

 /// Contains links to the bytecode of the function, as well as metadata
 /// describing all arguments and stack-local variables.
 class Function {
 public:
   using ParamDescriptor = std::pair<PrimType, Descriptor *>;
 
   /// Returns the size of the function's local stack.
   unsigned getFrameSize() const { return FrameSize; }
-  /// Returns the size of the argument stackx
+  /// Returns the size of the argument stack.
   unsigned getArgSize() const { return ArgSize; }
 
   /// Returns a pointer to the start of the code.
   CodePtr getCodeBegin() const { return Code.data(); }
   /// Returns a pointer to the end of the code.
   CodePtr getCodeEnd() const { return Code.data() + Code.size(); }
 
   /// Returns the original FunctionDecl.

clang/lib/AST/Interp/Interp.cpp

if (InterpFrame *Caller = S.Current->Caller) {
     delete S.Current;
     S.Current = nullptr;
     if (!ReturnValue<T>(Ret, Result))
       return false;
   }
   return true;
 }
 
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+static bool Call(InterpState &S, CodePtr &PC, const Function *Func) {
+  S.Current =
+      new InterpFrame(S, const_cast<Function *>(Func), S.Current, PC, {});
+  APValue CallResult;
+  // Note that we cannot assert(CallResult.hasValue()) here since
+  // Ret() above only sets the APValue if the curent frame doesn't
+  // have a caller set.
+  return Interpret(S, CallResult);
+}
+
+static bool CallVoid(InterpState &S, CodePtr &PC, const Function *Func) {
+  APValue VoidResult;
+  S.Current =
+      new InterpFrame(S, const_cast<Function *>(Func), S.Current, PC, {});
+  bool Success = Interpret(S, VoidResult);
+  assert(VoidResult.isAbsent());
+
+  return Success;
+}
+
 static bool RetVoid(InterpState &S, CodePtr &PC, APValue &Result) {
   S.CallStackDepth--;
 
   assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame");
   if (!S.checkingPotentialConstantExpression())
     S.Current->popArgs();
 
   if (InterpFrame *Caller = S.Current->Caller) {

 
 bool CheckPure(InterpState &S, CodePtr OpPC, const CXXMethodDecl *MD) {
   if (!MD->isPure())
     return true;
   const SourceInfo &E = S.Current->getSource(OpPC);
   S.FFDiag(E, diag::note_constexpr_pure_virtual_call, 1) << MD;
   S.Note(MD->getLocation(), diag::note_declared_at);
   return false;
 }
+
 bool Interpret(InterpState &S, APValue &Result) {
+  // The current stack frame when we started Interpret().
+  // This is being used by the ops to determine wheter
+  // to return from this function and thus terminate
+  // interpretation.
+  const InterpFrame *StartFrame = S.Current;
   assert(!S.Current->isRoot());
   CodePtr PC = S.Current->getPC();
 
   // Empty program.
   if (!PC)
     return true;
 
   for (;;) {

clang/lib/AST/Interp/InterpFrame.h

public:
   /// Map a location to a source.
   virtual SourceInfo getSource(CodePtr PC) const;
   const Expr *getExpr(CodePtr PC) const;
   SourceLocation getLocation(CodePtr PC) const;
 
 private:
   /// Returns an original argument from the stack.
   template <typename T> const T &stackRef(unsigned Offset) {
+    assert(Args);
     return *reinterpret_cast<const T *>(Args - ArgSize + Offset);
   }
 
   /// Returns an offset to a local.
   template <typename T> T &localRef(unsigned Offset) {
     return *reinterpret_cast<T *>(Locals.get() + Offset);
   }
 

clang/lib/AST/Interp/Opcodes.td

 def ArgSint16 : ArgType { let Name = "int16_t"; }
 def ArgUint16 : ArgType { let Name = "uint16_t"; }
 def ArgSint32 : ArgType { let Name = "int32_t"; }
 def ArgUint32 : ArgType { let Name = "uint32_t"; }
 def ArgSint64 : ArgType { let Name = "int64_t"; }
 def ArgUint64 : ArgType { let Name = "uint64_t"; }
 def ArgBool : ArgType { let Name = "bool"; }
 
-def ArgFunction : ArgType { let Name = "Function *"; }
+def ArgFunction : ArgType { let Name = "const Function *"; }
 def ArgRecord : ArgType { let Name = "Record *"; }
 
 def ArgSema : ArgType { let Name = "const fltSemantics *"; }
 
 def ArgExpr : ArgType { let Name = "const Expr *"; }
 def ArgFloatingLiteral : ArgType { let Name = "const FloatingLiteral *"; }
 def ArgCXXMethodDecl : ArgType { let Name = "const CXXMethodDecl *"; }
 def ArgFunctionDecl : ArgType { let Name = "const FunctionDecl *"; }

 def RetValue : Opcode {
   let CanReturn = 1;
   let ChangesPC = 1;
   let HasCustomEval = 1;
 }
 // [] -> EXIT
 def NoRet : Opcode {}
 
+
+def Call : Opcode {
+  let Args = [ArgFunction];
+  let Types = [AllTypeClass];
+  let ChangesPC = 1;
+  let HasCustomEval = 1;
+  let HasGroup = 1;
+}
+
+def CallVoid : Opcode {
+  let Args = [ArgFunction];
+  let Types = [];
+  let ChangesPC = 1;
+  let HasCustomEval = 1;
+}
+
 //===----------------------------------------------------------------------===//
 // Frame management
 //===----------------------------------------------------------------------===//
 
 // [] -> []
 def Destroy : Opcode {
   let Args = [ArgUint32];
   let HasCustomEval = 1;

clang/test/AST/Interp/cxx20.cpp

 // RUN: %clang_cc1 -fexperimental-new-constant-interpreter -std=c++20 -verify %s
 // RUN: %clang_cc1 -std=c++20 -verify=ref %s
 
 
 // expected-no-diagnostics
 // ref-no-diagnostics
 constexpr int getMinus5() {
   int a = 10;
   a = -5;
   int *p = &a;
   return *p;
 }
-//static_assert(getMinus5() == -5, "") TODO
+static_assert(getMinus5() == -5, "");
 
 constexpr int assign() {
   int m = 10;
   int k = 12;
 
   m = (k = 20);
 
   return m;
 }
-//static_assert(assign() == 20, "");  TODO
+static_assert(assign() == 20, "");
 
 
 constexpr int pointerAssign() {
   int m = 10;
   int *p = &m;
 
   *p = 12; // modifies m
 
   return m;
 }
-//static_assert(pointerAssign() == 12, "");  TODO
+static_assert(pointerAssign() == 12, "");
 
 constexpr int pointerDeref() {
   int m = 12;
   int *p = &m;
 
   return *p;
 }
-//static_assert(pointerDeref() == 12, ""); TODO
+static_assert(pointerDeref() == 12, "");
 
 constexpr int pointerAssign2() {
   int m = 10;
   int *p = &m;
   int **pp = &p;
 
   **pp = 12;
 
   int v = **pp;
 
   return v;
 }
-//static_assert(pointerAssign2() == 12, ""); TODO
+static_assert(pointerAssign2() == 12, "");

clang/test/AST/Interp/functions.cpp

+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -verify %s
+// RUN: %clang_cc1 -verify=ref %s
+
+// expected-no-diagnostics
+// ref-no-diagnostics
+
+constexpr void doNothing() {}
+constexpr int gimme5() {
+  doNothing();
+  return 5;
+}
+static_assert(gimme5() == 5, "");
+
+
+template<typename T> constexpr T identity(T t) { return t; }
+static_assert(identity(true), "");
+static_assert(identity(true), ""); /// Compiled bytecode should be cached
+static_assert(!identity(false), "");
+
+constexpr auto add(int a, int b) -> int {
+  return identity(a) + identity(b);
+}
+
+constexpr int sub(int a, int b) {
+  return a - b;
+}
+static_assert(sub(5, 2) == 3, "");
+static_assert(sub(0, 5) == -5, "");
+
+constexpr int norm(int n) {
+  if (n >= 0) {
+    return identity(n);
+  }
+  return -identity(n);
+}
+static_assert(norm(5) == norm(-5), "");
+
+constexpr int square(int n) {
+  return norm(n) * norm(n);
+}
+static_assert(square(2) == 4, "");
+
+constexpr int add_second(int a, int b, bool doAdd = true) {
+  if (doAdd)
+    return a + b;
+  return a;
+}
+static_assert(add_second(10, 3, true) == 13, "");
+static_assert(add_second(10, 3) == 13, "");
+static_assert(add_second(300, -20, false) == 300, "");
+
+
+constexpr int sub(int a, int b, int c) {
+  return a - b - c;
+}
+static_assert(sub(10, 8, 2) == 0, "");
+
+
+constexpr int recursion(int i) {
+  doNothing();
+  i = i - 1;
+  if (i == 0)
+    return identity(0);
+
+  return recursion(i);
+}
+static_assert(recursion(10) == 0, "");

clang/utils/TableGen/ClangOpcodesEmitter.cpp

void ClangOpcodesEmitter::EmitInterp(raw_ostream &OS, StringRef N, Record *R) {
 
   Enumerate(R, N, [this, R, &OS, &N](ArrayRef<Record *> TS, const Twine &ID) {
     bool CanReturn = R->getValueAsBit("CanReturn");
     bool ChangesPC = R->getValueAsBit("ChangesPC");
     auto Args = R->getValueAsListOfDefs("Args");
 
     OS << "case OP_" << ID << ": {\n";
 
+    if (CanReturn)
+      OS << "  bool DoReturn = (S.Current == StartFrame);\n";
+
     // Emit calls to read arguments.
     for (size_t I = 0, N = Args.size(); I < N; ++I) {
       OS << "  auto V" << I;
       OS << " = ";
       OS << "ReadArg<" << Args[I]->getValueAsString("Name") << ">(S, PC);\n";
     }
 
     // Emit a call to the template method and pass arguments.
for (size_t I = 0, N = Args.size(); I < N; ++I)
       OS << ", V" << I;
     OS << "))\n";
     OS << "    return false;\n";
 
     // Bail out if interpreter returned.
     if (CanReturn) {
       OS << "  if (!S.Current || S.Current->isRoot())\n";
       OS << "    return true;\n";
+
+      OS << "  if (DoReturn)\n";
+      OS << "    return true;\n";
     }
 
     OS << "  continue;\n";
     OS << "}\n";
   });
   OS << "#endif\n";
 }