1 //===--- ByteCodeExprGen.h - Code generator for expressions -----*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Defines the constexpr bytecode compiler.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CLANG_AST_INTERP_BYTECODEEXPRGEN_H
14 #define LLVM_CLANG_AST_INTERP_BYTECODEEXPRGEN_H
15 
16 #include "ByteCodeEmitter.h"
17 #include "EvalEmitter.h"
18 #include "Pointer.h"
19 #include "PrimType.h"
20 #include "Record.h"
21 #include "clang/AST/Decl.h"
22 #include "clang/AST/Expr.h"
23 #include "clang/AST/StmtVisitor.h"
24 #include "clang/Basic/TargetInfo.h"
25 
26 namespace clang {
27 class QualType;
28 
29 namespace interp {
30 
31 template <class Emitter> class LocalScope;
32 template <class Emitter> class RecordScope;
33 template <class Emitter> class VariableScope;
34 template <class Emitter> class DeclScope;
35 template <class Emitter> class OptionScope;
36 template <class Emitter> class ArrayIndexScope;
37 
38 /// Compilation context for expressions.
39 template <class Emitter>
40 class ByteCodeExprGen : public ConstStmtVisitor<ByteCodeExprGen<Emitter>, bool>,
41                         public Emitter {
42 protected:
43   // Aliases for types defined in the emitter.
44   using LabelTy = typename Emitter::LabelTy;
45   using AddrTy = typename Emitter::AddrTy;
46 
47   /// Current compilation context.
48   Context &Ctx;
49   /// Program to link to.
50   Program &P;
51 
52 public:
53   /// Initializes the compiler and the backend emitter.
54   template <typename... Tys>
ByteCodeExprGen(Context & Ctx,Program & P,Tys &&...Args)55   ByteCodeExprGen(Context &Ctx, Program &P, Tys &&... Args)
56       : Emitter(Ctx, P, Args...), Ctx(Ctx), P(P) {}
57 
58   // Expression visitors - result returned on interp stack.
59   bool VisitCastExpr(const CastExpr *E);
60   bool VisitIntegerLiteral(const IntegerLiteral *E);
61   bool VisitParenExpr(const ParenExpr *E);
62   bool VisitBinaryOperator(const BinaryOperator *E);
63   bool VisitPointerArithBinOp(const BinaryOperator *E);
64   bool VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E);
65   bool VisitCallExpr(const CallExpr *E);
66   bool VisitCXXMemberCallExpr(const CXXMemberCallExpr *E);
67   bool VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *E);
68   bool VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *E);
69   bool VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *E);
70   bool VisitCXXThisExpr(const CXXThisExpr *E);
71   bool VisitUnaryOperator(const UnaryOperator *E);
72   bool VisitDeclRefExpr(const DeclRefExpr *E);
73   bool VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E);
74   bool VisitSubstNonTypeTemplateParmExpr(const SubstNonTypeTemplateParmExpr *E);
75   bool VisitArraySubscriptExpr(const ArraySubscriptExpr *E);
76   bool VisitInitListExpr(const InitListExpr *E);
77   bool VisitConstantExpr(const ConstantExpr *E);
78   bool VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *E);
79   bool VisitMemberExpr(const MemberExpr *E);
80   bool VisitArrayInitIndexExpr(const ArrayInitIndexExpr *E);
81   bool VisitOpaqueValueExpr(const OpaqueValueExpr *E);
82   bool VisitAbstractConditionalOperator(const AbstractConditionalOperator *E);
83   bool VisitStringLiteral(const StringLiteral *E);
84   bool VisitCharacterLiteral(const CharacterLiteral *E);
85   bool VisitCompoundAssignOperator(const CompoundAssignOperator *E);
86 
87 protected:
88   bool visitExpr(const Expr *E) override;
89   bool visitDecl(const VarDecl *VD) override;
90 
91 protected:
92   /// Emits scope cleanup instructions.
93   void emitCleanup();
94 
95   /// Returns a record type from a record or pointer type.
96   const RecordType *getRecordTy(QualType Ty);
97 
98   /// Returns a record from a record or pointer type.
99   Record *getRecord(QualType Ty);
100   Record *getRecord(const RecordDecl *RD);
101 
102   // Returns a function for the given FunctionDecl.
103   // If the function does not exist yet, it is compiled.
104   const Function *getFunction(const FunctionDecl *FD);
105 
106   /// Classifies a type.
classify(const Expr * E)107   std::optional<PrimType> classify(const Expr *E) const {
108     return E->isGLValue() ? PT_Ptr : classify(E->getType());
109   }
classify(QualType Ty)110   std::optional<PrimType> classify(QualType Ty) const {
111     return Ctx.classify(Ty);
112   }
113 
114   /// Classifies a known primitive type
classifyPrim(QualType Ty)115   PrimType classifyPrim(QualType Ty) const {
116     if (auto T = classify(Ty)) {
117       return *T;
118     }
119     llvm_unreachable("not a primitive type");
120   }
121 
122   /// Evaluates an expression for side effects and discards the result.
123   bool discard(const Expr *E);
124   /// Evaluates an expression and places result on stack.
125   bool visit(const Expr *E);
126   /// Compiles an initializer.
127   bool visitInitializer(const Expr *E);
128   /// Compiles an array initializer.
129   bool visitArrayInitializer(const Expr *Initializer);
130   /// Compiles a record initializer.
131   bool visitRecordInitializer(const Expr *Initializer);
132   /// Creates and initializes a variable from the given decl.
133   bool visitVarDecl(const VarDecl *VD);
134 
135   /// Visits an expression and converts it to a boolean.
136   bool visitBool(const Expr *E);
137 
138   /// Visits an initializer for a local.
visitLocalInitializer(const Expr * Init,unsigned I)139   bool visitLocalInitializer(const Expr *Init, unsigned I) {
140     if (!this->emitGetPtrLocal(I, Init))
141       return false;
142 
143     if (!visitInitializer(Init))
144       return false;
145 
146     return this->emitPopPtr(Init);
147   }
148 
149   /// Visits an initializer for a global.
visitGlobalInitializer(const Expr * Init,unsigned I)150   bool visitGlobalInitializer(const Expr *Init, unsigned I) {
151     if (!this->emitGetPtrGlobal(I, Init))
152       return false;
153 
154     if (!visitInitializer(Init))
155       return false;
156 
157     return this->emitPopPtr(Init);
158   }
159 
160   /// Visits a delegated initializer.
visitThisInitializer(const Expr * I)161   bool visitThisInitializer(const Expr *I) {
162     if (!this->emitThis(I))
163       return false;
164 
165     if (!visitInitializer(I))
166       return false;
167 
168     return this->emitPopPtr(I);
169   }
170 
171   /// Creates a local primitive value.
172   unsigned allocateLocalPrimitive(DeclTy &&Decl, PrimType Ty, bool IsMutable,
173                                   bool IsExtended = false);
174 
175   /// Allocates a space storing a local given its type.
176   std::optional<unsigned> allocateLocal(DeclTy &&Decl, bool IsExtended = false);
177 
178 private:
179   friend class VariableScope<Emitter>;
180   friend class LocalScope<Emitter>;
181   friend class RecordScope<Emitter>;
182   friend class DeclScope<Emitter>;
183   friend class OptionScope<Emitter>;
184   friend class ArrayIndexScope<Emitter>;
185 
186   /// Emits a zero initializer.
187   bool visitZeroInitializer(PrimType T, const Expr *E);
188 
189   enum class DerefKind {
190     /// Value is read and pushed to stack.
191     Read,
192     /// Direct method generates a value which is written. Returns pointer.
193     Write,
194     /// Direct method receives the value, pushes mutated value. Returns pointer.
195     ReadWrite,
196   };
197 
198   /// Method to directly load a value. If the value can be fetched directly,
199   /// the direct handler is called. Otherwise, a pointer is left on the stack
200   /// and the indirect handler is expected to operate on that.
201   bool dereference(const Expr *LV, DerefKind AK,
202                    llvm::function_ref<bool(PrimType)> Direct,
203                    llvm::function_ref<bool(PrimType)> Indirect);
204   bool dereferenceParam(const Expr *LV, PrimType T, const ParmVarDecl *PD,
205                         DerefKind AK,
206                         llvm::function_ref<bool(PrimType)> Direct,
207                         llvm::function_ref<bool(PrimType)> Indirect);
208   bool dereferenceVar(const Expr *LV, PrimType T, const VarDecl *PD,
209                       DerefKind AK, llvm::function_ref<bool(PrimType)> Direct,
210                       llvm::function_ref<bool(PrimType)> Indirect);
211 
212   /// Emits an APSInt constant.
213   bool emitConst(const APSInt &Value, const Expr *E);
emitConst(const APInt & Value,const Expr * E)214   bool emitConst(const APInt &Value, const Expr *E) {
215     return emitConst(static_cast<APSInt>(Value), E);
216   }
217 
218   /// Emits an integer constant.
219   template <typename T> bool emitConst(T Value, const Expr *E);
220 
221   /// Returns the CXXRecordDecl for the type of the given expression,
222   /// or nullptr if no such decl exists.
getRecordDecl(const Expr * E)223   const CXXRecordDecl *getRecordDecl(const Expr *E) const {
224     QualType T = E->getType();
225     if (const auto *RD = T->getPointeeCXXRecordDecl())
226       return RD;
227     return T->getAsCXXRecordDecl();
228   }
229 
230   /// Returns whether we should create a global variable for the
231   /// given VarDecl.
shouldBeGloballyIndexed(const VarDecl * VD)232   bool shouldBeGloballyIndexed(const VarDecl *VD) const {
233     return VD->hasGlobalStorage() || VD->isConstexpr();
234   }
235 
236 protected:
237   /// Variable to storage mapping.
238   llvm::DenseMap<const ValueDecl *, Scope::Local> Locals;
239 
240   /// OpaqueValueExpr to location mapping.
241   llvm::DenseMap<const OpaqueValueExpr *, unsigned> OpaqueExprs;
242 
243   /// Current scope.
244   VariableScope<Emitter> *VarScope = nullptr;
245 
246   /// Current argument index. Needed to emit ArrayInitIndexExpr.
247   std::optional<uint64_t> ArrayIndex;
248 
249   /// Flag indicating if return value is to be discarded.
250   bool DiscardResult = false;
251 };
252 
253 extern template class ByteCodeExprGen<ByteCodeEmitter>;
254 extern template class ByteCodeExprGen<EvalEmitter>;
255 
256 /// Scope chain managing the variable lifetimes.
257 template <class Emitter> class VariableScope {
258 public:
VariableScope(ByteCodeExprGen<Emitter> * Ctx)259   VariableScope(ByteCodeExprGen<Emitter> *Ctx)
260       : Ctx(Ctx), Parent(Ctx->VarScope) {
261     Ctx->VarScope = this;
262   }
263 
~VariableScope()264   virtual ~VariableScope() { Ctx->VarScope = this->Parent; }
265 
add(const Scope::Local & Local,bool IsExtended)266   void add(const Scope::Local &Local, bool IsExtended) {
267     if (IsExtended)
268       this->addExtended(Local);
269     else
270       this->addLocal(Local);
271   }
272 
addLocal(const Scope::Local & Local)273   virtual void addLocal(const Scope::Local &Local) {
274     if (this->Parent)
275       this->Parent->addLocal(Local);
276   }
277 
addExtended(const Scope::Local & Local)278   virtual void addExtended(const Scope::Local &Local) {
279     if (this->Parent)
280       this->Parent->addExtended(Local);
281   }
282 
emitDestruction()283   virtual void emitDestruction() {}
284 
getParent()285   VariableScope *getParent() { return Parent; }
286 
287 protected:
288   /// ByteCodeExprGen instance.
289   ByteCodeExprGen<Emitter> *Ctx;
290   /// Link to the parent scope.
291   VariableScope *Parent;
292 };
293 
294 /// Scope for local variables.
295 ///
296 /// When the scope is destroyed, instructions are emitted to tear down
297 /// all variables declared in this scope.
298 template <class Emitter> class LocalScope : public VariableScope<Emitter> {
299 public:
LocalScope(ByteCodeExprGen<Emitter> * Ctx)300   LocalScope(ByteCodeExprGen<Emitter> *Ctx) : VariableScope<Emitter>(Ctx) {}
301 
~LocalScope()302   ~LocalScope() override { this->emitDestruction(); }
303 
addLocal(const Scope::Local & Local)304   void addLocal(const Scope::Local &Local) override {
305     if (!Idx) {
306       Idx = this->Ctx->Descriptors.size();
307       this->Ctx->Descriptors.emplace_back();
308     }
309 
310     this->Ctx->Descriptors[*Idx].emplace_back(Local);
311   }
312 
emitDestruction()313   void emitDestruction() override {
314     if (!Idx)
315       return;
316     this->Ctx->emitDestroy(*Idx, SourceInfo{});
317   }
318 
319 protected:
320   /// Index of the scope in the chain.
321   std::optional<unsigned> Idx;
322 };
323 
324 /// Scope for storage declared in a compound statement.
325 template <class Emitter> class BlockScope final : public LocalScope<Emitter> {
326 public:
BlockScope(ByteCodeExprGen<Emitter> * Ctx)327   BlockScope(ByteCodeExprGen<Emitter> *Ctx) : LocalScope<Emitter>(Ctx) {}
328 
addExtended(const Scope::Local & Local)329   void addExtended(const Scope::Local &Local) override {
330     llvm_unreachable("Cannot create temporaries in full scopes");
331   }
332 };
333 
334 /// Expression scope which tracks potentially lifetime extended
335 /// temporaries which are hoisted to the parent scope on exit.
336 template <class Emitter> class ExprScope final : public LocalScope<Emitter> {
337 public:
ExprScope(ByteCodeExprGen<Emitter> * Ctx)338   ExprScope(ByteCodeExprGen<Emitter> *Ctx) : LocalScope<Emitter>(Ctx) {}
339 
addExtended(const Scope::Local & Local)340   void addExtended(const Scope::Local &Local) override {
341     assert(this->Parent);
342     this->Parent->addLocal(Local);
343   }
344 };
345 
346 template <class Emitter> class ArrayIndexScope final {
347 public:
ArrayIndexScope(ByteCodeExprGen<Emitter> * Ctx,uint64_t Index)348   ArrayIndexScope(ByteCodeExprGen<Emitter> *Ctx, uint64_t Index) : Ctx(Ctx) {
349     OldArrayIndex = Ctx->ArrayIndex;
350     Ctx->ArrayIndex = Index;
351   }
352 
~ArrayIndexScope()353   ~ArrayIndexScope() { Ctx->ArrayIndex = OldArrayIndex; }
354 
355 private:
356   ByteCodeExprGen<Emitter> *Ctx;
357   std::optional<uint64_t> OldArrayIndex;
358 };
359 
360 } // namespace interp
361 } // namespace clang
362 
363 #endif
364