[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

1648

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

1715–1722

Might as well simplify these a little bit.

clang/lib/AST/Interp/Interp.h

1634–1635

[tbaeder]

Add some more tests for virtual destructors.

[tbaeder]

Ping

[tbaeder]

Ping

[tbaeder]

Ping

[tbaeder]

Ping

[tbaeder]

clang/lib/AST/Interp/Interp.h

1648

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

[tbaeder]

clang/lib/AST/Interp/Interp.h

1648

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

1648

Please do add the example in a follow-up.

clang/test/AST/Interp/records.cpp

650

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

650

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

650

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

clang/lib/AST/Interp/ByteCodeExprGen.cpp

if (const FunctionDecl *FuncDecl = E->getDirectCallee()) {
     // 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;
 
     assert(HasRVO == Func->hasRVO());
 
+    bool HasQualifier = false;
+    if (const auto *ME = dyn_cast<MemberExpr>(E->getCallee()))
+      HasQualifier = ME->hasQualifier();
+
+    bool IsVirtual = false;
+    if (const auto *MD = dyn_cast<CXXMethodDecl>(FuncDecl))
+      IsVirtual = MD->isVirtual();
+
     // 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 (IsVirtual && !HasQualifier) {
+      if (!this->emitCallVirt(Func, E))
+        return false;
+    } else {
       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;
 
     if (!this->emitCallPtr(E))

clang/lib/AST/Interp/Context.h

public:
   /// Returns CHAR_BIT.
   unsigned getCharBit() const;
   /// Return the floating-point semantics for T.
   const llvm::fltSemantics &getFloatSemantics(QualType T) const;
 
   /// Classifies an expression.
   std::optional<PrimType> classify(QualType T) const;
 
+  const CXXMethodDecl *
+  getOverridingFunction(const CXXRecordDecl *DynamicDecl,
+                        const CXXRecordDecl *StaticDecl,
+                        const CXXMethodDecl *InitialFunction) const;
+
 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 {
+
+  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/Descriptor.cpp

Descriptor::Descriptor(const DeclTy &D, Record *R, MetadataSize MD,
   assert(Source && "Missing source");
 }
 
 QualType Descriptor::getType() const {
   if (auto *E = asExpr())
     return E->getType();
   if (auto *D = asValueDecl())
     return D->getType();
+  if (auto *T = dyn_cast<TypeDecl>(asDecl()))
+    return QualType(T->getTypeForDecl(), 0);
   llvm_unreachable("Invalid descriptor type");
 }
 
 SourceLocation Descriptor::getLocation() const {
   if (auto *D = Source.dyn_cast<const Decl *>())
     return D->getLocation();
   if (auto *E = Source.dyn_cast<const Expr *>())
     return E->getExprLoc();

clang/lib/AST/Interp/Function.h

public:
   /// Checks if the function is virtual.
   bool isVirtual() const;
 
   /// Checks if the function is a constructor.
   bool isConstructor() const { return isa<CXXConstructorDecl>(F); }
   /// Checks if the function is a destructor.
   bool isDestructor() const { return isa<CXXDestructorDecl>(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

inline bool Call(InterpState &S, CodePtr OpPC, const Function *Func) {
   }
 
   // Interpreting the function failed somehow. Reset to
   // previous state.
   S.Current = FrameBefore;
   return false;
 }
 
+inline bool CallVirt(InterpState &S, CodePtr OpPC, const Function *Func) {
+  assert(Func->hasThisPointer());
+  assert(Func->isVirtual());
+  size_t ThisOffset =
+      Func->getArgSize() + (Func->hasRVO() ? primSize(PT_Ptr) : 0);
+  Pointer &ThisPtr = S.Stk.peek<Pointer>(ThisOffset);
+
+  const CXXRecordDecl *DynamicDecl =
+      ThisPtr.getDeclDesc()->getType()->getAsCXXRecordDecl();
+  const auto *StaticDecl = cast<CXXRecordDecl>(Func->getParentDecl());
+  const auto *InitialFunction = cast<CXXMethodDecl>(Func->getDecl());
+  const CXXMethodDecl *Overrider = S.getContext().getOverridingFunction(
+      DynamicDecl, StaticDecl, InitialFunction);
+
+  if (Overrider != InitialFunction)
+    Func = S.P.getFunction(Overrider);
+
+  return Call(S, OpPC, Func);
+}
+
 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;

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/lib/AST/Interp/Opcodes.td

 def NoRet : Opcode {}
 
 
 def Call : Opcode {
   let Args = [ArgFunction];
   let Types = [];
 }
 
+def CallVirt : Opcode {
+  let Args = [ArgFunction];
+  let Types = [];
+}
+
 def CallBI : Opcode {
   let Args = [ArgFunction];
   let Types = [];
 }
 
 def CallPtr : Opcode {
   let Args = [];
   let Types = [];

clang/lib/AST/Interp/Pointer.h

Descriptor *getFieldDesc() const {
     if (Base == 0 || Base == RootPtrMark)
       return getDeclDesc();
     return getInlineDesc()->Desc;
   }
 
   /// Returns the type of the innermost field.
   QualType getType() const { return getFieldDesc()->getType(); }
 
+  Pointer getDeclPtr() const { return Pointer(Pointee); }
+
   /// Returns the element size of the innermost field.
   size_t elemSize() const {
     if (Base == RootPtrMark)
       return getDeclDesc()->getSize();
     return getFieldDesc()->getElemSize();
   }
   /// Returns the total size of the innermost field.
   size_t getSize() const { return getFieldDesc()->getSize(); }

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}} expected-note {{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}} \
                                               // expected-note {{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}} \
                            // expected-note {{in call to 'Derived(12)'}}
+
   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 DeclRefs {
   constexpr B b;
   /// FIXME: The following two lines don't work because we don't get the
   ///   pointers on the LHS correct. They make us run into an assertion
   ///   in CheckEvaluationResult. However, this may just be caused by the
   ///   problems in the previous examples.
   //static_assert(b.a.m == 100, "");
   //static_assert(b.a.f == 100, "");
 }
+
+#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);
+}
+
+
+namespace VirtualDtors {
+  class A {
+  public:
+    unsigned &v;
+    constexpr A(unsigned &v) : v(v) {}
+    constexpr virtual ~A() {
+      v |= (1 << 0);
+    }
+  };
+  class B : public A {
+  public:
+    constexpr B(unsigned &v) : A(v) {}
+    constexpr virtual ~B() {
+      v |= (1 << 1);
+    }
+  };
+  class C : public B {
+  public:
+    constexpr C(unsigned &v) : B(v) {}
+    constexpr virtual ~C() {
+      v |= (1 << 2);
+    }
+  };
+
+  constexpr bool foo() {
+    unsigned a = 0;
+    {
+      C c(a);
+    }
+    return ((a & (1 << 0)) && (a & (1 << 1)) && (a & (1 << 2)));
+  }
+
+  static_assert(foo());
+
+
+};
+
+namespace QualifiedCalls {
+  class A {
+      public:
+      constexpr virtual int foo() const {
+          return 5;
+      }
+  };
+  class B : public A {};
+  class C : public B {
+      public:
+      constexpr int foo() const override {
+          return B::foo(); // B doesn't have a foo(), so this should call A::foo().
+      }
+      constexpr int foo2() const {
+        return this->A::foo();
+      }
+  };
+  constexpr C c;
+  static_assert(c.foo() == 5);
+  static_assert(c.foo2() == 5);
+
+
+  struct S {
+    int _c = 0;
+    virtual constexpr int foo() const { return 1; }
+  };
+
+  struct SS : S {
+    int a;
+    constexpr SS() {
+      a = S::foo();
+    }
+    constexpr int foo() const override {
+      return S::foo();
+    }
+  };
+
+  constexpr SS ss;
+  static_assert(ss.a == 1);
+}
+};
+#endif