nand created this revision.
nand added reviewers: rsmith, jfb, Bigcheese, dexonsmith.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
Implemented string constants and the following pointer operations:
- AddOffset
- SubOffset
- Narrow
- Expand
- LogicalNot
To allow for sensible tests, short-circuiting logical ops were also implemented.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D70087
Files:
clang/lib/AST/Interp/ByteCodeExprGen.cpp
clang/lib/AST/Interp/ByteCodeExprGen.h
clang/lib/AST/Interp/Interp.h
clang/lib/AST/Interp/Opcodes.td
clang/lib/AST/Interp/Opcodes/Logical.h
clang/lib/AST/Interp/Opcodes/Offset.h
clang/lib/AST/Interp/Program.cpp
clang/lib/AST/Interp/Program.h
clang/test/AST/Interp/string.cpp
Index: clang/test/AST/Interp/string.cpp
===================================================================
--- /dev/null
+++ clang/test/AST/Interp/string.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_cc1 -std=c++17 -fsyntax-only -fexperimental-new-constant-interpreter %s -verify
+// RUN: %clang_cc1 -std=c++17 -fsyntax-only %s -verify
+// expected-no-diagnostics
+
+constexpr bool streq(const char *a, const char *b) {
+ while (*a && *a == *b) {
+ a = a + 1;
+ b = b + 1;
+ }
+ return *a == *b;
+}
+
+constexpr bool is_equal() {
+ const char *a = "Hello";
+ const char *b = "Hello";
+ return streq(a, b);
+}
+
+static_assert(is_equal());
+
+constexpr bool not_equal() {
+ const char *a = "HA";
+ const char *b = "HB";
+ return streq(a, b);
+}
+
+static_assert(!streq("HA", "HB"));
Index: clang/lib/AST/Interp/Program.h
===================================================================
--- clang/lib/AST/Interp/Program.h
+++ clang/lib/AST/Interp/Program.h
@@ -63,6 +63,14 @@
public:
Program(Context &Ctx) : Ctx(Ctx) {}
+ /// Emits a string literal among global data.
+ unsigned createGlobalString(const StringLiteral *S);
+
+ /// Returns a pointer to a global.
+ Pointer getPtrGlobal(GlobalLocation Idx);
+ /// Returns a pointer to a global by index.
+ Pointer getPtrGlobal(const ValueDecl *VD);
+
/// Creates a new function from a code range.
template <typename... Ts>
Function *createFunction(const FunctionDecl *Def, Ts &&... Args) {
@@ -95,7 +103,11 @@
private:
friend class DeclScope;
- /// Reference to the VM context.
+
+ llvm::Optional<GlobalLocation> createGlobal(const DeclTy &D, QualType Ty,
+ bool IsStatic, bool IsExtern);
+
+ /// Reference to the VM context.
Context &Ctx;
/// Mapping from decls to cached bytecode functions.
llvm::DenseMap<const FunctionDecl *, std::unique_ptr<Function>> Funcs;
@@ -108,9 +120,38 @@
/// 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;
+ /// Cached global indices.
+ llvm::DenseMap<const void *, unsigned> GlobalIndices;
+
/// Creates a new descriptor.
template <typename... Ts> Descriptor *allocateDescriptor(Ts &&... Args) {
return new (Allocator) Descriptor(std::forward<Ts>(Args)...);
Index: clang/lib/AST/Interp/Program.cpp
===================================================================
--- clang/lib/AST/Interp/Program.cpp
+++ clang/lib/AST/Interp/Program.cpp
@@ -18,6 +18,78 @@
using namespace clang;
using namespace clang::interp;
+unsigned Program::createGlobalString(const StringLiteral *S) {
+ const size_t CharWidth = S->getCharByteWidth();
+ const size_t BitWidth = CharWidth * Ctx.getCharBit();
+
+ PrimType CharType;
+ switch (CharWidth) {
+ case 1:
+ CharType = PT_Sint8;
+ break;
+ case 2:
+ CharType = PT_Uint16;
+ break;
+ 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);
+
+ // 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);
+
+ // Construct the string in storage.
+ const Pointer Ptr(G->block());
+ 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;
+ }
+ case PT_Uint16: {
+ using T = PrimConv<PT_Uint16>::T;
+ Field.deref<T>() = T::from(CodePoint, BitWidth);
+ break;
+ }
+ case PT_Uint32: {
+ using T = PrimConv<PT_Uint32>::T;
+ Field.deref<T>() = T::from(CodePoint, BitWidth);
+ break;
+ }
+ default:
+ llvm_unreachable("unsupported character type");
+ }
+ }
+ return I;
+}
+
+Pointer Program::getPtrGlobal(GlobalLocation G) {
+ assert(G.Index < Globals.size());
+ return Pointer(Globals[G.Index]->block());
+}
+
+Pointer Program::getPtrGlobal(const ValueDecl *VD) {
+ auto It = GlobalIndices.find(VD);
+ assert(It != GlobalIndices.end() && "missing global");
+ return Pointer(Globals[It->second]->block());
+}
+
Function *Program::getFunction(const FunctionDecl *F) {
F = F->getDefinition();
auto It = Funcs.find(F);
@@ -36,4 +108,3 @@
// A relocation which traps if not resolved.
return nullptr;
}
-
Index: clang/lib/AST/Interp/Opcodes/Offset.h
===================================================================
--- /dev/null
+++ clang/lib/AST/Interp/Opcodes/Offset.h
@@ -0,0 +1,86 @@
+//===--- PoitnerArithmetic.h - Pointer arithmetic instructions --*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of the pointer offset opcodes: AddOffset, SubOffset
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_OPCODES_OFFSET_H
+#define LLVM_CLANG_AST_INTERP_OPCODES_OFFSET_H
+
+namespace detail {
+
+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 (!S.CheckNull(OpPC, Ptr, CSK_ArrayIndex))
+ return false;
+ if (!S.CheckRange(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.
+ 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 (!S.CheckArray(OpPC, Ptr))
+ return false;
+
+ // 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);
+ APSInt NewIndex = Add ? (APIndex + APOffset) : (APIndex - APOffset);
+ S.CCEDiag(S.getSource(OpPC), diag::note_constexpr_array_index)
+ << NewIndex << /*array*/ static_cast<int>(!Ptr.inArray())
+ << static_cast<unsigned>(MaxIndex);
+ return false;
+ };
+
+ // If the new offset would be negative, bail out.
+ if (Add && Offset.isNegative() && (Offset.isMin() || -Offset > Index))
+ return InvalidOffset();
+ if (!Add && Offset.isPositive() && Index < Offset)
+ return InvalidOffset();
+
+ // If the new offset would be out of bounds, bail out.
+ unsigned MaxOffset = MaxIndex - Ptr.getIndex();
+ if (Add && Offset.isPositive() && Offset > MaxOffset)
+ return InvalidOffset();
+ if (!Add && 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)));
+ return true;
+}
+
+} // namespace detail
+
+template <PrimType Name> bool AddOffset(InterpState &S, CodePtr OpPC) {
+ return detail::OffsetHelper<typename PrimConv<Name>::T, true>(S, OpPC);
+}
+
+template <PrimType Name> bool SubOffset(InterpState &S, CodePtr OpPC) {
+ return detail::OffsetHelper<typename PrimConv<Name>::T, false>(S, OpPC);
+}
+
+#endif
Index: clang/lib/AST/Interp/Opcodes/Logical.h
===================================================================
--- /dev/null
+++ clang/lib/AST/Interp/Opcodes/Logical.h
@@ -0,0 +1,24 @@
+//===--- Logical.h - Logical instructions -----------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of logical instructions: LNot
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_OPCODES_LOGICAL_H
+#define LLVM_CLANG_AST_INTERP_OPCODES_LOGICAL_H
+
+
+template <PrimType Name>
+bool LogicalNot(InterpState &S, CodePtr OpPC) {
+ S.Stk.push<bool>(S.Stk.pop<typename PrimConv<Name>::T>().isZero());
+ return true;
+}
+
+
+#endif
Index: clang/lib/AST/Interp/Opcodes.td
===================================================================
--- clang/lib/AST/Interp/Opcodes.td
+++ clang/lib/AST/Interp/Opcodes.td
@@ -239,6 +239,20 @@
// Offset of parameter.
let Args = [ArgUint32];
}
+// [] -> [Pointer]
+def GetPtrGlobal : Opcode {
+ // Index of global.
+ let Args = [ArgUint32];
+}
+
+//===----------------------------------------------------------------------===//
+// Pointer manipulation
+//===----------------------------------------------------------------------===//
+
+// [Pointer] -> [Pointer]
+def NarrowPtr : Opcode;
+// [Pointer] -> [Pointer]
+def ExpandPtr : Opcode;
//===----------------------------------------------------------------------===//
// Direct field accessors
@@ -296,6 +310,15 @@
// [Pointer, Value] -> []
def StorePop : StoreOpcode {}
+//===----------------------------------------------------------------------===//
+// Pointer arithmetic.
+//===----------------------------------------------------------------------===//
+
+// [Pointer, Integral] -> [Pointer]
+def AddOffset : AluOpcode;
+// [Pointer, Integral] -> [Pointer]
+def SubOffset : AluOpcode;
+
//===----------------------------------------------------------------------===//
// Binary operators.
//===----------------------------------------------------------------------===//
@@ -316,6 +339,11 @@
let Types = [AllTypeClass];
let HasGroup = 1;
}
+// [Value] -> [Bool]
+def LogicalNot : Opcode {
+ let Types = [AllTypeClass];
+ let HasGroup = 1;
+}
//===----------------------------------------------------------------------===//
// Comparison opcodes.
Index: clang/lib/AST/Interp/Interp.h
===================================================================
--- clang/lib/AST/Interp/Interp.h
+++ clang/lib/AST/Interp/Interp.h
@@ -199,6 +199,11 @@
return true;
}
+inline bool GetPtrGlobal(InterpState &S, CodePtr OpPC, uint32_t I) {
+ S.Stk.push<Pointer>(S.P.getPtrGlobal(I));
+ return true;
+}
+
//===----------------------------------------------------------------------===//
// Load, Store, Init
//===----------------------------------------------------------------------===//
@@ -287,6 +292,22 @@
return false;
}
+//===----------------------------------------------------------------------===//
+// NarrowPtr, ExpandPtr
+//===----------------------------------------------------------------------===//
+
+inline bool NarrowPtr(InterpState &S, CodePtr OpPC) {
+ const Pointer &Ptr = S.Stk.pop<Pointer>();
+ S.Stk.push<Pointer>(Ptr.narrow());
+ return true;
+}
+
+inline bool ExpandPtr(InterpState &S, CodePtr OpPC) {
+ const Pointer &Ptr = S.Stk.pop<Pointer>();
+ S.Stk.push<Pointer>(Ptr.expand());
+ return true;
+}
+
//===----------------------------------------------------------------------===//
// Trap
//===----------------------------------------------------------------------===//
@@ -298,6 +319,8 @@
}
#include "Opcodes/Comparison.h"
+#include "Opcodes/Logical.h"
+#include "Opcodes/Offset.h"
} // namespace interp
} // namespace clang
Index: clang/lib/AST/Interp/ByteCodeExprGen.h
===================================================================
--- clang/lib/AST/Interp/ByteCodeExprGen.h
+++ clang/lib/AST/Interp/ByteCodeExprGen.h
@@ -71,9 +71,13 @@
bool VisitCastExpr(const CastExpr *E);
bool VisitConstantExpr(const ConstantExpr *E);
bool VisitIntegerLiteral(const IntegerLiteral *E);
+ bool VisitStringLiteral(const StringLiteral *E);
bool VisitParenExpr(const ParenExpr *E);
bool VisitBinaryOperator(const BinaryOperator *E);
bool VisitUnaryMinus(const UnaryOperator *E);
+ bool VisitUnaryDeref(const UnaryOperator *E);
+ bool VisitUnaryAddrOf(const UnaryOperator *E);
+ bool VisitUnaryLNot(const UnaryOperator *E);
bool VisitCallExpr(const CallExpr *E);
// Fallback methods for nodes which are not yet implemented.
@@ -150,6 +154,11 @@
bool emitFunctionCall(const FunctionDecl *Callee, llvm::Optional<PrimType> T,
const Expr *Call);
+ /// Visits a short-circuit logical operator: && or ||.
+ bool visitShortCircuit(const BinaryOperator *E);
+ /// Compiles an offset calculation.
+ bool visitOffset(const Expr *Ptr, const Expr *Off, const Expr *E, UnaryFn Op);
+ /// Compiles an assignment.
bool visitAssign(PrimType T, const BinaryOperator *BO);
enum class DerefKind {
Index: clang/lib/AST/Interp/ByteCodeExprGen.cpp
===================================================================
--- clang/lib/AST/Interp/ByteCodeExprGen.cpp
+++ clang/lib/AST/Interp/ByteCodeExprGen.cpp
@@ -229,6 +229,15 @@
return false;
}
+template <class Emitter>
+bool ByteCodeExprGen<Emitter>::VisitStringLiteral(const StringLiteral *E) {
+ if (InitFn)
+ return this->bail(E);
+ if (DiscardResult)
+ return true;
+ return this->emitGetPtrGlobal(P.createGlobalString(E), E);
+}
+
template <class Emitter>
bool ByteCodeExprGen<Emitter>::VisitParenExpr(const ParenExpr *PE) {
return this->Visit(PE->getSubExpr());
@@ -267,22 +276,22 @@
switch (BO->getOpcode()) {
case BO_Add: {
if (isPointer(*LT) && !isPointer(*RT))
- return this->bail(BO);
- if (isPointer(*RT) && !isPointer(*LT))
- return this->bail(BO);
+ return visitOffset(LHS, RHS, BO, &ByteCodeExprGen::emitAddOffset);
+ if (!isPointer(*RT) && isPointer(*LT))
+ return visitOffset(RHS, LHS, BO, &ByteCodeExprGen::emitAddOffset);
break;
}
case BO_Sub: {
if (isPointer(*LT) && isPointer(*RT))
return this->bail(BO);
- if (isPointer(*LT) && isPointer(*RT))
- return this->bail(BO);
+ if (isPointer(*LT) && !isPointer(*RT))
+ return visitOffset(LHS, RHS, BO, &ByteCodeExprGen::emitSubOffset);
break;
}
case BO_LOr:
case BO_LAnd:
- return this->bail(BO);
+ return visitShortCircuit(BO);
default:
break;
@@ -333,6 +342,36 @@
return this->bail(UM);
}
+template <class Emitter>
+bool ByteCodeExprGen<Emitter>::VisitUnaryDeref(const UnaryOperator *E) {
+ if (!this->Visit(E->getSubExpr()))
+ return false;
+ if (DiscardResult)
+ return true;
+ if (needsAdjust(E->getType()))
+ return this->emitNarrowPtr(E);
+ return true;
+}
+
+template <class Emitter>
+bool ByteCodeExprGen<Emitter>::VisitUnaryAddrOf(const UnaryOperator *E) {
+ if (!this->Visit(E->getSubExpr()))
+ return false;
+ if (DiscardResult)
+ return true;
+ if (needsAdjust(E->getType()))
+ return this->emitExpandPtr(E);
+ return true;
+}
+
+template <class Emitter>
+bool ByteCodeExprGen<Emitter>::VisitUnaryLNot(const UnaryOperator *UO) {
+ if (!this->Visit(UO->getSubExpr()))
+ return false;
+ PrimType T = *classify(UO->getType());
+ return DiscardResult ? true : this->emitLogicalNot(T, UO);
+}
+
template <class Emitter>
bool ByteCodeExprGen<Emitter>::VisitCallExpr(const CallExpr *CE) {
// Emit the pointer to build the return value into.
@@ -415,6 +454,45 @@
}
}
+
+template <class Emitter>
+bool ByteCodeExprGen<Emitter>::visitOffset(const Expr *Ptr, const Expr *Off,
+ const Expr *E, UnaryFn Op) {
+ if (!visit(Ptr))
+ return false;
+ if (!visit(Off))
+ return false;
+ if (!(this->*Op)(*classify(Off->getType()), E))
+ return false;
+ return DiscardResult ? this->emitPopPtr(E) : true;
+}
+
+template <class Emitter>
+bool ByteCodeExprGen<Emitter>::visitShortCircuit(const BinaryOperator *E) {
+ if (!visitBool(E->getLHS()))
+ return false;
+
+ LabelTy Short = this->getLabel();
+ const bool IsTrue = E->getOpcode() == BO_LAnd;
+ if (DiscardResult) {
+ if (!(IsTrue ? this->jumpFalse(Short) : this->jumpTrue(Short)))
+ return false;
+ if (!this->discard(E->getRHS()))
+ return false;
+ } else {
+ if (!this->emitDupBool(E))
+ return false;
+ if (!(IsTrue ? this->jumpFalse(Short) : this->jumpTrue(Short)))
+ return false;
+ if (!this->emitPopBool(E))
+ return false;
+ if (!visitBool(E->getRHS()))
+ return false;
+ }
+ this->fallthrough(Short);
+ return true;
+}
+
template <class Emitter>
bool ByteCodeExprGen<Emitter>::visitAssign(PrimType T,
const BinaryOperator *BO) {
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
