[clang][Interp] Support pointer arithmetic in binary operators

[shafik]

clang/lib/AST/Interp/ByteCodeExprGen.cpp

259

I am not sure if this is the right place to handle this but there are a bunch of other cases.

• nullptr can have 0 added or subtracted
• You can only do addition/subtraction from a pointer if the result in within bounds or one after the end
• You can subtract two pointers if they point to the same object.

godbolt: https://godbolt.org/z/5YTY93z8M

[tbaeder]

clang/lib/AST/Interp/ByteCodeExprGen.cpp

259

I will probably move this special case out of the function and into its own.
Thanks for the tests, I think this should all already work except for adding two pointers. I'll update the diff once I checked that out.

[tbaeder]

clang/lib/AST/Interp/Interp.h

1085

This is also not being diagnosed (only rejected) by the current interpreter. But would be nice to have an error message.

[tbaeder]

Ping

[shafik]

clang/lib/AST/Interp/ByteCodeExprGen.cpp

259

You will also want to cover this case as well: https://eel.is/c++draft/expr.add#6

265

or neither left or right operand is a pointer type

277

If it is two pointers then it must be a subtraction.

302

306

310

[tbaeder]

clang/lib/AST/Interp/ByteCodeExprGen.cpp

259

FWIW I've looked at the link but can hardly wrap my head around what the text is talking about, let alone make some contant expression out of it that doesn't run into some sort of other error :(

[shafik]

clang/lib/AST/Interp/ByteCodeExprGen.cpp

259

nvm, I just realized it requires a reinterpret_cast

[shafik]

clang/test/AST/Interp/arrays.cpp

69

We should also have a test for addition out of bounds but subsequent addition bringing it back in bounds. Still UB but we should verify it: https://godbolt.org/z/c1MWjGdfT

Apparently gcc does not catch this one.

[shafik]

clang/lib/AST/Interp/Interp.h

1085

The TODO is still present, will you tackle this as part of this PR or a follow-up?

[tbaeder]

clang/lib/AST/Interp/Interp.h

1085

A follow-up would be better I think.

[shafik]

LGTM

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 interp stack.
   bool VisitCastExpr(const CastExpr *E);
   bool VisitIntegerLiteral(const IntegerLiteral *E);
   bool VisitParenExpr(const ParenExpr *E);
   bool VisitBinaryOperator(const BinaryOperator *E);
+  bool VisitPointerArithBinOp(const BinaryOperator *E);
   bool VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E);
   bool VisitCallExpr(const CallExpr *E);
   bool VisitCXXMemberCallExpr(const CXXMemberCallExpr *E);
   bool VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *E);
   bool VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *E);
   bool VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *E);
   bool VisitCXXThisExpr(const CXXThisExpr *E);
   bool VisitUnaryOperator(const UnaryOperator *E);

clang/lib/AST/Interp/ByteCodeExprGen.cpp

case BO_Comma:
     return true;
   default:
     break;
   }
 
   // Typecheck the args.
   Optional<PrimType> LT = classify(LHS->getType());
   Optional<PrimType> RT = classify(RHS->getType());
-  if (!LT || !RT) {
+  Optional<PrimType> T = classify(BO->getType());
+  if (!LT || !RT || !T) {
     return this->bail(BO);
   }
 
-  if (Optional<PrimType> T = classify(BO->getType())) {
-    if (!visit(LHS))
-      return false;
-    if (!visit(RHS))
-      return false;
-
-    auto Discard = [this, T, BO](bool Result) {
-      if (!Result)
-        return false;
-      return DiscardResult ? this->emitPop(*T, BO) : true;
-    };
 
-    switch (BO->getOpcode()) {
-    case BO_EQ:
-      return Discard(this->emitEQ(*LT, BO));
-    case BO_NE:
-      return Discard(this->emitNE(*LT, BO));
-    case BO_LT:
-      return Discard(this->emitLT(*LT, BO));
-    case BO_LE:
-      return Discard(this->emitLE(*LT, BO));
-    case BO_GT:
-      return Discard(this->emitGT(*LT, BO));
-    case BO_GE:
-      return Discard(this->emitGE(*LT, BO));
-    case BO_Sub:
-      return Discard(this->emitSub(*T, BO));
-    case BO_Add:
-      return Discard(this->emitAdd(*T, BO));
-    case BO_Mul:
-      return Discard(this->emitMul(*T, BO));
-    case BO_Rem:
-      return Discard(this->emitRem(*T, BO));
-    case BO_Div:
-      return Discard(this->emitDiv(*T, BO));
-    case BO_Assign:
-      if (!this->emitStore(*T, BO))
-        return false;
-      return DiscardResult ? this->emitPopPtr(BO) : true;
-    case BO_And:
-      return Discard(this->emitBitAnd(*T, BO));
-    case BO_Or:
-      return Discard(this->emitBitOr(*T, BO));
-    case BO_Shl:
-      return Discard(this->emitShl(*LT, *RT, BO));
-    case BO_Shr:
-      return Discard(this->emitShr(*LT, *RT, BO));
-    case BO_Xor:
-      return Discard(this->emitBitXor(*T, BO));
-    case BO_LAnd:
-    case BO_LOr:
-    default:
-      return this->bail(BO);
-    }
-  }
+  // Pointer arithmetic special case.
+  if (BO->getOpcode() == BO_Add || BO->getOpcode() == BO_Sub) {
+    if (*T == PT_Ptr || (*LT == PT_Ptr && *RT == PT_Ptr))
+      return this->VisitPointerArithBinOp(BO);
+  }
+
+  if (!visit(LHS) || !visit(RHS))
+    return false;
+
+
+  llvm_unreachable("Unhandled binary op");
 
-  return this->bail(BO);
+/// Perform addition/subtraction of a pointer and an integer or
+/// subtraction of two pointers.
+template <class Emitter>
+bool ByteCodeExprGen<Emitter>::VisitPointerArithBinOp(const BinaryOperator *E) {
+  BinaryOperatorKind Op = E->getOpcode();
+  const Expr *LHS = E->getLHS();
+  const Expr *RHS = E->getRHS();
+
+  if ((Op != BO_Add && Op != BO_Sub) ||
+      (!LHS->getType()->isPointerType() && !RHS->getType()->isPointerType()))
+    return false;
+
+  Optional<PrimType> LT = classify(LHS);
+  Optional<PrimType> RT = classify(RHS);
+
+  if (!LT || !RT)
+    return false;
+
+  if (LHS->getType()->isPointerType() && RHS->getType()->isPointerType()) {
+    if (Op != BO_Sub)
+      return false;
+
+    assert(E->getType()->isIntegerType());
+    if (!visit(RHS) || !visit(LHS))
+      return false;
+
+    return this->emitSubPtr(classifyPrim(E->getType()), E);
+  }
+
+  PrimType OffsetType;
+  if (LHS->getType()->isIntegerType()) {
+    if (!visit(RHS) || !visit(LHS))
+      return false;
+    OffsetType = *LT;
+  } else if (RHS->getType()->isIntegerType()) {
+    if (!visit(LHS) || !visit(RHS))
+      return false;
+    OffsetType = *RT;
+  } else {
+    return false;
+  }
+
+  if (Op == BO_Add)
+    return this->emitAddOffset(OffsetType, E);
+  else if (Op == BO_Sub)
+    return this->emitSubOffset(OffsetType, E);
+
+  return this->bail(E);
 }
 
 template <class Emitter>
 bool ByteCodeExprGen<Emitter>::VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E) {
   if (Optional<PrimType> T = classify(E))
     return this->emitZero(*T, E);
 
   return false;
 }
 
 template <class Emitter>
 bool ByteCodeExprGen<Emitter>::VisitArraySubscriptExpr(

clang/lib/AST/Interp/Interp.h

inline bool CmpHelperEQ<Pointer>(InterpState &S, CodePtr OpPC, CompareFn Fn) {
   }
 
   if (!Pointer::hasSameBase(LHS, RHS)) {
     S.Stk.push<BoolT>(BoolT::from(Fn(ComparisonCategoryResult::Unordered)));
     return true;
   } else {
     unsigned VL = LHS.getByteOffset();
     unsigned VR = RHS.getByteOffset();
+
+    // In our Pointer class, a pointer to an array and a pointer to the first
+    // element in the same array are NOT equal. They have the same Base value,
+    // but a different Offset. This is a pretty rare case, so we fix this here
+    // by comparing pointers to the first elements.
+    if (LHS.inArray() && LHS.isRoot())
+      VL = LHS.atIndex(0).getByteOffset();
+    if (RHS.inArray() && RHS.isRoot())
+      VR = RHS.atIndex(0).getByteOffset();
+
     S.Stk.push<BoolT>(BoolT::from(Fn(Compare(VL, VR))));
     return true;
   }
 }
 
 template <PrimType Name, class T = typename PrimConv<Name>::T>
 bool EQ(InterpState &S, CodePtr OpPC) {
   return CmpHelperEQ<T>(S, OpPC, [](ComparisonCategoryResult R) {

 //===----------------------------------------------------------------------===//
 // AddOffset, SubOffset
 //===----------------------------------------------------------------------===//
 
 template <class T, bool Add> bool OffsetHelper(InterpState &S, CodePtr OpPC) {
   // Fetch the pointer and the offset.
   const T &Offset = S.Stk.pop<T>();
   const Pointer &Ptr = S.Stk.pop<Pointer>();
-  if (!CheckNull(S, OpPC, Ptr, CSK_ArrayIndex))
-    return false;
+
   if (!CheckRange(S, OpPC, Ptr, CSK_ArrayToPointer))
     return false;
 
-  // Get a version of the index comparable to the type.
-  T Index = T::from(Ptr.getIndex(), Offset.bitWidth());
-  // A zero offset does not change the pointer, but in the case of an array
-  // it has to be adjusted to point to the first element instead of the array.
+  // A zero offset does not change the pointer.
   if (Offset.isZero()) {
-    S.Stk.push<Pointer>(Index.isZero() ? Ptr.atIndex(0) : Ptr);
+    S.Stk.push<Pointer>(Ptr);
     return true;
   }
+
+  if (!CheckNull(S, OpPC, Ptr, CSK_ArrayIndex))
+    return false;
+
   // Arrays of unknown bounds cannot have pointers into them.
   if (!CheckArray(S, OpPC, Ptr))
     return false;
 
+  // Get a version of the index comparable to the type.
+  T Index = T::from(Ptr.getIndex(), Offset.bitWidth());
   // Compute the largest index into the array.
   unsigned MaxIndex = Ptr.getNumElems();
 
   // Helper to report an invalid offset, computed as APSInt.
   auto InvalidOffset = [&]() {
     const unsigned Bits = Offset.bitWidth();
     APSInt APOffset(Offset.toAPSInt().extend(Bits + 2), false);
     APSInt APIndex(Index.toAPSInt().extend(Bits + 2), false);
bool AddOffset(InterpState &S, CodePtr OpPC) {
   return OffsetHelper<T, true>(S, OpPC);
 }
 
 template <PrimType Name, class T = typename PrimConv<Name>::T>
 bool SubOffset(InterpState &S, CodePtr OpPC) {
   return OffsetHelper<T, false>(S, OpPC);
 }
 
+/// 1) Pops a Pointer from the stack.
+/// 2) Pops another Pointer from the stack.
+/// 3) Pushes the different of the indices of the two pointers on the stack.
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+inline bool SubPtr(InterpState &S, CodePtr OpPC) {
+  const Pointer &LHS = S.Stk.pop<Pointer>();
+  const Pointer &RHS = S.Stk.pop<Pointer>();
+
+  if (!Pointer::hasSameArray(LHS, RHS)) {
+    // TODO: Diagnose.
+    return false;
+  }
+
+  T A = T::from(LHS.getIndex());
+  T B = T::from(RHS.getIndex());
+  return AddSubMulHelper<T, T::sub, std::minus>(S, OpPC, A.bitWidth(), A, B);
+}
 
 //===----------------------------------------------------------------------===//
 // Destroy
 //===----------------------------------------------------------------------===//
 
 inline bool Destroy(InterpState &S, CodePtr OpPC, uint32_t I) {
   S.Current->destroy(I);
   return true;

clang/lib/AST/Interp/Opcodes.td

 // Pointer arithmetic.
 //===----------------------------------------------------------------------===//
 
 // [Pointer, Integral] -> [Pointer]
 def AddOffset : AluOpcode;
 // [Pointer, Integral] -> [Pointer]
 def SubOffset : AluOpcode;
 
+// Pointer, Pointer] - [Integral]
+def SubPtr : Opcode {
+  let Types = [IntegerTypeClass];
+  let HasGroup = 1;
+}
+
 //===----------------------------------------------------------------------===//
 // Binary operators.
 //===----------------------------------------------------------------------===//
 
 // [Real, Real] -> [Real]
 def Sub : AluOpcode;
 def Add : AluOpcode;
 def Mul : AluOpcode;

clang/lib/AST/Interp/Pointer.cpp

void Pointer::deactivate() const {
   // TODO: this only appears in constructors, so nothing to deactivate.
 }
 
 bool Pointer::hasSameBase(const Pointer &A, const Pointer &B) {
   return A.Pointee == B.Pointee;
 }
 
 bool Pointer::hasSameArray(const Pointer &A, const Pointer &B) {
-  return A.Base == B.Base && A.getFieldDesc()->IsArray;
+  return hasSameBase(A, B) && A.Base == B.Base && A.getFieldDesc()->IsArray;
 }

clang/test/AST/Interp/arrays.cpp

 
 constexpr int getElement(int i) {
   int values[] = {1, 4, 9, 16, 25, 36};
   return values[i];
 }
 static_assert(getElement(1) == 4, "");
 static_assert(getElement(5) == 36, "");
 
+constexpr int data[] = {5, 4, 3, 2, 1};
+constexpr int getElement(const int *Arr, int index) {
+  return *(Arr + index);
+}
+
+static_assert(getElement(data, 1) == 4, "");
+static_assert(getElement(data, 4) == 1, "");
+
+constexpr int getElementFromEnd(const int *Arr, int size, int index) {
+  return *(Arr + size - index - 1);
+}
+static_assert(getElementFromEnd(data, 5, 0) == 1, "");
+static_assert(getElementFromEnd(data, 5, 4) == 5, "");
+
+
+constexpr static int arr[2] = {1,2};
+constexpr static int arr2[2] = {3,4};
+constexpr int *p1 = nullptr;
+constexpr int *p2 = p1 + 1; // expected-error {{must be initialized by a constant expression}} \
+                            // expected-note {{cannot perform pointer arithmetic on null pointer}} \
+                            // ref-error {{must be initialized by a constant expression}} \
+                            // ref-note {{cannot perform pointer arithmetic on null pointer}}
+constexpr int *p3 = p1 + 0;
+constexpr int *p4 = p1 - 0;
+constexpr int *p5 =  0 + p1;
+constexpr int *p6 =  0 - p1; // expected-error {{invalid operands to binary expression}} \
+                             // ref-error {{invalid operands to binary expression}}
+
+constexpr int const * ap1 = &arr[0];
+constexpr int const * ap2 = ap1 + 3; // expected-error {{must be initialized by a constant expression}} \
+                                     // expected-note {{cannot refer to element 3 of array of 2}} \
+                                     // ref-error {{must be initialized by a constant expression}} \
+                                     // ref-note {{cannot refer to element 3 of array of 2}}
+
+constexpr auto ap3 = arr - 1; // expected-error {{must be initialized by a constant expression}} \
+                              // expected-note {{cannot refer to element -1}} \
+                              // ref-error {{must be initialized by a constant expression}} \
+                              // ref-note {{cannot refer to element -1}}
+constexpr int k1 = &arr[1] - &arr[0];
+static_assert(k1 == 1, "");
+static_assert((&arr[0] - &arr[1]) == -1, "");
+
+constexpr int k2 = &arr2[1] - &arr[0]; // expected-error {{must be initialized by a constant expression}} \
+                                       // ref-error {{must be initialized by a constant expression}}
+
+static_assert((arr + 0) == arr, "");
+static_assert(&arr[0] == arr, "");
+static_assert(*(&arr[0]) == 1, "");
+static_assert(*(&arr[1]) == 2, "");
+
+constexpr const int *OOB = (arr + 3) - 3; // expected-error {{must be initialized by a constant expression}} \
+                                          // expected-note {{cannot refer to element 3 of array of 2}} \
+                                          // ref-error {{must be initialized by a constant expression}} \
+                                          // ref-note {{cannot refer to element 3 of array of 2}}
 
 template<typename T>
 constexpr T getElementOf(T* array, int i) {
   return array[i];
 }
 static_assert(getElementOf(foo[0], 1) == &m, "");
 
 
 template <typename T, int N>
 constexpr T& getElementOfArray(T (&array)[N], int I) {
   return array[I];
 }
 static_assert(getElementOfArray(foo[2], 3) == &m, "");
 
 
-constexpr int data[] = {5, 4, 3, 2, 1};
 static_assert(data[0] == 4, ""); // expected-error{{failed}} \
                                  // expected-note{{5 == 4}} \
                                  // ref-error{{failed}} \
                                  // ref-note{{5 == 4}}
 
 
 constexpr int dynamic[] = {
   f, 3, 2 + 5, data[3], *getElementOf(foo[2], 3)