[clang][Interp] Implement virtual function calls

[tbaeder]

Summary

@aaron.ballman Not sure if this (the added early return) is all you meant when you talked about virtual destructors.

I also wasn't sure about the added getOverridingFunction() - I think isDerivedFrom(..., paths) is what I should be using, but that seemed excessively hard to use.

[tbaeder]

Ping

[tbaeder]

Hmm, this doesn't work if the callee is somewhere in between the path from the dynamic to the static type, e.g.

struct A {
  virtual constexpr int foo() const { return 1; }
};

struct B : A {
  virtual constexpr int foo() const { return A::foo(); }
};

constexpr B a;
static_assert(a.foo() == 1);

For the A::foo() call, the type of the This pointer is B, so we will just select the B::foo() to call.

[aaron.ballman]

In D142630#4110839, @tbaeder wrote:

Hmm, this doesn't work if the callee is somewhere in between the path from the dynamic to the static type, e.g.

struct A {
  virtual constexpr int foo() const { return 1; }
};

struct B : A {
  virtual constexpr int foo() const { return A::foo(); }
};

constexpr B a;
static_assert(a.foo() == 1);

For the A::foo() call, the type of the This pointer is B, so we will just select the B::foo() to call.

Ah, it sounds like we're not handling qualified calls properly. That makes me think of a few more test cases:

struct A {
  virtual constexpr int foo() const { return 1; }
};

struct B : A {
  // Same behavior as your test case but with more baffling syntax. :-)
  virtual constexpr int foo() const { return this->A::foo(); }
};

constexpr B a;
static_assert(a.foo() == 1);

or with shadowed member variables (not related to virtual functions directly, but is related to qualified lookup):

struct A {
  virtual constexpr int foo() const { return 0; }
  int Val = 1;
};

struct B : A {
  virtual constexpr int foo() const { return A::Val; }
  int Val = 2;
};

constexpr B a;
static_assert(a.foo() == 1);

note, the rules are different for constructors and destructors than they are for other functions, so similar test cases involving those would be a good idea as well (though perhaps in a separate patch).

[tbaeder]

Fixed all the new test cases by adding a new CallVirt opcode and only using that if appropriate.

[tbaeder]

clang/lib/AST/Interp/Interp.h

1576

I think this test case was from the function pointer review, but this fixes:

struct S {
  virtual constexpr int func() const { return 1; }
};

struct Middle : S {
  constexpr Middle(int i) : i(i) {}
  int i;
};

struct Other {
  constexpr Other(int k) : k(k) {}
  int k;
};

struct S2 : Middle, Other {
  int j;
  constexpr S2(int i, int j, int k) : Middle(i), Other(k), j(j) {}
  virtual constexpr int func() const { return i + j + k  + S::func(); }
};


constexpr S s;
constexpr decltype(&S::func) foo = &S::func;
constexpr S2 s2(1, 2, 3);
constexpr int value3 = (s2.*foo)();

even I am confused by all of this now, so the comment might not be the clearest :)

(I did not add that test case since it needs other changes in`classify() and VisitBinaryOperator()`, but can do that in a follow-up commit.)

[tbaeder]

Ping

[aaron.ballman]

(Still thinking about the implementation work here, mostly just drive-by comments at the moment. My gut instinct is that we've not got sufficient test coverage here, but that might be partially because of other parts of the interpreter not being ready yet.)

clang/lib/AST/Interp/ByteCodeExprGen.cpp

1758–1765

Might as well simplify these a little bit.

clang/lib/AST/Interp/Interp.h

1562–1563

[tbaeder]

Add some more tests for virtual destructors.

[tbaeder]

Ping

[tbaeder]

Ping

[tbaeder]

Ping

[tbaeder]

Ping

[tbaeder]

clang/lib/AST/Interp/Interp.h

1576

Just so I don't forget: The assignment to ThisPtr here is dead.

[tbaeder]

clang/lib/AST/Interp/Interp.h

1576

Lies. I explained above that it's for the testcase. ThisPtr is a reference, so this replaces the this pointer on the stack.

[aaron.ballman]

clang/lib/AST/Interp/Interp.h

1576

Please do add the example in a follow-up.

clang/test/AST/Interp/records.cpp

516

We should also have test cases for calling virtual functions from within a constructor and a destructor, as that has special semantics. e.g., https://godbolt.org/z/snaj1zfM5

[tbaeder]

clang/test/AST/Interp/records.cpp

516

That's broken right now of course. I'l add the test and adjust the expected output. I'll probably have to save a few bits for "things we're currently doing" (like evaluating a constructor), but in a later patch.

FWIW, I expanded your test a bit: https://godbolt.org/z/vq5xT3xvq and it only fails in clang - with a reference:

// CWG issue 1517: we're constructing a base class of the object described by
// 'This', so that object has not yet begun its period of construction and
// any polymorphic operation on it results in undefined behavior.

[aaron.ballman]

LGTM

clang/test/AST/Interp/records.cpp

516

Handled in a follow-up is fine by me, thanks!

clang/lib/AST/Interp/ByteCodeExprGen.cpp

if (const FunctionDecl *FuncDecl = E->getDirectCallee()) {
     // 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;
 
     assert(HasRVO == Func->hasRVO());
 
     // In any case call the function. The return value will end up on the stack
     // and if the function has RVO, we already have the pointer on the stack to
     // write the result into.
     if (!this->emitCall(Func, E))
       return false;
 
   } else {
     // Indirect call. Visit the callee, which will leave a FunctionPointer on
     // the stack. Cleanup of the returned value if necessary will be done after
     // the function call completed.
     if (!this->visit(E->getCallee()))
       return false;
 
     this->emitCallPtr(E);
   }
 
   // Cleanup for discarded return values.
if (const CXXDestructorDecl *Dtor = R->getDestructor();
     if (DtorFunc && DtorFunc->isConstexpr()) {
       assert(DtorFunc->hasThisPointer());
       assert(DtorFunc->getNumParams() == 1);
       if (!this->emitDupPtr(SourceInfo{}))
         return false;
       if (!this->emitCall(DtorFunc, SourceInfo{}))
         return false;
     }
+    if (Dtor->isVirtual())
+      return this->emitPopPtr(SourceInfo{});
   }
 
   for (const Record::Base &Base : llvm::reverse(R->bases())) {
     if (!this->emitGetPtrBase(Base.Offset, SourceInfo{}))
       return false;
     if (!this->emitRecordDestruction(Base.Desc))
       return false;
   }

clang/lib/AST/Interp/Context.h

public:
   /// Returns the interpreter stack.
   InterpStack &getStack() { return Stk; }
   /// Returns CHAR_BIT.
   unsigned getCharBit() const;
 
   /// Classifies an expression.
   std::optional<PrimType> classify(QualType T) const;
 
+  const CXXMethodDecl *
+  getOverridingFunction(const CXXRecordDecl *DynamicDecl,
+                        const CXXRecordDecl *StaticDecl,
+                        const CXXMethodDecl *InitialFunction);
+
 private:
   /// Runs a function.
   bool Run(State &Parent, Function *Func, APValue &Result);
 
   /// Checks a result from the interpreter.
   bool Check(State &Parent, llvm::Expected<bool> &&R);
 
   /// Current compilation context.

clang/lib/AST/Interp/Context.cpp

if (Flag)
     return *Flag;
   handleAllErrors(Flag.takeError(), [&Parent](ByteCodeGenError &Err) {
     Parent.FFDiag(Err.getRange().getBegin(),
                   diag::err_experimental_clang_interp_failed)
         << Err.getRange();
   });
   return false;
 }
+
+// TODO: Virtual bases?
+const CXXMethodDecl *
+Context::getOverridingFunction(const CXXRecordDecl *DynamicDecl,
+                               const CXXRecordDecl *StaticDecl,
+                               const CXXMethodDecl *InitialFunction) {
+
+  const CXXRecordDecl *CurRecord = DynamicDecl;
+  const CXXMethodDecl *FoundFunction = InitialFunction;
+  for (;;) {
+    const CXXMethodDecl *Overrider =
+        FoundFunction->getCorrespondingMethodDeclaredInClass(CurRecord, false);
+    if (Overrider)
+      return Overrider;
+
+    // Common case of only one base class.
+    if (CurRecord->getNumBases() == 1) {
+      CurRecord = CurRecord->bases_begin()->getType()->getAsCXXRecordDecl();
+      continue;
+    }
+
+    // Otherwise, go to the base class that will lead to the StaticDecl.
+    for (const CXXBaseSpecifier &Spec : CurRecord->bases()) {
+      const CXXRecordDecl *Base = Spec.getType()->getAsCXXRecordDecl();
+      if (Base == StaticDecl || Base->isDerivedFrom(StaticDecl)) {
+        CurRecord = Base;
+        break;
+      }
+    }
+  }
+
+  llvm_unreachable(
+      "Couldn't find an overriding function in the class hierarchy?");
+  return nullptr;
+}

clang/lib/AST/Interp/Function.h

public:
   bool isConstexpr() const { return IsValid; }
 
   /// Checks if the function is virtual.
   bool isVirtual() const;
 
   /// Checks if the function is a constructor.
   bool isConstructor() const { return isa<CXXConstructorDecl>(F); }
 
+  /// Returns the parent record decl, if any.
+  const CXXRecordDecl *getParentDecl() const {
+    if (const auto *MD = dyn_cast<CXXMethodDecl>(F))
+      return MD->getParent();
+    return nullptr;
+  }
+
   /// Checks if the function is fully done compiling.
   bool isFullyCompiled() const { return IsFullyCompiled; }
 
   bool hasThisPointer() const { return HasThisPointer; }
 
   // Checks if the funtion already has a body attached.
   bool hasBody() const { return HasBody; }
 

clang/lib/AST/Interp/Interp.h

size_t ThisOffset =
         Func->getArgSize() + (Func->hasRVO() ? primSize(PT_Ptr) : 0);
     const Pointer &ThisPtr = S.Stk.peek<Pointer>(ThisOffset);
 
     if (!CheckInvoke(S, PC, ThisPtr))
       return false;
 
     if (S.checkingPotentialConstantExpression())
       return false;
+
+    // For a virtual call, we need to get the right function here.
+    if (Func->isVirtual()) {
+      // Our ThisPtr has the decl of the right type at this point,
+      // so we just need to find the function to call.
+      const CXXRecordDecl *DynamicDecl =
+          ThisPtr.getDeclDesc()->getType()->getAsCXXRecordDecl();
+      const CXXRecordDecl *StaticDecl =
+          cast<CXXRecordDecl>(Func->getParentDecl());
+      const CXXMethodDecl *InitialFunction =
+          cast<CXXMethodDecl>(Func->getDecl());
+      const CXXMethodDecl *Overrider = S.getContext().getOverridingFunction(
+          DynamicDecl, StaticDecl, InitialFunction);
+      if (Overrider != InitialFunction)
+        Func = S.P.getFunction(Overrider);
+    }
   }
 
   if (!CheckCallable(S, PC, Func))
     return false;
 
   auto NewFrame = std::make_unique<InterpFrame>(S, Func, PC);
   InterpFrame *FrameBefore = S.Current;
   S.Current = NewFrame.get();
inline bool CallBI(InterpState &S, CodePtr &PC, const Function *Func) {
   auto NewFrame = std::make_unique<InterpFrame>(S, Func, PC);
 
   InterpFrame *FrameBefore = S.Current;
   S.Current = NewFrame.get();
 
   if (InterpretBuiltin(S, PC, Func->getBuiltinID())) {
     NewFrame.release();
     return true;
   }
   S.Current = FrameBefore;
   return false;
 }
 
 inline bool CallPtr(InterpState &S, CodePtr &PC) {
   const FunctionPointer &FuncPtr = S.Stk.pop<FunctionPointer>();
 
   const Function *F = FuncPtr.getFunction();
   if (!F || !F->isConstexpr())
     return false;
 
   return Call(S, PC, F);
 }
 
 inline bool GetFnPtr(InterpState &S, CodePtr &PC, const Function *Func) {
   assert(Func);
   S.Stk.push<FunctionPointer>(Func);
   return true;
 }
 
 //===----------------------------------------------------------------------===//
 // Read opcode arguments

clang/lib/AST/Interp/InterpState.h

public:
   /// Deallocates a pointer.
   void deallocate(Block *B);
 
   /// Delegates source mapping to the mapper.
   SourceInfo getSource(const Function *F, CodePtr PC) const override {
     return M ? M->getSource(F, PC) : F->getSource(PC);
   }
 
+  Context &getContext() const { return Ctx; }
+
 private:
   /// AST Walker state.
   State &Parent;
   /// Dead block chain.
   DeadBlock *DeadBlocks = nullptr;
   /// Reference to the offset-source mapping.
   SourceMapper *M;
 

clang/test/AST/Interp/records.cpp

 // RUN: %clang_cc1 -fexperimental-new-constant-interpreter -verify %s
 // RUN: %clang_cc1 -fexperimental-new-constant-interpreter -std=c++14 -verify %s
+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -std=c++20 -verify %s
 // RUN: %clang_cc1 -fexperimental-new-constant-interpreter -triple i686 -verify %s
 // RUN: %clang_cc1 -verify=ref %s
 // RUN: %clang_cc1 -verify=ref -std=c++14 %s
+// RUN: %clang_cc1 -verify=ref -std=c++20 %s
 // RUN: %clang_cc1 -verify=ref -triple i686 %s
 
 struct BoolPair {
   bool first;
   bool second;
 };
 
 struct Ints {
class D : private A, private B {
     constexpr int getB() const { return b; }
   };
   constexpr D d = {};
   static_assert(d.getA() == 20, "");
   static_assert(d.getB() == 30, "");
 };
 
 namespace DeriveFailures {
+#if __cplusplus < 202002L
   struct Base { // ref-note 2{{declared here}}
     int Val;
   };
 
   struct Derived : Base {
     int OtherVal;
 
     constexpr Derived(int i) : OtherVal(i) {} // ref-error {{never produces a constant expression}} \
                                               // ref-note 2{{non-constexpr constructor 'Base' cannot be used in a constant expression}}
   };
 
   constexpr Derived D(12); // ref-error {{must be initialized by a constant expression}} \
                            // ref-note {{in call to 'Derived(12)'}} \
                            // ref-note {{declared here}} \
                            // expected-error {{must be initialized by a constant expression}}
+
   static_assert(D.Val == 0, ""); // ref-error {{not an integral constant expression}} \
                                  // ref-note {{initializer of 'D' is not a constant expression}} \
                                  // expected-error {{not an integral constant expression}} \
                                  // expected-note {{read of object outside its lifetime}}
+#endif
 
   struct AnotherBase {
     int Val;
     constexpr AnotherBase(int i) : Val(12 / i) {} //ref-note {{division by zero}} \
                                                   //expected-note {{division by zero}}
   };
 
   struct AnotherDerived : AnotherBase {
namespace ConditionalInit {
 
   constexpr S getS(bool b) {
     return b ? S{12} : S{13};
   }
 
   static_assert(getS(true).a == 12, "");
   static_assert(getS(false).a == 13, "");
 };
+
+#if __cplusplus >= 202002L
+namespace VirtualCalls {
+namespace Obvious {
+
+  class A {
+  public:
+    constexpr A(){}
+    constexpr virtual int foo() {
+      return 3;
+    }
+  };
+  class B : public A {
+  public:
+    constexpr int foo() override {
+      return 6;
+    }
+  };
+
+  constexpr int getFooB(bool b) {
+    A *a;
+    A myA;
+    B myB;
+
+    if (b)
+      a = &myA;
+    else
+      a = &myB;
+
+    return a->foo();
+  }
+  static_assert(getFooB(true) == 3, "");
+  static_assert(getFooB(false) == 6, "");
+}
+
+namespace MultipleBases {
+  class A {
+  public:
+    constexpr virtual int getInt() const { return 10; }
+  };
+  class B {
+  public:
+  };
+  class C : public A, public B {
+  public:
+    constexpr int getInt() const override { return 20; }
+  };
+
+  constexpr int callGetInt(const A& a) { return a.getInt(); }
+  static_assert(callGetInt(C()) == 20, "");
+  static_assert(callGetInt(A()) == 10, "");
+}
+
+namespace Destructors {
+  class Base {
+  public:
+    int i;
+    constexpr Base(int &i) : i(i) {i++;}
+    constexpr virtual ~Base() {i--;}
+  };
+
+  class Derived : public Base {
+  public:
+    constexpr Derived(int &i) : Base(i) {}
+    constexpr virtual ~Derived() {i--;}
+  };
+
+  constexpr int test() {
+    int i = 0;
+    Derived d(i);
+    return i;
+  }
+  static_assert(test() == 1);
+}
+
+
+
+};
+#endif