[clang][Interp] WIP: Array fillers

[tbaeder]

Summary

Uploading this now to get some early feedback on the approach and maybe find some better tests.

Pointers in the VM are implemented through the Pointer class. Each Pointer points to a Block, which represent memory. However, each Block also knows all the Pointers pointing at it. I've used this to find simply replace a Block representing an array with a larger one and update all pointers pointing to said block (Block::transferPointers()). This is the core of it all, but it requires quite a few smaller changes that could be broken out of this patch of course. Like enabling pointer tracking for static Blocks.

[tbaeder]

clang/lib/AST/Interp/Context.cpp

54

The additional asserts I inserted here could be in another patch. However, I added them because I ran into a peculiar problem: when creating a Pointer, it calls Pointee->addPointer(this). It will only remove itself from the pointee again in its destructor. But the destructor is not (necessarily) being called at all because the Pointer is constructed in the stack (or otherwise placement-new'ed into a larger memory region).

clang/lib/AST/Interp/Interp.h

831

Note here that both the block and the descriptor are leaked. They are usually allocated in Program, which uses its own allocator for them. I'm not 100% sure what to do about this, since the blocks have different lifetimes depending on if they are for global or local variables (or parameters).
Short of introducing a Program::managesBlock(Block* B) that just does a linear search for the blocks.

[shafik]

clang/lib/AST/Interp/Descriptor.h

83

How about NumElemsWithFiller?

clang/lib/AST/Interp/Pointer.h

252

You say greater here but you use < below in the assert instead of <=

clang/lib/AST/Interp/Boolean.h

public:
   bool operator<(Boolean RHS) const { return V < RHS.V; }
   bool operator>(Boolean RHS) const { return V > RHS.V; }
   bool operator<=(Boolean RHS) const { return V <= RHS.V; }
   bool operator>=(Boolean RHS) const { return V >= RHS.V; }
   bool operator==(Boolean RHS) const { return V == RHS.V; }
   bool operator!=(Boolean RHS) const { return V != RHS.V; }
 
   bool operator>(unsigned RHS) const { return static_cast<unsigned>(V) > RHS; }
+  bool operator>=(unsigned RHS) const { return static_cast<unsigned>(V) >= RHS; }
 
   Boolean operator-() const { return Boolean(V); }
   Boolean operator~() const { return Boolean(true); }
 
   explicit operator unsigned() const { return V; }
   explicit operator int64_t() const { return V; }
   explicit operator uint64_t() const { return V; }
   explicit operator int() const { return V; }

clang/lib/AST/Interp/ByteCodeExprGen.cpp

 }
 
 // NB: When calling this function, we have a pointer to the
 //   array-to-initialize on the stack.
 template <class Emitter>
 bool ByteCodeExprGen<Emitter>::visitArrayInitializer(const Expr *Initializer) {
   assert(Initializer->getType()->isArrayType());
 
-  // TODO: Fillers?
   if (const auto *InitList = dyn_cast<InitListExpr>(Initializer)) {
     unsigned ElementIndex = 0;
     for (const Expr *Init : InitList->inits()) {
       QualType InitType = Init->getType();
 
       if (InitType->isArrayType()) {
         // Advance the pointer currently on the stack to the given
         // dimension and narrow().

clang/lib/AST/Interp/Context.cpp

 using namespace clang;
 using namespace clang::interp;
 
 Context::Context(ASTContext &Ctx) : Ctx(Ctx), P(new Program(*this)) {}
 
 Context::~Context() {}
 
 bool Context::isPotentialConstantExpr(State &Parent, const FunctionDecl *FD) {
+  assert(Stk.empty());
   Function *Func = P->getFunction(FD);
   if (!Func) {
     if (auto R = ByteCodeStmtGen<ByteCodeEmitter>(*this, *P).compileFunc(FD)) {
       Func = *R;
     } else {
       handleAllErrors(R.takeError(), [&Parent](ByteCodeGenError &Err) {
         Parent.FFDiag(Err.getLoc(), diag::err_experimental_clang_interp_failed);
       });
       return false;
     }
   }
 
+  Stk.clear();
+
   if (!Func->isConstexpr())
     return false;
 
-  APValue Dummy;
-  return Run(Parent, Func, Dummy);
+  // XXX We *actually* just ONLY want to assert that the stack is empty.
+  //   (Without the clear() above).
+  //   However, currently we emit some unnecessary Destroy() and RetVoid
+  //   ops. Long-term, we should get rid of those. But short-term, they
+  //   cause no harm.
+  assert(Stk.empty());
+  return true;
 }
 
 bool Context::evaluateAsRValue(State &Parent, const Expr *E, APValue &Result) {
+  assert(Stk.empty());
   ByteCodeExprGen<EvalEmitter> C(*this, *P, Parent, Stk, Result);
-  return Check(Parent, C.interpretExpr(E));
+
+  if (Check(Parent, C.interpretExpr(E))) {
+    assert(Stk.empty());
+    return true;
+  }
+
+  Stk.clear();
+  return false;
 }
 
 bool Context::evaluateAsInitializer(State &Parent, const VarDecl *VD,
                                     APValue &Result) {
+  assert(Stk.empty());
   ByteCodeExprGen<EvalEmitter> C(*this, *P, Parent, Stk, Result);
-  return Check(Parent, C.interpretDecl(VD));
+
+  if (Check(Parent, C.interpretDecl(VD))) {
+    assert(Stk.empty());
+    return true;
+  }
+
+  Stk.clear();
+  return false;
 }
 
 const LangOptions &Context::getLangOpts() const { return Ctx.getLangOpts(); }
 
 llvm::Optional<PrimType> Context::classify(QualType T) const {
   if (T->isReferenceType() || T->isPointerType()) {
     return PT_Ptr;
   }

clang/lib/AST/Interp/Descriptor.h

public:
   /// Flag indicating if the block is mutable.
   const bool IsConst = false;
   /// Flag indicating if a field is mutable.
   const bool IsMutable = false;
   /// Flag indicating if the block is a temporary.
   const bool IsTemporary = false;
   /// Flag indicating if the block is an array.
   const bool IsArray = false;
+  /// NB: Might be different than (Size / ElemSize), for arrays
+  ///   that have an array filler.
+  const InterpSize NumFullElems = 0;
+  const Expr *ArrayFiller = nullptr;
 
   /// Storage management methods.
   const BlockCtorFn CtorFn = nullptr;
   const BlockDtorFn DtorFn = nullptr;
   const BlockMoveFn MoveFn = nullptr;
 
   /// Allocates a descriptor for a primitive.
   Descriptor(const DeclTy &D, PrimType Type, bool IsConst, bool IsTemporary,
              bool IsMutable);
 
   /// Allocates a descriptor for an array of primitives.
-  Descriptor(const DeclTy &D, PrimType Type, size_t NumElems, bool IsConst,
+  Descriptor(const DeclTy &D, PrimType Type, size_t NumElems,
+             const Expr *Filler, size_t FullElems, bool IsConst,
              bool IsTemporary, bool IsMutable);
 
   /// Allocates a descriptor for an array of primitives of unknown size.
   Descriptor(const DeclTy &D, PrimType Type, bool IsTemporary, UnknownSize);
 
   /// Allocates a descriptor for an array of composites.
   Descriptor(const DeclTy &D, Descriptor *Elem, unsigned NumElems, bool IsConst,
              bool IsTemporary, bool IsMutable);
 
   /// Allocates a descriptor for an array of composites of unknown size.
   Descriptor(const DeclTy &D, Descriptor *Elem, bool IsTemporary, UnknownSize);
 
   /// Allocates a descriptor for a record.
   Descriptor(const DeclTy &D, Record *R, bool IsConst, bool IsTemporary,
              bool IsMutable);
 
   QualType getType() const;
   SourceLocation getLocation() const;
 
   const Decl *asDecl() const { return Source.dyn_cast<const Decl *>(); }
   const Expr *asExpr() const { return Source.dyn_cast<const Expr *>(); }
+  const Expr *getArrayFiller() const { return ArrayFiller; }
 
   const ValueDecl *asValueDecl() const {
     return dyn_cast_or_null<ValueDecl>(asDecl());
   }
 
   const FieldDecl *asFieldDecl() const {
     return dyn_cast_or_null<FieldDecl>(asDecl());
   }
public:
   unsigned getAllocSize() const { return AllocSize; }
   /// returns the size of an element when the structure is viewed as an array.
   unsigned getElemSize()  const { return ElemSize; }
 
   /// Returns the number of elements stored in the block.
   unsigned getNumElems() const {
     return Size == UnknownSizeMark ? 0 : (getSize() / getElemSize());
   }
+  /// Returns the maximum number the block may hold.
+  unsigned getNumFullElems() const {
+    return Size == UnknownSizeMark ? 0 : NumFullElems;
+  }
 
   /// Checks if the descriptor is of an array of primitives.
   bool isPrimitiveArray() const { return IsArray && !ElemDesc; }
   /// Checks if the descriptor is of an array of zero size.
   bool isZeroSizeArray() const { return Size == 0; }
   /// Checks if the descriptor is of an array of unknown size.
   bool isUnknownSizeArray() const { return Size == UnknownSizeMark; }
 

clang/lib/AST/Interp/Descriptor.cpp

Descriptor::Descriptor(const DeclTy &D, PrimType Type, bool IsConst,
                        bool IsTemporary, bool IsMutable)
     : Source(D), ElemSize(primSize(Type)), Size(ElemSize), AllocSize(Size),
       IsConst(IsConst), IsMutable(IsMutable), IsTemporary(IsTemporary),
       CtorFn(getCtorPrim(Type)), DtorFn(getDtorPrim(Type)),
       MoveFn(getMovePrim(Type)) {
   assert(Source && "Missing source");
 }
 
+/// XXX Just make a new constructor that takes 2 sizes as well as an array
+/// filler expression.
 Descriptor::Descriptor(const DeclTy &D, PrimType Type, size_t NumElems,
-                       bool IsConst, bool IsTemporary, bool IsMutable)
+                       const Expr *Filler, size_t FullElems, bool IsConst,
+                       bool IsTemporary, bool IsMutable)
     : Source(D), ElemSize(primSize(Type)), Size(ElemSize * NumElems),
       AllocSize(align(Size) + sizeof(InitMap *)), IsConst(IsConst),
       IsMutable(IsMutable), IsTemporary(IsTemporary), IsArray(true),
+      NumFullElems(FullElems), ArrayFiller(Filler),
       CtorFn(getCtorArrayPrim(Type)), DtorFn(getDtorArrayPrim(Type)),
       MoveFn(getMoveArrayPrim(Type)) {
   assert(Source && "Missing source");
+  assert(NumElems <= FullElems);
 }
 
 Descriptor::Descriptor(const DeclTy &D, PrimType Type, bool IsTemporary,
                        UnknownSize)
     : Source(D), ElemSize(primSize(Type)), Size(UnknownSizeMark),
       AllocSize(alignof(void *)), IsConst(true), IsMutable(false),
       IsTemporary(IsTemporary), IsArray(true), CtorFn(getCtorArrayPrim(Type)),
       DtorFn(getDtorArrayPrim(Type)), MoveFn(getMoveArrayPrim(Type)) {
   assert(Source && "Missing source");
 }
 
 Descriptor::Descriptor(const DeclTy &D, Descriptor *Elem, unsigned NumElems,
                        bool IsConst, bool IsTemporary, bool IsMutable)
     : Source(D), ElemSize(Elem->getAllocSize() + sizeof(InlineDescriptor)),
       Size(ElemSize * NumElems),
       AllocSize(std::max<size_t>(alignof(void *), Size)), ElemDesc(Elem),
       IsConst(IsConst), IsMutable(IsMutable), IsTemporary(IsTemporary),
-      IsArray(true), CtorFn(ctorArrayDesc), DtorFn(dtorArrayDesc),
-      MoveFn(moveArrayDesc) {
+      IsArray(true), NumFullElems(NumElems), CtorFn(ctorArrayDesc),
+      DtorFn(dtorArrayDesc), MoveFn(moveArrayDesc) {
   assert(Source && "Missing source");
 }
 
 Descriptor::Descriptor(const DeclTy &D, Descriptor *Elem, bool IsTemporary,
                        UnknownSize)
     : Source(D), ElemSize(Elem->getAllocSize() + sizeof(InlineDescriptor)),
       Size(UnknownSizeMark), AllocSize(alignof(void *)), ElemDesc(Elem),
       IsConst(true), IsMutable(false), IsTemporary(IsTemporary), IsArray(true),

clang/lib/AST/Interp/EvalEmitter.cpp

if (auto *RT = Ty->getAs<RecordType>()) {
           const Record::Base *VD = Record->getVirtualBase(I);
           QualType VirtBaseTy = Ctx.getASTContext().getRecordType(VD->Decl);
           const Pointer &VP = Ptr.atField(VD->Offset);
           Ok &= Composite(VirtBaseTy, VP, R.getStructBase(NB + I));
         }
       }
       return Ok;
     }
-    if (auto *AT = Ty->getAsArrayTypeUnsafe()) {
-      const size_t NumElems = Ptr.getNumElems();
+    if (const auto *AT = Ty->getAsArrayTypeUnsafe()) {
+      size_t NumElems = Ptr.getNumElems();
+      const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT);
+      const size_t FullElems = CAT->getSize().getZExtValue();
+
       QualType ElemTy = AT->getElementType();
-      R = APValue(APValue::UninitArray{}, NumElems, NumElems);
+      R = APValue(APValue::UninitArray{}, NumElems, FullElems);
 
       bool Ok = true;
       for (unsigned I = 0; I < NumElems; ++I) {
         APValue &Slot = R.getArrayInitializedElt(I);
         const Pointer &EP = Ptr.atIndex(I);
         if (llvm::Optional<PrimType> T = Ctx.classify(ElemTy)) {
           TYPE_SWITCH(*T, Ok &= ReturnValue<T>(EP.deref<T>(), Slot));
         } else {
           Ok &= Composite(ElemTy, EP.narrow(), Slot);
         }
       }
+
+      if (NumElems != FullElems) {
+        // Need to convert the array filler to a APValue
+        const Expr *AF = Ptr.getArrayFiller();
+        assert(AF);
+
+        // TODO: I have no idea if the potentially nested call
+        //  to evaluateAsRValue() here is always going to work.
+        //
+        //  We should evaluate the array filler *once* during
+        //  normal evaluation, not when returning the value.
+        APValue FillerValue;
+        Ctx.evaluateAsRValue(S, AF, FillerValue);
+        FillerValue.dump();
+        R.getArrayFiller() = FillerValue;
+      }
       return Ok;
     }
     llvm_unreachable("invalid value to return");
   };
 
   // Return the composite type.
   const auto &Ptr = S.Stk.pop<Pointer>();
   return Composite(Ptr.getType(), Ptr, Result);

clang/lib/AST/Interp/Integral.h

public:
   bool operator<=(Integral RHS) const { return V <= RHS.V; }
   bool operator>=(Integral RHS) const { return V >= RHS.V; }
   bool operator==(Integral RHS) const { return V == RHS.V; }
   bool operator!=(Integral RHS) const { return V != RHS.V; }
 
   bool operator>(unsigned RHS) const {
     return V >= 0 && static_cast<unsigned>(V) > RHS;
   }
+  bool operator>=(unsigned RHS) const {
+    return V >= 0 && static_cast<unsigned>(V) >= RHS;
+  }
 
   Integral operator-() const { return Integral(-V); }
   Integral operator~() const { return Integral(~V); }
 
   template <unsigned DstBits, bool DstSign>
   explicit operator Integral<DstBits, DstSign>() const {
     return Integral<DstBits, DstSign>(V);
   }

clang/lib/AST/Interp/Interp.h

if (Offset.isZero()) {
     S.Stk.push<Pointer>(Index.isZero() ? Ptr.atIndex(0) : Ptr);
     return true;
   }
   // Arrays of unknown bounds cannot have pointers into them.
   if (!CheckArray(S, OpPC, Ptr))
     return false;
 
   // Compute the largest index into the array.
-  unsigned MaxIndex = Ptr.getNumElems();
+  unsigned MaxIndex = Ptr.getNumFullElems();
 
   // 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);
     APSInt NewIndex = Add ? (APIndex + APOffset) : (APIndex - APOffset);
     S.CCEDiag(S.Current->getSource(OpPC), diag::note_constexpr_array_index)
         << NewIndex
         << /*array*/ static_cast<int>(!Ptr.inArray())
         << static_cast<unsigned>(MaxIndex);
     return false;
   };
 
   unsigned MaxOffset = MaxIndex - Ptr.getIndex();
   if constexpr (Add) {
     // If the new offset would be negative, bail out.
     if (Offset.isNegative() && (Offset.isMin() || -Offset > Index))
       return InvalidOffset();
 
     // If the new offset would be out of bounds, bail out.
-    if (Offset.isPositive() && Offset > MaxOffset)
+    if (Offset.isPositive() && Offset >= MaxOffset)
       return InvalidOffset();
   } else {
     // If the new offset would be negative, bail out.
     if (Offset.isPositive() && Index < Offset)
       return InvalidOffset();
 
     // If the new offset would be out of bounds, bail out.
     if (Offset.isNegative() && (Offset.isMin() || -Offset > MaxOffset))
       return InvalidOffset();
   }
 
   // Offset is valid - compute it on unsigned.
   int64_t WideIndex = static_cast<int64_t>(Index);
   int64_t WideOffset = static_cast<int64_t>(Offset);
   int64_t Result = Add ? (WideIndex + WideOffset) : (WideIndex - WideOffset);
-  S.Stk.push<Pointer>(Ptr.atIndex(static_cast<unsigned>(Result)));
+  unsigned UResult = static_cast<unsigned>(Result);
+
+  // For arrays, we might need to expand them using the filler element.
+  if (Ptr.needsExpansionForIndex(UResult)) {
+    Block *Pointee = Ptr.block();
+    const Descriptor *Desc = Ptr.getFieldDesc();
+    unsigned OldNumElems = Desc->getNumElems();
+    unsigned NewNumElems = std::min(UResult * 2, Desc->getNumFullElems());
+    assert(NewNumElems > OldNumElems);
+
+    // TODO: Just create a different Descriptor constructor for this case
+    Descriptor *D = new Descriptor(
+        Desc->asDecl(), static_cast<PrimType>(4), // PT_Sint32,
+        NewNumElems, Desc->getArrayFiller(), Desc->getNumFullElems(),
+        Desc->IsConst, Desc->IsTemporary, Desc->IsMutable);
+    char *m = (char *)malloc(sizeof(Block) + D->getAllocSize());
+    Block *_B = new (m) Block(D, Pointee->isStatic(), Pointee->isExtern());
+    _B->invokeCtor();
+
+    memcpy(_B->data(), Pointee->data(), Desc->getAllocSize());
+
+    Pointee->transferPointersTo(_B);
+    assert(Ptr.block() == _B);
+    assert(Ptr.block()->hasPointer(&Ptr));
+    // TODO:  Actually use the array filler for the new elements!
+  }
+
+  S.Stk.push<Pointer>(Ptr.atIndex(UResult));
   return true;
 }
 
 template <PrimType Name, class T = typename PrimConv<Name>::T>
 bool AddOffset(InterpState &S, CodePtr OpPC) {
   return OffsetHelper<T, true>(S, OpPC);
 }
 

clang/lib/AST/Interp/InterpBlock.h

public:
   bool isTemporary() const { return Desc->IsTemporary; }
   /// Returns the size of the block.
   InterpSize getSize() const { return Desc->getAllocSize(); }
   /// Returns the declaration ID.
   llvm::Optional<unsigned> getDeclID() const { return DeclID; }
 
   /// Returns a pointer to the stored data.
   char *data() { return reinterpret_cast<char *>(this + 1); }
+  const char *data() const { return reinterpret_cast<const char *>(this + 1); }
 
   /// Returns a view over the data.
   template <typename T>
   T &deref() { return *reinterpret_cast<T *>(data()); }
 
   /// Invokes the constructor.
   void invokeCtor() {
     std::memset(data(), 0, getSize());
     if (Desc->CtorFn)
       Desc->CtorFn(this, data(), Desc->IsConst, Desc->IsMutable,
                    /*isActive=*/true, Desc);
   }
 
+  /// Checks if \P is in the list of pointers this block manages.
+  /// This does NOT check if P->Pointee is this block.
+  ///
+  /// Only use this function in assertions.
+  bool hasPointer(const Pointer *P) const;
+
+  /// Transfer all pointers pointing to this block to \t To.
+  /// After calling this function, this->hasPointers() will
+  /// return false.
+  void transferPointersTo(Block *To);
+
 protected:
   friend class Pointer;
   friend class DeadBlock;
   friend class InterpState;
 
   Block(Descriptor *Desc, bool IsExtern, bool IsStatic, bool IsDead)
     : IsStatic(IsStatic), IsExtern(IsExtern), IsDead(true), Desc(Desc) {}
 
   // Deletes a dead block at the end of its lifetime.
   void cleanup();
 
   // Pointer chain management.
   void addPointer(Pointer *P);
   void removePointer(Pointer *P);
-  void movePointer(Pointer *From, Pointer *To);
 
   /// Start of the chain of pointers.
   Pointer *Pointers = nullptr;
   /// Unique identifier of the declaration.
   llvm::Optional<unsigned> DeclID;
   /// Flag indicating if the block has static storage duration.
   bool IsStatic = false;
   /// Flag indicating if the block is an extern.

clang/lib/AST/Interp/InterpBlock.cpp

 //===----------------------------------------------------------------------===//
 
 #include "InterpBlock.h"
 #include "Pointer.h"
 
 using namespace clang;
 using namespace clang::interp;
 
-
-
 void Block::addPointer(Pointer *P) {
-  if (IsStatic)
-    return;
+  assert(Pointers != P);
+  assert(P);
+  assert(!hasPointer(P));
+
   if (Pointers)
     Pointers->Prev = P;
   P->Next = Pointers;
   P->Prev = nullptr;
   Pointers = P;
 }
 
 void Block::removePointer(Pointer *P) {
-  if (IsStatic)
-    return;
+  assert(P);
+
   if (Pointers == P)
     Pointers = P->Next;
   if (P->Prev)
     P->Prev->Next = P->Next;
   if (P->Next)
     P->Next->Prev = P->Prev;
+  // Setting P->Pointee to null sounds like a good idea but
+  // it seems like some things (e.g. the Pointee->cleanup() call
+  // in ~Pointer()) rely on this not happening.
 }
 
 void Block::cleanup() {
   if (Pointers == nullptr && IsDead)
     (reinterpret_cast<DeadBlock *>(this + 1) - 1)->free();
 }
 
-void Block::movePointer(Pointer *From, Pointer *To) {
-  if (IsStatic)
+void Block::transferPointersTo(Block *To) {
+  assert(To);
+  if (!Pointers)
     return;
-  To->Prev = From->Prev;
-  if (To->Prev)
-    To->Prev->Next = To;
-  To->Next = From->Next;
-  if (To->Next)
-    To->Next->Prev = To;
-  if (Pointers == From)
-    Pointers = To;
 
-  From->Prev = nullptr;
-  From->Next = nullptr;
+  Pointer *P = this->Pointers;
+  while (P) {
+    Pointer *Next = P->Next;
+    removePointer(P);
+    To->addPointer(P);
+    P->Pointee = To;
+
+    P = Next;
+  }
+  assert(!hasPointers());
+}
+
+bool Block::hasPointer(const Pointer *P) const {
+  const Pointer *Iter = this->Pointers;
+  while (Iter) {
+    if (Iter == P)
+      return true;
+
+    assert(Iter != P);
+    assert(Iter != Iter->Next);
+    Iter = Iter->Next;
+  }
+
+  return false;
 }
 
 DeadBlock::DeadBlock(DeadBlock *&Root, Block *Blk)
     : Root(Root), B(Blk->Desc, Blk->IsStatic, Blk->IsExtern, /*isDead=*/true) {
   // Add the block to the chain of dead blocks.
   if (Root)
     Root->Prev = this;
 

clang/lib/AST/Interp/InterpFrame.h

private:
   /// Return address.
   CodePtr RetPC;
   /// The size of all the arguments.
   const unsigned ArgSize;
   /// Pointer to the arguments in the callee's frame.
   char *Args = nullptr;
   /// Fixed, initial storage for known local variables.
   std::unique_ptr<char[]> Locals;
+  /// Pointers we lazily create for the locals.
+  llvm::DenseMap<unsigned, Pointer> LocalPointers;
   /// Offset on the stack at entry.
   const size_t FrameOffset;
   /// Mapping from arg offsets to their argument blocks.
   llvm::DenseMap<unsigned, std::unique_ptr<char[]>> Params;
 };
 
 } // namespace interp
 } // namespace clang
 
 #endif

clang/lib/AST/Interp/InterpFrame.cpp

 }
 
 const FunctionDecl *InterpFrame::getCallee() const {
   return Func->getDecl();
 }
 
 Pointer InterpFrame::getLocalPointer(unsigned Offset) {
   assert(Offset < Func->getFrameSize() && "Invalid local offset.");
-  return Pointer(
-      reinterpret_cast<Block *>(Locals.get() + Offset - sizeof(Block)));
+  if (auto It = LocalPointers.find(Offset); It != LocalPointers.end())
+    return Pointer(It->second);
+
+  auto *B = reinterpret_cast<Block *>(Locals.get() + Offset - sizeof(Block));
+  Pointer &P = LocalPointers[Offset];
+  P = Pointer(B);
+  return P;
 }
 
 Pointer InterpFrame::getParamPointer(unsigned Off) {
   // Return the block if it was created previously.
   auto Pt = Params.find(Off);
   if (Pt != Params.end()) {
     return Pointer(reinterpret_cast<Block *>(Pt->second.get()));
   }

clang/lib/AST/Interp/InterpStack.h

public:
   void *top() { return Chunk ? peek(0) : nullptr; }
 
   /// Returns the size of the stack in bytes.
   size_t size() const { return StackSize; }
 
   /// Clears the stack without calling any destructors.
   void clear();
 
+  /// Returns true if the stack is empty.
+  bool empty() const { return size() == 0; }
+
 private:
   /// All stack slots are aligned to the native pointer alignment for storage.
   /// The size of an object is rounded up to a pointer alignment multiple.
   template <typename T> constexpr size_t aligned_size() const {
     constexpr size_t PtrAlign = alignof(void *);
     return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign;
   }
 

clang/lib/AST/Interp/Pointer.h

public:
 
   /// Converts the pointer to an APValue.
   APValue toAPValue() const;
 
   /// Offsets a pointer inside an array.
   Pointer atIndex(unsigned Idx) const {
     if (Base == RootPtrMark)
       return Pointer(Pointee, RootPtrMark, getDeclDesc()->getSize());
+
     unsigned Off = Idx * elemSize();
     if (getFieldDesc()->ElemDesc)
       Off += sizeof(InlineDescriptor);
     else
       Off += sizeof(InitMap *);
     return Pointer(Pointee, Base, Base + Off);
   }
 
bool isUnknownSizeArray() const {
     return getFieldDesc()->isUnknownSizeArray();
   }
   /// Checks if the pointer points to an array.
   bool isArrayElement() const { return Base != Offset; }
   /// Pointer points directly to a block.
   bool isRoot() const {
     return (Base == 0 || Base == RootPtrMark) && Offset == 0;
   }
+  /// Returns the Block this pointer points to.
+  Block *block() const { return Pointee; }
 
   /// Returns the record descriptor of a class.
   Record *getRecord() const { return getFieldDesc()->ElemRecord; }
   /// Returns the field information.
   const FieldDecl *getField() const { return getFieldDesc()->asFieldDecl(); }
 
   /// Checks if the object is a union.
   bool isUnion() const;
public:
   bool isMutable() const { return Base != 0 && getInlineDesc()->IsMutable; }
   /// Checks if an object was initialized.
   bool isInitialized() const;
   /// Checks if the object is active.
   bool isActive() const { return Base == 0 || getInlineDesc()->IsActive; }
   /// Checks if a structure is a base class.
   bool isBaseClass() const { return isField() && getInlineDesc()->IsBase; }
 
+  const Expr *getArrayFiller() const {
+    return getFieldDesc()->getArrayFiller();
+  }
+
+  bool needsExpansionForIndex(unsigned Idx) const {
+    const Descriptor *Desc = getFieldDesc();
+    // The given index should never be greater than NumFullElems,
+    // this needs to be checked earlier.
+    assert(Idx < Desc->getNumFullElems());
+    return Desc->isArray() &&
+      Idx >= Desc->getNumElems();
+  }
+
   /// Checks if an object or a subfield is mutable.
   bool isConst() const {
     return Base == 0 ? getDeclDesc()->IsConst : getInlineDesc()->IsConst;
   }
 
   /// Returns the declaration ID.
   llvm::Optional<unsigned> getDeclID() const { return Pointee->getDeclID(); }
 
   /// Returns the byte offset from the start.
   unsigned getByteOffset() const {
     return Offset;
   }
 
   /// Returns the number of elements.
   unsigned getNumElems() const { return getSize() / elemSize(); }
 
+  /// Returns the maximum number of elements.
+  unsigned getNumFullElems() const { return getFieldDesc()->getNumFullElems(); }
+
   /// Returns the index into an array.
   int64_t getIndex() const {
     if (isElementPastEnd())
       return 1;
     if (auto ElemSize = elemSize())
       return getOffset() / ElemSize;
     return 0;
   }

clang/lib/AST/Interp/Pointer.cpp

 //===--- Pointer.cpp - Types for the constexpr VM ---------------*- 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 "Pointer.h"
 #include "Function.h"
 #include "InterpBlock.h"
 #include "PrimType.h"
+#include "Program.h"
 
 using namespace clang;
 using namespace clang::interp;
 
-Pointer::Pointer(Block *Pointee) : Pointer(Pointee, 0, 0) {}
+Pointer::Pointer(Block *Pointee) : Pointee(Pointee), Base(0), Offset(0) {
+  if (Pointee)
+    Pointee->addPointer(this);
+}
 
-Pointer::Pointer(const Pointer &P) : Pointer(P.Pointee, P.Base, P.Offset) {}
+Pointer::Pointer(const Pointer &P) : Pointer(P.Pointee, P.Base, P.Offset) {
+  if (Pointee)
+    assert(Pointee->hasPointer(this));
+}
 
 Pointer::Pointer(Pointer &&P)
     : Pointee(P.Pointee), Base(P.Base), Offset(P.Offset) {
-  if (Pointee)
-    Pointee->movePointer(&P, this);
+  if (Pointee) {
+    assert(!Pointee->hasPointer(this));
+    Pointee->addPointer(this);
+    assert(Pointee->hasPointer(this));
+  }
 }
 
 Pointer::Pointer(Block *Pointee, unsigned Base, unsigned Offset)
     : Pointee(Pointee), Base(Base), Offset(Offset) {
   assert((Base == RootPtrMark || Base % alignof(void *) == 0) && "wrong base");
   if (Pointee)
     Pointee->addPointer(this);
 }
 
 Pointer::~Pointer() {
   if (Pointee) {
-    Pointee->removePointer(this);
     Pointee->cleanup();
+    Pointee->removePointer(this);
+    Pointee = nullptr;
   }
 }
 
 void Pointer::operator=(const Pointer &P) {
   Block *Old = Pointee;
 
   if (Pointee)
     Pointee->removePointer(this);
 
   Offset = P.Offset;
   Base = P.Base;
 
   Pointee = P.Pointee;
-  if (Pointee)
+  if (Pointee) {
     Pointee->addPointer(this);
+    assert(Pointee->hasPointer(this));
+  }
 
+  assert(Pointee->hasPointer(this));
   if (Old)
     Old->cleanup();
 }
 
 void Pointer::operator=(Pointer &&P) {
   Block *Old = Pointee;
 
-  if (Pointee)
+  if (this->Pointee)
     Pointee->removePointer(this);
 
   Offset = P.Offset;
   Base = P.Base;
-
   Pointee = P.Pointee;
-  if (Pointee)
-    Pointee->movePointer(&P, this);
+
+  if (Pointee) {
+    Pointee->addPointer(this);
+    assert(Pointee->hasPointer(this));
+  }
 
   if (Old)
     Old->cleanup();
 }
 
 APValue Pointer::toAPValue() const {
   APValue::LValueBase Base;
   llvm::SmallVector<APValue::LValuePathEntry, 5> Path;

clang/lib/AST/Interp/Program.h

public:
   unsigned createGlobalString(const StringLiteral *S);
 
   /// Returns a pointer to a global.
   Pointer getPtrGlobal(unsigned Idx);
 
   /// Returns the value of a global.
   Block *getGlobal(unsigned Idx) {
     assert(Idx < Globals.size());
-    return Globals[Idx]->block();
+    return Globals[Idx].block();
+  }
+
+  /// Checks whether the given pointer points to a global variable.
+  bool isGlobalPointer(const Pointer &P) const {
+    return false;
   }
 
   /// Finds a global's index.
   llvm::Optional<unsigned> getGlobal(const ValueDecl *VD);
 
   /// Returns or creates a global an creates an index to it.
   llvm::Optional<unsigned> getOrCreateGlobal(const ValueDecl *VD);
 
private:
   /// Native pointers referenced by bytecode.
   std::vector<const void *> NativePointers;
   /// Cached native pointer indices.
   llvm::DenseMap<const void *, unsigned> NativePointerIndices;
 
   /// Custom allocator for global storage.
   using PoolAllocTy = llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator>;
 
-  /// Descriptor + storage for a global object.
-  ///
-  /// Global objects never go out of scope, thus they do not track pointers.
-  class Global {
-  public:
-    /// Create a global descriptor for string literals.
-    template <typename... Tys>
-    Global(Tys... Args) : B(std::forward<Tys>(Args)...) {}
-
-    /// Allocates the global in the pool, reserving storate for data.
-    void *operator new(size_t Meta, PoolAllocTy &Alloc, size_t Data) {
-      return Alloc.Allocate(Meta + Data, alignof(void *));
-    }
-
-    /// Return a pointer to the data.
-    char *data() { return B.data(); }
-    /// Return a pointer to the block.
-    Block *block() { return &B; }
-
-  private:
-    /// Required metadata - does not actually track pointers.
-    Block B;
-  };
-
   /// Allocator for globals.
   PoolAllocTy Allocator;
 
-  /// Global objects.
-  std::vector<Global *> Globals;
+  /// All global variables we've created. We use Pointers instances here
+  /// so we get pointer tracking in the blocks.
+  std::vector<Pointer> Globals;
   /// Cached global indices.
   llvm::DenseMap<const void *, unsigned> GlobalIndices;
 
   /// Mapping from decls to record metadata.
   llvm::DenseMap<const RecordDecl *, Record *> Records;
 
   /// Dummy parameter to generate pointers from.
   llvm::DenseMap<const ParmVarDecl *, unsigned> DummyParams;
 
   /// Creates a new descriptor.
   template <typename... Ts>
   Descriptor *allocateDescriptor(Ts &&... Args) {
     return new (Allocator) Descriptor(std::forward<Ts>(Args)...);
   }
 
+  /// Creates a new Block.
+  template <typename... Ts>
+  Block *allocateBlock(const Descriptor *D, Ts &&...Args) {
+    Block *B = static_cast<Block *>(
+        Allocator.Allocate(sizeof(Block) + D->getAllocSize(), alignof(void *)));
+    new (B) Block(std::forward<Ts>(Args)...);
+    return B;
+  }
+
   /// No declaration ID.
   static constexpr unsigned NoDeclaration = (unsigned)-1;
   /// Last declaration ID.
   unsigned LastDeclaration = 0;
   /// Current declaration ID.
   unsigned CurrentDeclaration = NoDeclaration;
 
   /// Starts evaluating a declaration.

clang/lib/AST/Interp/Program.cpp

unsigned Program::createGlobalString(const StringLiteral *S) {
   case 4:
     CharType = PT_Uint32;
     break;
   default:
     llvm_unreachable("unsupported character width");
   }
 
   // Create a descriptor for the string.
-  Descriptor *Desc = allocateDescriptor(S, CharType, S->getLength() + 1,
-                                        /*isConst=*/true,
-                                        /*isTemporary=*/false,
-                                        /*isMutable=*/false);
+  Descriptor *Desc =
+      allocateDescriptor(S, CharType, S->getLength() + 1,
+                         /*ArrayFiller=*/nullptr, S->getLength() + 1,
+                         /*IsConst=*/true,
+                         /*IsTemporary=*/false,
+                         /*IsMutable=*/false);
 
   // Allocate storage for the string.
   // The byte length does not include the null terminator.
   unsigned I = Globals.size();
-  unsigned Sz = Desc->getAllocSize();
-  auto *G = new (Allocator, Sz) Global(Desc, /*isStatic=*/true,
-                                       /*isExtern=*/false);
-  Globals.push_back(G);
+  auto *G = allocateBlock(Desc, Desc, true, false);
+  Globals.emplace_back(G);
 
   // Construct the string in storage.
-  const Pointer Ptr(G->block());
+  const Pointer Ptr(G);
   for (unsigned I = 0, N = S->getLength(); I <= N; ++I) {
     Pointer Field = Ptr.atIndex(I).narrow();
     const uint32_t CodePoint = I == N ? 0 : S->getCodeUnit(I);
     switch (CharType) {
       case PT_Sint8: {
         using T = PrimConv<PT_Sint8>::T;
         Field.deref<T>() = T::from(CodePoint, BitWidth);
         break;
switch (CharType) {
         llvm_unreachable("unsupported character type");
     }
   }
   return I;
 }
 
 Pointer Program::getPtrGlobal(unsigned Idx) {
   assert(Idx < Globals.size());
-  return Pointer(Globals[Idx]->block());
+  return Globals[Idx];
 }
 
 llvm::Optional<unsigned> Program::getGlobal(const ValueDecl *VD) {
   auto It = GlobalIndices.find(VD);
   if (It != GlobalIndices.end())
     return It->second;
 
   // Find any previous declarations which were already evaluated.
llvm::Optional<unsigned> Program::createGlobal(const DeclTy &D, QualType Ty,
                                                const Expr *Init) {
   // Create a descriptor for the global.
   Descriptor *Desc;
   const bool IsConst = Ty.isConstQualified();
   const bool IsTemporary = D.dyn_cast<const Expr *>();
   if (auto T = Ctx.classify(Ty)) {
     Desc = createDescriptor(D, *T, IsConst, IsTemporary);
   } else {
-    Desc = createDescriptor(D, Ty.getTypePtr(), IsConst, IsTemporary);
+    Desc =
+        createDescriptor(D, Ty.getTypePtr(), IsConst, IsTemporary, false, Init);
   }
   if (!Desc)
     return {};
 
   // Allocate a block for storage.
   unsigned I = Globals.size();
-
-  auto *G = new (Allocator, Desc->getAllocSize())
-      Global(getCurrentDecl(), Desc, IsStatic, IsExtern);
-  G->block()->invokeCtor();
-
-  Globals.push_back(G);
+  auto *G = allocateBlock(Desc, getCurrentDecl(), Desc, IsStatic, IsExtern);
+  G->invokeCtor();
+  Globals.emplace_back(G);
 
   return I;
 }
 
 Function *Program::getFunction(const FunctionDecl *F) {
   F = F->getDefinition();
   auto It = Funcs.find(F);
   return It == Funcs.end() ? nullptr : It->second.get();
if (auto *Record = getOrCreateRecord(RT->getDecl()))
       return allocateDescriptor(D, Record, IsConst, IsTemporary, IsMutable);
   }
 
   // Arrays.
   if (auto ArrayType = Ty->getAsArrayTypeUnsafe()) {
     QualType ElemTy = ArrayType->getElementType();
     // Array of well-known bounds.
     if (auto CAT = dyn_cast<ConstantArrayType>(ArrayType)) {
-      size_t NumElems = CAT->getSize().getZExtValue();
+      const size_t NumElems = CAT->getSize().getZExtValue();
+      size_t NumGivenElems = NumElems;
+
+      const Expr *ArrayFiller = nullptr;
+      const auto *InitList = dyn_cast_if_present<InitListExpr>(Init);
+      if (InitList && InitList->hasArrayFiller()) {
+        ArrayFiller = InitList->getArrayFiller();
+
+        NumGivenElems = InitList->getNumInits();
+        assert(NumGivenElems < NumElems);
+        // TODO: Check if the array filler is element-dependent.
+        //   We can just copy that from ExprConstant.cpp \o/
+        // TODO: Is this really only for primitive arrays?
+      }
+
       if (llvm::Optional<PrimType> T = Ctx.classify(ElemTy)) {
         // Arrays of primitives.
         unsigned ElemSize = primSize(*T);
-        if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems) {
+        if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems)
           return {};
-        }
-        return allocateDescriptor(D, *T, NumElems, IsConst, IsTemporary,
-                                  IsMutable);
+        return allocateDescriptor(D, *T, NumGivenElems, ArrayFiller, NumElems,
+                                  IsConst, IsTemporary, IsMutable);
       } else {
         // Arrays of composites. In this case, the array is a list of pointers,
         // followed by the actual elements.
         Descriptor *ElemDesc =
             createDescriptor(D, ElemTy.getTypePtr(), IsConst, IsTemporary);
+
         if (!ElemDesc)
           return nullptr;
         InterpSize ElemSize =
             ElemDesc->getAllocSize() + sizeof(InlineDescriptor);
         if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems)
           return {};
         return allocateDescriptor(D, ElemDesc, NumElems, IsConst, IsTemporary,
                                   IsMutable);
Descriptor *Program::createDescriptor(const DeclTy &D, const Type *Ty,
   if (auto *AT = Ty->getAs<AtomicType>()) {
     const Type *InnerTy = AT->getValueType().getTypePtr();
     return createDescriptor(D, InnerTy, IsConst, IsTemporary, IsMutable);
   }
 
   // Complex types - represented as arrays of elements.
   if (auto *CT = Ty->getAs<ComplexType>()) {
     PrimType ElemTy = *Ctx.classify(CT->getElementType());
-    return allocateDescriptor(D, ElemTy, 2, IsConst, IsTemporary, IsMutable);
+    return allocateDescriptor(D, ElemTy, 2, nullptr, 2, IsConst, IsTemporary,
+                              IsMutable);
   }
 
   return nullptr;
 }

clang/test/AST/Interp/arrays.cpp

 struct fred {
   char s [6];
   int n;
 };
 
 struct fred y [] = { [0] = { .s[0] = 'q' } };
 #endif
 #pragma clang diagnostic pop
+
+namespace indices {
+  constexpr int first[] = {1};
+  constexpr int firstValue = first[2]; // ref-error {{must be initialized by a constant expression}} \
+                                       // ref-note {{cannot refer to element 2 of array of 1}} \
+                                       // expected-error {{must be initialized by a constant expression}} \
+                                       // expected-note {{cannot refer to element 2 of array of 1}}
+
+  constexpr int second[10] = {17};
+  constexpr int secondValue = second[10];// ref-error {{must be initialized by a constant expression}} \
+                                         // ref-note {{read of dereferenced one-past-the-end pointer}} \
+                                         // expected-error {{must be initialized by a constant expression}} \
+                                         // expected-note {{cannot refer to element 10 of array of 10}}
+
+  constexpr int negative = second[-2]; // ref-error {{must be initialized by a constant expression}} \
+                                       // ref-note {{cannot refer to element -2 of array of 10}} \
+                                       // expected-error {{must be initialized by a constant expression}} \
+                                       // expected-note {{cannot refer to element -2 of array of 10}}
+};
+
+namespace fillers {
+  constexpr int k[3] = {1337};
+  constexpr int foo(int m) {
+    return k[m];
+  }
+  static_assert(foo(0) == 1337, "");
+  static_assert(foo(1) == 0, "");
+  static_assert(foo(2) == 0, "");
+
+  constexpr int N = 12;
+  constexpr int local(unsigned i) {
+    int arr[N] = {1,2,3};
+    return arr[i];
+  }
+  static_assert(local(0) == 1, "");
+  static_assert(local(1) == 2, "");
+  static_assert(local(2) == 3, "");
+  static_assert(local(3) == 0, "");
+  static_assert(local(N - 1) == 0, "");
+
+  /// FIXME: Non-primitive array fillers are not handled properly currently,
+  ///   but nobody notices right now because all fillers are 0 anyway and
+  ///   that's also was we memset() the memory to.
+  constexpr int twodim[2][4] = {
+    {1,2},
+    {3,4}
+  };
+  static_assert(twodim[0][0] == 1, "");
+  static_assert(twodim[0][1] == 2, "");
+  static_assert(twodim[0][2] == 0, "");
+  static_assert(twodim[0][3] == 0, "");
+  static_assert(twodim[1][0] == 3, "");
+  static_assert(twodim[1][1] == 4, "");
+  static_assert(twodim[1][2] == 0, "");
+  static_assert(twodim[1][3] == 0, "");
+};