[clang][Interp] Add frame depth checking

[tbaeder]

Summary

There was already some form of this, but it wasn't working. I moved the depth tracking from InterpState to InterpFrame so remove some of the magic from the Ret instructions.

[tbaeder]

Move things around a bit and add some + 1s to get matching diagnostic output with the current interpreter.

[tbaeder]

Ping

[shafik]

The changes make sense, I am sure about any trade-offs of doing the checking during the call Vs doing at return.

[tbaeder]

Ping

[aaron.ballman]

clang/lib/AST/Interp/Interp.cpp

345–352

-fconstexpr-depth sets the number of *recursive* constexpr calls, but this looks like it's measuring the depth of the call stack regardless of whether there's recursion or not. Can you add a test where you set this value to something low and make nested calls that exceed that depth?

(Also, there's -fconstexpr-steps https://clang.llvm.org/docs/UsersManual.html#cmdoption-fconstexpr-steps we'll need to support at some point, in case you weren't aware of the option.)

[aaron.ballman]

LGTM, though I would appreciate adding the other test case from my comments since it's interesting behavior.

clang/lib/AST/Interp/Interp.cpp

345–352

Whelp, TIL that our docs are wrong and should be updated (I'll take care of that): https://godbolt.org/z/ahPjPnhGr

It has nothing to do with recursion, that's just the way in which you'd typically run into it.

[tbaeder]

clang/lib/AST/Interp/Interp.cpp

345–352

I know about -fconstexpr-steps, but the notion of "steps" is implementation dependent, isn't it? I.e. I could just cal a "step" the execution of one opcode?

clang/lib/AST/Interp/Interp.h

 bool CheckInvoke(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
 
 /// Checks if a value can be initialized.
 bool CheckInit(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
 
 /// Checks if a method can be called.
 bool CheckCallable(InterpState &S, CodePtr OpPC, const Function *F);
 
+/// Checks if calling the currently active function would exceed
+/// the allowed call depth.
+bool CheckCallDepth(InterpState &S, CodePtr OpPC);
+
 /// 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);
 
 /// Checks that all fields are initialized after a constructor call.
 bool CheckCtorCall(InterpState &S, CodePtr OpPC, const Pointer &This);

 
 //===----------------------------------------------------------------------===//
 // Returning values
 //===----------------------------------------------------------------------===//
 
 template <PrimType Name, bool Builtin = false,
           class T = typename PrimConv<Name>::T>
 bool Ret(InterpState &S, CodePtr &PC, APValue &Result) {
-  S.CallStackDepth--;
   const T &Ret = S.Stk.pop<T>();
 
   assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame");
   if (Builtin || !S.checkingPotentialConstantExpression())
     S.Current->popArgs();
 
   if (InterpFrame *Caller = S.Current->Caller) {
     PC = S.Current->getRetPC();
     delete S.Current;
     S.Current = Caller;
     S.Stk.push<T>(Ret);
   } else {
     delete S.Current;
     S.Current = nullptr;
     if (!ReturnValue<T>(Ret, Result))
       return false;
   }
   return true;
 }
 
 template <bool Builtin = false>
 inline bool RetVoid(InterpState &S, CodePtr &PC, APValue &Result) {
-  S.CallStackDepth--;
-
   assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame");
   if (Builtin || !S.checkingPotentialConstantExpression())
     S.Current->popArgs();
 
   if (InterpFrame *Caller = S.Current->Caller) {
     PC = S.Current->getRetPC();
     delete S.Current;
     S.Current = Caller;
if (Func->hasThisPointer()) {
 
     if (S.checkingPotentialConstantExpression())
       return false;
   }
 
   if (!CheckCallable(S, OpPC, Func))
     return false;
 
+  if (!CheckCallDepth(S, OpPC))
+    return false;
+
   auto NewFrame = std::make_unique<InterpFrame>(S, Func, OpPC);
   InterpFrame *FrameBefore = S.Current;
   S.Current = NewFrame.get();
 
   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.

clang/lib/AST/Interp/Interp.cpp

if (S.getLangOpts().CPlusPlus11) {
       S.FFDiag(Loc, diag::note_invalid_subexpr_in_const_expr);
     }
     return false;
   }
 
   return true;
 }
 
+bool CheckCallDepth(InterpState &S, CodePtr OpPC) {
+  if ((S.Current->getDepth() + 1) > S.getLangOpts().ConstexprCallDepth) {
+    S.FFDiag(S.Current->getSource(OpPC),
+             diag::note_constexpr_depth_limit_exceeded)
+        << S.getLangOpts().ConstexprCallDepth;
+    return false;
+  }
+
+  return true;
+}
+
 bool CheckThis(InterpState &S, CodePtr OpPC, const Pointer &This) {
   if (!This.isZero())
     return true;
 
   const SourceInfo &Loc = S.Current->getSource(OpPC);
 
   bool IsImplicit = false;
   if (auto *E = dyn_cast_if_present<CXXThisExpr>(Loc.asExpr()))

clang/lib/AST/Interp/InterpFrame.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_INTERP_INTERPFRAME_H
 #define LLVM_CLANG_AST_INTERP_INTERPFRAME_H
 
 #include "Frame.h"
 #include "Program.h"
-#include "State.h"
 #include <cstdint>
 #include <vector>
 
 namespace clang {
 namespace interp {
 class Function;
 class InterpState;
 class Pointer;
public:
   /// Returns the return address of the frame.
   CodePtr getRetPC() const { return RetPC; }
 
   /// Map a location to a source.
   virtual SourceInfo getSource(CodePtr PC) const;
   const Expr *getExpr(CodePtr PC) const;
   SourceLocation getLocation(CodePtr PC) const;
 
+  unsigned getDepth() const { return Depth; }
+
 private:
   /// Returns an original argument from the stack.
   template <typename T> const T &stackRef(unsigned Offset) const {
     assert(Args);
     return *reinterpret_cast<const T *>(Args - ArgSize + Offset);
   }
 
   /// Returns an offset to a local.
private:
   // Returns the inline descriptor of the local.
   InlineDescriptor *localInlineDesc(unsigned Offset) const {
     return reinterpret_cast<InlineDescriptor *>(Locals.get() + Offset);
   }
 
 private:
   /// Reference to the interpreter state.
   InterpState &S;
+  /// Depth of this frame.
+  unsigned Depth;
   /// Reference to the function being executed.
   const Function *Func;
   /// Current object pointer for methods.
   Pointer This;
   /// Pointer the non-primitive return value gets constructed in.
   Pointer RVOPtr;
   /// Return address.
   CodePtr RetPC;

clang/lib/AST/Interp/InterpFrame.cpp

 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclCXX.h"
 
 using namespace clang;
 using namespace clang::interp;
 
 InterpFrame::InterpFrame(InterpState &S, const Function *Func,
                          InterpFrame *Caller, CodePtr RetPC)
-    : Caller(Caller), S(S), Func(Func), RetPC(RetPC),
-      ArgSize(Func ? Func->getArgSize() : 0),
+    : Caller(Caller), S(S), Depth(Caller ? Caller->Depth + 1 : 0), Func(Func),
+      RetPC(RetPC), ArgSize(Func ? Func->getArgSize() : 0),
       Args(static_cast<char *>(S.Stk.top())), FrameOffset(S.Stk.size()) {
   if (!Func)
     return;
 
   unsigned FrameSize = Func->getFrameSize();
   if (FrameSize == 0)
     return;
 

clang/lib/AST/Interp/InterpState.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_INTERP_INTERPSTATE_H
 #define LLVM_CLANG_AST_INTERP_INTERPSTATE_H
 
 #include "Context.h"
 #include "Function.h"
+#include "InterpFrame.h"
 #include "InterpStack.h"
 #include "State.h"
 #include "clang/AST/APValue.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/OptionalDiagnostic.h"
 
 namespace clang {
public:
   InterpState(State &Parent, Program &P, InterpStack &Stk, Context &Ctx,
               SourceMapper *M = nullptr);
 
   ~InterpState();
 
   // Stack frame accessors.
   Frame *getSplitFrame() { return Parent.getCurrentFrame(); }
   Frame *getCurrentFrame() override;
-  unsigned getCallStackDepth() override { return CallStackDepth; }
+  unsigned getCallStackDepth() override {
+    return Current ? (Current->getDepth() + 1) : 1;
+  }
   const Frame *getBottomFrame() const override {
     return Parent.getBottomFrame();
   }
 
   // Access objects from the walker context.
   Expr::EvalStatus &getEvalStatus() const override {
     return Parent.getEvalStatus();
   }
public:
   /// Reference to the module containing all bytecode.
   Program &P;
   /// Temporary stack.
   InterpStack &Stk;
   /// Interpreter Context.
   Context &Ctx;
   /// The current frame.
   InterpFrame *Current = nullptr;
-  /// Call stack depth.
-  unsigned CallStackDepth;
 };
 
 } // namespace interp
 } // namespace clang
 
 #endif

clang/lib/AST/Interp/InterpState.cpp

 #include "Program.h"
 #include "State.h"
 
 using namespace clang;
 using namespace clang::interp;
 
 InterpState::InterpState(State &Parent, Program &P, InterpStack &Stk,
                          Context &Ctx, SourceMapper *M)
-    : Parent(Parent), M(M), P(P), Stk(Stk), Ctx(Ctx), Current(nullptr),
-      CallStackDepth(Parent.getCallStackDepth() + 1) {}
+    : Parent(Parent), M(M), P(P), Stk(Stk), Ctx(Ctx), Current(nullptr) {}
 
 InterpState::~InterpState() {
   while (Current) {
     InterpFrame *Next = Current->Caller;
     delete Current;
     Current = Next;
   }
 

clang/test/AST/Interp/depth-limit.cpp

+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -fconstexpr-depth 100 -verify %s
+// RUN: %clang_cc1 -fconstexpr-depth 100 -verify=ref %s
+
+constexpr int f(int a) {
+  if (a == 100)
+    return 1 / 0; // expected-warning {{division by zero is undefined}} \
+                  // ref-warning {{division by zero is undefined}}
+
+  return f(a + 1); // ref-note {{exceeded maximum depth of 100 calls}} \
+                   // ref-note {{in call to 'f(99)'}} \
+                   // ref-note {{in call to 'f(98)'}} \
+                   // ref-note {{in call to 'f(97)'}} \
+                   // ref-note {{in call to 'f(96)'}} \
+                   // ref-note {{in call to 'f(95)'}} \
+                   // ref-note {{skipping 90 calls in backtrace}} \
+                   // ref-note {{in call to 'f(4)'}} \
+                   // ref-note {{in call to 'f(3)'}} \
+                   // ref-note {{in call to 'f(2)'}} \
+                   // ref-note {{in call to 'f(1)'}} \
+                   // expected-note {{exceeded maximum depth of 100 calls}} \
+                   // expected-note {{in call to 'f(99)'}} \
+                   // expected-note {{in call to 'f(98)'}} \
+                   // expected-note {{in call to 'f(97)'}} \
+                   // expected-note {{in call to 'f(96)'}} \
+                   // expected-note {{in call to 'f(95)'}} \
+                   // expected-note {{skipping 90 calls in backtrace}} \
+                   // expected-note {{in call to 'f(4)'}} \
+                   // expected-note {{in call to 'f(3)'}} \
+                   // expected-note {{in call to 'f(2)'}} \
+                   // expected-note {{in call to 'f(1)'}}
+}
+static_assert(f(0) == 100); // ref-error {{not an integral constant expression}} \
+                            // ref-note {{in call to 'f(0)'}} \
+                            // expected-error {{not an integral constant expression}} \
+                            // expected-note {{in call to 'f(0)'}}

clang/test/AST/Interp/depth-limit2.cpp

+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -fconstexpr-depth 2 -verify %s
+// RUN: %clang_cc1 -fconstexpr-depth 2 -verify=ref %s
+
+
+constexpr int func() {
+  return 12;
+}
+
+constexpr int foo() {
+  return func(); // expected-note {{exceeded maximum depth of 2 calls}} \
+                 // ref-note {{exceeded maximum depth of 2 calls}}
+}
+
+constexpr int bar() {
+  return foo(); // expected-note {{in call to 'foo()'}} \
+                // ref-note {{in call to 'foo()'}}
+}
+
+static_assert(bar() == 12); // expected-error {{not an integral constant expression}} \
+                            // expected-note {{in call to 'bar()'}} \
+                            // ref-error {{not an integral constant expression}} \
+                            // ref-note {{in call to 'bar()'}}
+