xref: /freebsd/contrib/llvm-project/clang/lib/AST/Interp/Interp.h (revision c66ec88fed842fbaad62c30d510644ceb7bd2d71) 
1 //===--- Interp.h - Interpreter for the constexpr VM ------------*- 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 // Definition of the interpreter state and entry point.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CLANG_AST_INTERP_INTERP_H
14 #define LLVM_CLANG_AST_INTERP_INTERP_H
15 
16 #include <limits>
17 #include <vector>
18 #include "Function.h"
19 #include "InterpFrame.h"
20 #include "InterpStack.h"
21 #include "InterpState.h"
22 #include "Opcode.h"
23 #include "PrimType.h"
24 #include "Program.h"
25 #include "State.h"
26 #include "clang/AST/ASTContext.h"
27 #include "clang/AST/ASTDiagnostic.h"
28 #include "clang/AST/CXXInheritance.h"
29 #include "clang/AST/Expr.h"
30 #include "llvm/ADT/APFloat.h"
31 #include "llvm/ADT/APSInt.h"
32 #include "llvm/Support/Endian.h"
33 
34 namespace clang {
35 namespace interp {
36 
37 using APInt = llvm::APInt;
38 using APSInt = llvm::APSInt;
39 
40 /// Convers a value to an APValue.
41 template <typename T> bool ReturnValue(const T &V, APValue &R) {
42   R = V.toAPValue();
43   return true;
44 }
45 
46 /// Checks if the variable has externally defined storage.
47 bool CheckExtern(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
48 
49 /// Checks if the array is offsetable.
50 bool CheckArray(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
51 
52 /// Checks if a pointer is live and accesible.
53 bool CheckLive(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
54                AccessKinds AK);
55 /// Checks if a pointer is null.
56 bool CheckNull(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
57                CheckSubobjectKind CSK);
58 
59 /// Checks if a pointer is in range.
60 bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
61                 AccessKinds AK);
62 
63 /// Checks if a field from which a pointer is going to be derived is valid.
64 bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
65                 CheckSubobjectKind CSK);
66 
67 /// Checks if a pointer points to const storage.
68 bool CheckConst(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
69 
70 /// Checks if a pointer points to a mutable field.
71 bool CheckMutable(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
72 
73 /// Checks if a value can be loaded from a block.
74 bool CheckLoad(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
75 
76 /// Checks if a value can be stored in a block.
77 bool CheckStore(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
78 
79 /// Checks if a method can be invoked on an object.
80 bool CheckInvoke(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
81 
82 /// Checks if a value can be initialized.
83 bool CheckInit(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
84 
85 /// Checks if a method can be called.
86 bool CheckCallable(InterpState &S, CodePtr OpPC, Function *F);
87 
88 /// Checks the 'this' pointer.
89 bool CheckThis(InterpState &S, CodePtr OpPC, const Pointer &This);
90 
91 /// Checks if a method is pure virtual.
92 bool CheckPure(InterpState &S, CodePtr OpPC, const CXXMethodDecl *MD);
93 
94 template <typename T> inline bool IsTrue(const T &V) { return !V.isZero(); }
95 
96 //===----------------------------------------------------------------------===//
97 // Add, Sub, Mul
98 //===----------------------------------------------------------------------===//
99 
100 template <typename T, bool (*OpFW)(T, T, unsigned, T *),
101           template <typename U> class OpAP>
102 bool AddSubMulHelper(InterpState &S, CodePtr OpPC, unsigned Bits, const T &LHS,
103                      const T &RHS) {
104   // Fast path - add the numbers with fixed width.
105   T Result;
106   if (!OpFW(LHS, RHS, Bits, &Result)) {
107     S.Stk.push<T>(Result);
108     return true;
109   }
110 
111   // If for some reason evaluation continues, use the truncated results.
112   S.Stk.push<T>(Result);
113 
114   // Slow path - compute the result using another bit of precision.
115   APSInt Value = OpAP<APSInt>()(LHS.toAPSInt(Bits), RHS.toAPSInt(Bits));
116 
117   // Report undefined behaviour, stopping if required.
118   const Expr *E = S.Current->getExpr(OpPC);
119   QualType Type = E->getType();
120   if (S.checkingForUndefinedBehavior()) {
121     auto Trunc = Value.trunc(Result.bitWidth()).toString(10);
122     auto Loc = E->getExprLoc();
123     S.report(Loc, diag::warn_integer_constant_overflow) << Trunc << Type;
124     return true;
125   } else {
126     S.CCEDiag(E, diag::note_constexpr_overflow) << Value << Type;
127     return S.noteUndefinedBehavior();
128   }
129 }
130 
131 template <PrimType Name, class T = typename PrimConv<Name>::T>
132 bool Add(InterpState &S, CodePtr OpPC) {
133   const T &RHS = S.Stk.pop<T>();
134   const T &LHS = S.Stk.pop<T>();
135   const unsigned Bits = RHS.bitWidth() + 1;
136   return AddSubMulHelper<T, T::add, std::plus>(S, OpPC, Bits, LHS, RHS);
137 }
138 
139 template <PrimType Name, class T = typename PrimConv<Name>::T>
140 bool Sub(InterpState &S, CodePtr OpPC) {
141   const T &RHS = S.Stk.pop<T>();
142   const T &LHS = S.Stk.pop<T>();
143   const unsigned Bits = RHS.bitWidth() + 1;
144   return AddSubMulHelper<T, T::sub, std::minus>(S, OpPC, Bits, LHS, RHS);
145 }
146 
147 template <PrimType Name, class T = typename PrimConv<Name>::T>
148 bool Mul(InterpState &S, CodePtr OpPC) {
149   const T &RHS = S.Stk.pop<T>();
150   const T &LHS = S.Stk.pop<T>();
151   const unsigned Bits = RHS.bitWidth() * 2;
152   return AddSubMulHelper<T, T::mul, std::multiplies>(S, OpPC, Bits, LHS, RHS);
153 }
154 
155 //===----------------------------------------------------------------------===//
156 // EQ, NE, GT, GE, LT, LE
157 //===----------------------------------------------------------------------===//
158 
159 using CompareFn = llvm::function_ref<bool(ComparisonCategoryResult)>;
160 
161 template <typename T>
162 bool CmpHelper(InterpState &S, CodePtr OpPC, CompareFn Fn) {
163   using BoolT = PrimConv<PT_Bool>::T;
164   const T &RHS = S.Stk.pop<T>();
165   const T &LHS = S.Stk.pop<T>();
166   S.Stk.push<BoolT>(BoolT::from(Fn(LHS.compare(RHS))));
167   return true;
168 }
169 
170 template <typename T>
171 bool CmpHelperEQ(InterpState &S, CodePtr OpPC, CompareFn Fn) {
172   return CmpHelper<T>(S, OpPC, Fn);
173 }
174 
175 template <>
176 inline bool CmpHelper<Pointer>(InterpState &S, CodePtr OpPC, CompareFn Fn) {
177   using BoolT = PrimConv<PT_Bool>::T;
178   const Pointer &RHS = S.Stk.pop<Pointer>();
179   const Pointer &LHS = S.Stk.pop<Pointer>();
180 
181   if (!Pointer::hasSameBase(LHS, RHS)) {
182     const SourceInfo &Loc = S.Current->getSource(OpPC);
183     S.FFDiag(Loc, diag::note_invalid_subexpr_in_const_expr);
184     return false;
185   } else {
186     unsigned VL = LHS.getByteOffset();
187     unsigned VR = RHS.getByteOffset();
188     S.Stk.push<BoolT>(BoolT::from(Fn(Compare(VL, VR))));
189     return true;
190   }
191 }
192 
193 template <>
194 inline bool CmpHelperEQ<Pointer>(InterpState &S, CodePtr OpPC, CompareFn Fn) {
195   using BoolT = PrimConv<PT_Bool>::T;
196   const Pointer &RHS = S.Stk.pop<Pointer>();
197   const Pointer &LHS = S.Stk.pop<Pointer>();
198 
199   if (LHS.isZero() && RHS.isZero()) {
200     S.Stk.push<BoolT>(BoolT::from(Fn(ComparisonCategoryResult::Equal)));
201     return true;
202   }
203 
204   if (!Pointer::hasSameBase(LHS, RHS)) {
205     S.Stk.push<BoolT>(BoolT::from(Fn(ComparisonCategoryResult::Unordered)));
206     return true;
207   } else {
208     unsigned VL = LHS.getByteOffset();
209     unsigned VR = RHS.getByteOffset();
210     S.Stk.push<BoolT>(BoolT::from(Fn(Compare(VL, VR))));
211     return true;
212   }
213 }
214 
215 template <PrimType Name, class T = typename PrimConv<Name>::T>
216 bool EQ(InterpState &S, CodePtr OpPC) {
217   return CmpHelperEQ<T>(S, OpPC, [](ComparisonCategoryResult R) {
218     return R == ComparisonCategoryResult::Equal;
219   });
220 }
221 
222 template <PrimType Name, class T = typename PrimConv<Name>::T>
223 bool NE(InterpState &S, CodePtr OpPC) {
224   return CmpHelperEQ<T>(S, OpPC, [](ComparisonCategoryResult R) {
225     return R != ComparisonCategoryResult::Equal;
226   });
227 }
228 
229 template <PrimType Name, class T = typename PrimConv<Name>::T>
230 bool LT(InterpState &S, CodePtr OpPC) {
231   return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
232     return R == ComparisonCategoryResult::Less;
233   });
234 }
235 
236 template <PrimType Name, class T = typename PrimConv<Name>::T>
237 bool LE(InterpState &S, CodePtr OpPC) {
238   return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
239     return R == ComparisonCategoryResult::Less ||
240            R == ComparisonCategoryResult::Equal;
241   });
242 }
243 
244 template <PrimType Name, class T = typename PrimConv<Name>::T>
245 bool GT(InterpState &S, CodePtr OpPC) {
246   return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
247     return R == ComparisonCategoryResult::Greater;
248   });
249 }
250 
251 template <PrimType Name, class T = typename PrimConv<Name>::T>
252 bool GE(InterpState &S, CodePtr OpPC) {
253   return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
254     return R == ComparisonCategoryResult::Greater ||
255            R == ComparisonCategoryResult::Equal;
256   });
257 }
258 
259 //===----------------------------------------------------------------------===//
260 // InRange
261 //===----------------------------------------------------------------------===//
262 
263 template <PrimType Name, class T = typename PrimConv<Name>::T>
264 bool InRange(InterpState &S, CodePtr OpPC) {
265   const T RHS = S.Stk.pop<T>();
266   const T LHS = S.Stk.pop<T>();
267   const T Value = S.Stk.pop<T>();
268 
269   S.Stk.push<bool>(LHS <= Value && Value <= RHS);
270   return true;
271 }
272 
273 //===----------------------------------------------------------------------===//
274 // Dup, Pop, Test
275 //===----------------------------------------------------------------------===//
276 
277 template <PrimType Name, class T = typename PrimConv<Name>::T>
278 bool Dup(InterpState &S, CodePtr OpPC) {
279   S.Stk.push<T>(S.Stk.peek<T>());
280   return true;
281 }
282 
283 template <PrimType Name, class T = typename PrimConv<Name>::T>
284 bool Pop(InterpState &S, CodePtr OpPC) {
285   S.Stk.pop<T>();
286   return true;
287 }
288 
289 //===----------------------------------------------------------------------===//
290 // Const
291 //===----------------------------------------------------------------------===//
292 
293 template <PrimType Name, class T = typename PrimConv<Name>::T>
294 bool Const(InterpState &S, CodePtr OpPC, const T &Arg) {
295   S.Stk.push<T>(Arg);
296   return true;
297 }
298 
299 //===----------------------------------------------------------------------===//
300 // Get/Set Local/Param/Global/This
301 //===----------------------------------------------------------------------===//
302 
303 template <PrimType Name, class T = typename PrimConv<Name>::T>
304 bool GetLocal(InterpState &S, CodePtr OpPC, uint32_t I) {
305   S.Stk.push<T>(S.Current->getLocal<T>(I));
306   return true;
307 }
308 
309 template <PrimType Name, class T = typename PrimConv<Name>::T>
310 bool SetLocal(InterpState &S, CodePtr OpPC, uint32_t I) {
311   S.Current->setLocal<T>(I, S.Stk.pop<T>());
312   return true;
313 }
314 
315 template <PrimType Name, class T = typename PrimConv<Name>::T>
316 bool GetParam(InterpState &S, CodePtr OpPC, uint32_t I) {
317   if (S.checkingPotentialConstantExpression()) {
318     return false;
319   }
320   S.Stk.push<T>(S.Current->getParam<T>(I));
321   return true;
322 }
323 
324 template <PrimType Name, class T = typename PrimConv<Name>::T>
325 bool SetParam(InterpState &S, CodePtr OpPC, uint32_t I) {
326   S.Current->setParam<T>(I, S.Stk.pop<T>());
327   return true;
328 }
329 
330 template <PrimType Name, class T = typename PrimConv<Name>::T>
331 bool GetField(InterpState &S, CodePtr OpPC, uint32_t I) {
332   const Pointer &Obj = S.Stk.peek<Pointer>();
333   if (!CheckNull(S, OpPC, Obj, CSK_Field))
334       return false;
335   if (!CheckRange(S, OpPC, Obj, CSK_Field))
336     return false;
337   const Pointer &Field = Obj.atField(I);
338   if (!CheckLoad(S, OpPC, Field))
339     return false;
340   S.Stk.push<T>(Field.deref<T>());
341   return true;
342 }
343 
344 template <PrimType Name, class T = typename PrimConv<Name>::T>
345 bool SetField(InterpState &S, CodePtr OpPC, uint32_t I) {
346   const T &Value = S.Stk.pop<T>();
347   const Pointer &Obj = S.Stk.peek<Pointer>();
348   if (!CheckNull(S, OpPC, Obj, CSK_Field))
349     return false;
350   if (!CheckRange(S, OpPC, Obj, CSK_Field))
351     return false;
352   const Pointer &Field = Obj.atField(I);
353   if (!CheckStore(S, OpPC, Field))
354     return false;
355   Field.deref<T>() = Value;
356   return true;
357 }
358 
359 template <PrimType Name, class T = typename PrimConv<Name>::T>
360 bool GetFieldPop(InterpState &S, CodePtr OpPC, uint32_t I) {
361   const Pointer &Obj = S.Stk.pop<Pointer>();
362   if (!CheckNull(S, OpPC, Obj, CSK_Field))
363     return false;
364   if (!CheckRange(S, OpPC, Obj, CSK_Field))
365     return false;
366   const Pointer &Field = Obj.atField(I);
367   if (!CheckLoad(S, OpPC, Field))
368     return false;
369   S.Stk.push<T>(Field.deref<T>());
370   return true;
371 }
372 
373 template <PrimType Name, class T = typename PrimConv<Name>::T>
374 bool GetThisField(InterpState &S, CodePtr OpPC, uint32_t I) {
375   if (S.checkingPotentialConstantExpression())
376     return false;
377   const Pointer &This = S.Current->getThis();
378   if (!CheckThis(S, OpPC, This))
379     return false;
380   const Pointer &Field = This.atField(I);
381   if (!CheckLoad(S, OpPC, Field))
382     return false;
383   S.Stk.push<T>(Field.deref<T>());
384   return true;
385 }
386 
387 template <PrimType Name, class T = typename PrimConv<Name>::T>
388 bool SetThisField(InterpState &S, CodePtr OpPC, uint32_t I) {
389   if (S.checkingPotentialConstantExpression())
390     return false;
391   const T &Value = S.Stk.pop<T>();
392   const Pointer &This = S.Current->getThis();
393   if (!CheckThis(S, OpPC, This))
394     return false;
395   const Pointer &Field = This.atField(I);
396   if (!CheckStore(S, OpPC, Field))
397     return false;
398   Field.deref<T>() = Value;
399   return true;
400 }
401 
402 template <PrimType Name, class T = typename PrimConv<Name>::T>
403 bool GetGlobal(InterpState &S, CodePtr OpPC, uint32_t I) {
404   auto *B = S.P.getGlobal(I);
405   if (B->isExtern())
406     return false;
407   S.Stk.push<T>(B->deref<T>());
408   return true;
409 }
410 
411 template <PrimType Name, class T = typename PrimConv<Name>::T>
412 bool SetGlobal(InterpState &S, CodePtr OpPC, uint32_t I) {
413   // TODO: emit warning.
414   return false;
415 }
416 
417 template <PrimType Name, class T = typename PrimConv<Name>::T>
418 bool InitGlobal(InterpState &S, CodePtr OpPC, uint32_t I) {
419   S.P.getGlobal(I)->deref<T>() = S.Stk.pop<T>();
420   return true;
421 }
422 
423 template <PrimType Name, class T = typename PrimConv<Name>::T>
424 bool InitThisField(InterpState &S, CodePtr OpPC, uint32_t I) {
425   if (S.checkingPotentialConstantExpression())
426     return false;
427   const Pointer &This = S.Current->getThis();
428   if (!CheckThis(S, OpPC, This))
429     return false;
430   const Pointer &Field = This.atField(I);
431   Field.deref<T>() = S.Stk.pop<T>();
432   Field.initialize();
433   return true;
434 }
435 
436 template <PrimType Name, class T = typename PrimConv<Name>::T>
437 bool InitThisBitField(InterpState &S, CodePtr OpPC, const Record::Field *F) {
438   if (S.checkingPotentialConstantExpression())
439     return false;
440   const Pointer &This = S.Current->getThis();
441   if (!CheckThis(S, OpPC, This))
442     return false;
443   const Pointer &Field = This.atField(F->Offset);
444   const auto &Value = S.Stk.pop<T>();
445   Field.deref<T>() = Value.truncate(F->Decl->getBitWidthValue(S.getCtx()));
446   Field.initialize();
447   return true;
448 }
449 
450 template <PrimType Name, class T = typename PrimConv<Name>::T>
451 bool InitThisFieldActive(InterpState &S, CodePtr OpPC, uint32_t I) {
452   if (S.checkingPotentialConstantExpression())
453     return false;
454   const Pointer &This = S.Current->getThis();
455   if (!CheckThis(S, OpPC, This))
456     return false;
457   const Pointer &Field = This.atField(I);
458   Field.deref<T>() = S.Stk.pop<T>();
459   Field.activate();
460   Field.initialize();
461   return true;
462 }
463 
464 template <PrimType Name, class T = typename PrimConv<Name>::T>
465 bool InitField(InterpState &S, CodePtr OpPC, uint32_t I) {
466   const T &Value = S.Stk.pop<T>();
467   const Pointer &Field = S.Stk.pop<Pointer>().atField(I);
468   Field.deref<T>() = Value;
469   Field.activate();
470   Field.initialize();
471   return true;
472 }
473 
474 template <PrimType Name, class T = typename PrimConv<Name>::T>
475 bool InitBitField(InterpState &S, CodePtr OpPC, const Record::Field *F) {
476   const T &Value = S.Stk.pop<T>();
477   const Pointer &Field = S.Stk.pop<Pointer>().atField(F->Offset);
478   Field.deref<T>() = Value.truncate(F->Decl->getBitWidthValue(S.getCtx()));
479   Field.activate();
480   Field.initialize();
481   return true;
482 }
483 
484 template <PrimType Name, class T = typename PrimConv<Name>::T>
485 bool InitFieldActive(InterpState &S, CodePtr OpPC, uint32_t I) {
486   const T &Value = S.Stk.pop<T>();
487   const Pointer &Ptr = S.Stk.pop<Pointer>();
488   const Pointer &Field = Ptr.atField(I);
489   Field.deref<T>() = Value;
490   Field.activate();
491   Field.initialize();
492   return true;
493 }
494 
495 //===----------------------------------------------------------------------===//
496 // GetPtr Local/Param/Global/Field/This
497 //===----------------------------------------------------------------------===//
498 
499 inline bool GetPtrLocal(InterpState &S, CodePtr OpPC, uint32_t I) {
500   S.Stk.push<Pointer>(S.Current->getLocalPointer(I));
501   return true;
502 }
503 
504 inline bool GetPtrParam(InterpState &S, CodePtr OpPC, uint32_t I) {
505   if (S.checkingPotentialConstantExpression()) {
506     return false;
507   }
508   S.Stk.push<Pointer>(S.Current->getParamPointer(I));
509   return true;
510 }
511 
512 inline bool GetPtrGlobal(InterpState &S, CodePtr OpPC, uint32_t I) {
513   S.Stk.push<Pointer>(S.P.getPtrGlobal(I));
514   return true;
515 }
516 
517 inline bool GetPtrField(InterpState &S, CodePtr OpPC, uint32_t Off) {
518   const Pointer &Ptr = S.Stk.pop<Pointer>();
519   if (!CheckNull(S, OpPC, Ptr, CSK_Field))
520     return false;
521   if (!CheckExtern(S, OpPC, Ptr))
522     return false;
523   if (!CheckRange(S, OpPC, Ptr, CSK_Field))
524     return false;
525   S.Stk.push<Pointer>(Ptr.atField(Off));
526   return true;
527 }
528 
529 inline bool GetPtrThisField(InterpState &S, CodePtr OpPC, uint32_t Off) {
530   if (S.checkingPotentialConstantExpression())
531     return false;
532   const Pointer &This = S.Current->getThis();
533   if (!CheckThis(S, OpPC, This))
534     return false;
535   S.Stk.push<Pointer>(This.atField(Off));
536   return true;
537 }
538 
539 inline bool GetPtrActiveField(InterpState &S, CodePtr OpPC, uint32_t Off) {
540   const Pointer &Ptr = S.Stk.pop<Pointer>();
541   if (!CheckNull(S, OpPC, Ptr, CSK_Field))
542     return false;
543   if (!CheckRange(S, OpPC, Ptr, CSK_Field))
544     return false;
545   Pointer Field = Ptr.atField(Off);
546   Ptr.deactivate();
547   Field.activate();
548   S.Stk.push<Pointer>(std::move(Field));
549   return true;
550 }
551 
552 inline bool GetPtrActiveThisField(InterpState &S, CodePtr OpPC, uint32_t Off) {
553  if (S.checkingPotentialConstantExpression())
554     return false;
555   const Pointer &This = S.Current->getThis();
556   if (!CheckThis(S, OpPC, This))
557     return false;
558   Pointer Field = This.atField(Off);
559   This.deactivate();
560   Field.activate();
561   S.Stk.push<Pointer>(std::move(Field));
562   return true;
563 }
564 
565 inline bool GetPtrBase(InterpState &S, CodePtr OpPC, uint32_t Off) {
566   const Pointer &Ptr = S.Stk.pop<Pointer>();
567   if (!CheckNull(S, OpPC, Ptr, CSK_Base))
568     return false;
569   S.Stk.push<Pointer>(Ptr.atField(Off));
570   return true;
571 }
572 
573 inline bool GetPtrThisBase(InterpState &S, CodePtr OpPC, uint32_t Off) {
574   if (S.checkingPotentialConstantExpression())
575     return false;
576   const Pointer &This = S.Current->getThis();
577   if (!CheckThis(S, OpPC, This))
578     return false;
579   S.Stk.push<Pointer>(This.atField(Off));
580   return true;
581 }
582 
583 inline bool VirtBaseHelper(InterpState &S, CodePtr OpPC, const RecordDecl *Decl,
584                            const Pointer &Ptr) {
585   Pointer Base = Ptr;
586   while (Base.isBaseClass())
587     Base = Base.getBase();
588 
589   auto *Field = Base.getRecord()->getVirtualBase(Decl);
590   S.Stk.push<Pointer>(Base.atField(Field->Offset));
591   return true;
592 }
593 
594 inline bool GetPtrVirtBase(InterpState &S, CodePtr OpPC, const RecordDecl *D) {
595   const Pointer &Ptr = S.Stk.pop<Pointer>();
596   if (!CheckNull(S, OpPC, Ptr, CSK_Base))
597     return false;
598   return VirtBaseHelper(S, OpPC, D, Ptr);
599 }
600 
601 inline bool GetPtrThisVirtBase(InterpState &S, CodePtr OpPC,
602                                const RecordDecl *D) {
603   if (S.checkingPotentialConstantExpression())
604     return false;
605   const Pointer &This = S.Current->getThis();
606   if (!CheckThis(S, OpPC, This))
607     return false;
608   return VirtBaseHelper(S, OpPC, D, S.Current->getThis());
609 }
610 
611 //===----------------------------------------------------------------------===//
612 // Load, Store, Init
613 //===----------------------------------------------------------------------===//
614 
615 template <PrimType Name, class T = typename PrimConv<Name>::T>
616 bool Load(InterpState &S, CodePtr OpPC) {
617   const Pointer &Ptr = S.Stk.peek<Pointer>();
618   if (!CheckLoad(S, OpPC, Ptr))
619     return false;
620   S.Stk.push<T>(Ptr.deref<T>());
621   return true;
622 }
623 
624 template <PrimType Name, class T = typename PrimConv<Name>::T>
625 bool LoadPop(InterpState &S, CodePtr OpPC) {
626   const Pointer &Ptr = S.Stk.pop<Pointer>();
627   if (!CheckLoad(S, OpPC, Ptr))
628     return false;
629   S.Stk.push<T>(Ptr.deref<T>());
630   return true;
631 }
632 
633 template <PrimType Name, class T = typename PrimConv<Name>::T>
634 bool Store(InterpState &S, CodePtr OpPC) {
635   const T &Value = S.Stk.pop<T>();
636   const Pointer &Ptr = S.Stk.peek<Pointer>();
637   if (!CheckStore(S, OpPC, Ptr))
638     return false;
639   Ptr.deref<T>() = Value;
640   return true;
641 }
642 
643 template <PrimType Name, class T = typename PrimConv<Name>::T>
644 bool StorePop(InterpState &S, CodePtr OpPC) {
645   const T &Value = S.Stk.pop<T>();
646   const Pointer &Ptr = S.Stk.pop<Pointer>();
647   if (!CheckStore(S, OpPC, Ptr))
648     return false;
649   Ptr.deref<T>() = Value;
650   return true;
651 }
652 
653 template <PrimType Name, class T = typename PrimConv<Name>::T>
654 bool StoreBitField(InterpState &S, CodePtr OpPC) {
655   const T &Value = S.Stk.pop<T>();
656   const Pointer &Ptr = S.Stk.peek<Pointer>();
657   if (!CheckStore(S, OpPC, Ptr))
658     return false;
659   if (auto *FD = Ptr.getField()) {
660     Ptr.deref<T>() = Value.truncate(FD->getBitWidthValue(S.getCtx()));
661   } else {
662     Ptr.deref<T>() = Value;
663   }
664   return true;
665 }
666 
667 template <PrimType Name, class T = typename PrimConv<Name>::T>
668 bool StoreBitFieldPop(InterpState &S, CodePtr OpPC) {
669   const T &Value = S.Stk.pop<T>();
670   const Pointer &Ptr = S.Stk.pop<Pointer>();
671   if (!CheckStore(S, OpPC, Ptr))
672     return false;
673   if (auto *FD = Ptr.getField()) {
674     Ptr.deref<T>() = Value.truncate(FD->getBitWidthValue(S.getCtx()));
675   } else {
676     Ptr.deref<T>() = Value;
677   }
678   return true;
679 }
680 
681 template <PrimType Name, class T = typename PrimConv<Name>::T>
682 bool InitPop(InterpState &S, CodePtr OpPC) {
683   const T &Value = S.Stk.pop<T>();
684   const Pointer &Ptr = S.Stk.pop<Pointer>();
685   if (!CheckInit(S, OpPC, Ptr))
686     return false;
687   Ptr.initialize();
688   new (&Ptr.deref<T>()) T(Value);
689   return true;
690 }
691 
692 template <PrimType Name, class T = typename PrimConv<Name>::T>
693 bool InitElem(InterpState &S, CodePtr OpPC, uint32_t Idx) {
694   const T &Value = S.Stk.pop<T>();
695   const Pointer &Ptr = S.Stk.peek<Pointer>().atIndex(Idx);
696   if (!CheckInit(S, OpPC, Ptr))
697     return false;
698   Ptr.initialize();
699   new (&Ptr.deref<T>()) T(Value);
700   return true;
701 }
702 
703 template <PrimType Name, class T = typename PrimConv<Name>::T>
704 bool InitElemPop(InterpState &S, CodePtr OpPC, uint32_t Idx) {
705   const T &Value = S.Stk.pop<T>();
706   const Pointer &Ptr = S.Stk.pop<Pointer>().atIndex(Idx);
707   if (!CheckInit(S, OpPC, Ptr))
708     return false;
709   Ptr.initialize();
710   new (&Ptr.deref<T>()) T(Value);
711   return true;
712 }
713 
714 //===----------------------------------------------------------------------===//
715 // AddOffset, SubOffset
716 //===----------------------------------------------------------------------===//
717 
718 template <class T, bool Add> bool OffsetHelper(InterpState &S, CodePtr OpPC) {
719   // Fetch the pointer and the offset.
720   const T &Offset = S.Stk.pop<T>();
721   const Pointer &Ptr = S.Stk.pop<Pointer>();
722   if (!CheckNull(S, OpPC, Ptr, CSK_ArrayIndex))
723     return false;
724   if (!CheckRange(S, OpPC, Ptr, CSK_ArrayToPointer))
725     return false;
726 
727   // Get a version of the index comparable to the type.
728   T Index = T::from(Ptr.getIndex(), Offset.bitWidth());
729   // A zero offset does not change the pointer, but in the case of an array
730   // it has to be adjusted to point to the first element instead of the array.
731   if (Offset.isZero()) {
732     S.Stk.push<Pointer>(Index.isZero() ? Ptr.atIndex(0) : Ptr);
733     return true;
734   }
735   // Arrays of unknown bounds cannot have pointers into them.
736   if (!CheckArray(S, OpPC, Ptr))
737     return false;
738 
739   // Compute the largest index into the array.
740   unsigned MaxIndex = Ptr.getNumElems();
741 
742   // Helper to report an invalid offset, computed as APSInt.
743   auto InvalidOffset = [&]() {
744     const unsigned Bits = Offset.bitWidth();
745     APSInt APOffset(Offset.toAPSInt().extend(Bits + 2), false);
746     APSInt APIndex(Index.toAPSInt().extend(Bits + 2), false);
747     APSInt NewIndex = Add ? (APIndex + APOffset) : (APIndex - APOffset);
748     S.CCEDiag(S.Current->getSource(OpPC), diag::note_constexpr_array_index)
749         << NewIndex
750         << /*array*/ static_cast<int>(!Ptr.inArray())
751         << static_cast<unsigned>(MaxIndex);
752     return false;
753   };
754 
755   // If the new offset would be negative, bail out.
756   if (Add && Offset.isNegative() && (Offset.isMin() || -Offset > Index))
757     return InvalidOffset();
758   if (!Add && Offset.isPositive() && Index < Offset)
759     return InvalidOffset();
760 
761   // If the new offset would be out of bounds, bail out.
762   unsigned MaxOffset = MaxIndex - Ptr.getIndex();
763   if (Add && Offset.isPositive() && Offset > MaxOffset)
764     return InvalidOffset();
765   if (!Add && Offset.isNegative() && (Offset.isMin() || -Offset > MaxOffset))
766     return InvalidOffset();
767 
768   // Offset is valid - compute it on unsigned.
769   int64_t WideIndex = static_cast<int64_t>(Index);
770   int64_t WideOffset = static_cast<int64_t>(Offset);
771   int64_t Result = Add ? (WideIndex + WideOffset) : (WideIndex - WideOffset);
772   S.Stk.push<Pointer>(Ptr.atIndex(static_cast<unsigned>(Result)));
773   return true;
774 }
775 
776 template <PrimType Name, class T = typename PrimConv<Name>::T>
777 bool AddOffset(InterpState &S, CodePtr OpPC) {
778   return OffsetHelper<T, true>(S, OpPC);
779 }
780 
781 template <PrimType Name, class T = typename PrimConv<Name>::T>
782 bool SubOffset(InterpState &S, CodePtr OpPC) {
783   return OffsetHelper<T, false>(S, OpPC);
784 }
785 
786 
787 //===----------------------------------------------------------------------===//
788 // Destroy
789 //===----------------------------------------------------------------------===//
790 
791 inline bool Destroy(InterpState &S, CodePtr OpPC, uint32_t I) {
792   S.Current->destroy(I);
793   return true;
794 }
795 
796 //===----------------------------------------------------------------------===//
797 // Cast, CastFP
798 //===----------------------------------------------------------------------===//
799 
800 template <PrimType TIn, PrimType TOut> bool Cast(InterpState &S, CodePtr OpPC) {
801   using T = typename PrimConv<TIn>::T;
802   using U = typename PrimConv<TOut>::T;
803   S.Stk.push<U>(U::from(S.Stk.pop<T>()));
804   return true;
805 }
806 
807 //===----------------------------------------------------------------------===//
808 // Zero, Nullptr
809 //===----------------------------------------------------------------------===//
810 
811 template <PrimType Name, class T = typename PrimConv<Name>::T>
812 bool Zero(InterpState &S, CodePtr OpPC) {
813   S.Stk.push<T>(T::zero());
814   return true;
815 }
816 
817 template <PrimType Name, class T = typename PrimConv<Name>::T>
818 inline bool Null(InterpState &S, CodePtr OpPC) {
819   S.Stk.push<T>();
820   return true;
821 }
822 
823 //===----------------------------------------------------------------------===//
824 // This, ImplicitThis
825 //===----------------------------------------------------------------------===//
826 
827 inline bool This(InterpState &S, CodePtr OpPC) {
828   // Cannot read 'this' in this mode.
829   if (S.checkingPotentialConstantExpression()) {
830     return false;
831   }
832 
833   const Pointer &This = S.Current->getThis();
834   if (!CheckThis(S, OpPC, This))
835     return false;
836 
837   S.Stk.push<Pointer>(This);
838   return true;
839 }
840 
841 //===----------------------------------------------------------------------===//
842 // Shr, Shl
843 //===----------------------------------------------------------------------===//
844 
845 template <PrimType TR, PrimType TL, class T = typename PrimConv<TR>::T>
846 unsigned Trunc(InterpState &S, CodePtr OpPC, unsigned Bits, const T &V) {
847   // C++11 [expr.shift]p1: Shift width must be less than the bit width of
848   // the shifted type.
849   if (Bits > 1 && V >= T::from(Bits, V.bitWidth())) {
850     const Expr *E = S.Current->getExpr(OpPC);
851     const APSInt Val = V.toAPSInt();
852     QualType Ty = E->getType();
853     S.CCEDiag(E, diag::note_constexpr_large_shift) << Val << Ty << Bits;
854     return Bits;
855   } else {
856     return static_cast<unsigned>(V);
857   }
858 }
859 
860 template <PrimType TL, PrimType TR, typename T = typename PrimConv<TL>::T>
861 inline bool ShiftRight(InterpState &S, CodePtr OpPC, const T &V, unsigned RHS) {
862   if (RHS >= V.bitWidth()) {
863     S.Stk.push<T>(T::from(0, V.bitWidth()));
864   } else {
865     S.Stk.push<T>(T::from(V >> RHS, V.bitWidth()));
866   }
867   return true;
868 }
869 
870 template <PrimType TL, PrimType TR, typename T = typename PrimConv<TL>::T>
871 inline bool ShiftLeft(InterpState &S, CodePtr OpPC, const T &V, unsigned RHS) {
872   if (V.isSigned() && !S.getLangOpts().CPlusPlus20) {
873     // C++11 [expr.shift]p2: A signed left shift must have a non-negative
874     // operand, and must not overflow the corresponding unsigned type.
875     // C++2a [expr.shift]p2: E1 << E2 is the unique value congruent to
876     // E1 x 2^E2 module 2^N.
877     if (V.isNegative()) {
878       const Expr *E = S.Current->getExpr(OpPC);
879       S.CCEDiag(E, diag::note_constexpr_lshift_of_negative) << V.toAPSInt();
880     } else if (V.countLeadingZeros() < RHS) {
881       S.CCEDiag(S.Current->getExpr(OpPC), diag::note_constexpr_lshift_discards);
882     }
883   }
884 
885   if (V.bitWidth() == 1) {
886     S.Stk.push<T>(V);
887   } else if (RHS >= V.bitWidth()) {
888     S.Stk.push<T>(T::from(0, V.bitWidth()));
889   } else {
890     S.Stk.push<T>(T::from(V.toUnsigned() << RHS, V.bitWidth()));
891   }
892   return true;
893 }
894 
895 template <PrimType TL, PrimType TR>
896 inline bool Shr(InterpState &S, CodePtr OpPC) {
897   const auto &RHS = S.Stk.pop<typename PrimConv<TR>::T>();
898   const auto &LHS = S.Stk.pop<typename PrimConv<TL>::T>();
899   const unsigned Bits = LHS.bitWidth();
900 
901   if (RHS.isSigned() && RHS.isNegative()) {
902     const SourceInfo &Loc = S.Current->getSource(OpPC);
903     S.CCEDiag(Loc, diag::note_constexpr_negative_shift) << RHS.toAPSInt();
904     return ShiftLeft<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, -RHS));
905   } else {
906     return ShiftRight<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, RHS));
907   }
908 }
909 
910 template <PrimType TL, PrimType TR>
911 inline bool Shl(InterpState &S, CodePtr OpPC) {
912   const auto &RHS = S.Stk.pop<typename PrimConv<TR>::T>();
913   const auto &LHS = S.Stk.pop<typename PrimConv<TL>::T>();
914   const unsigned Bits = LHS.bitWidth();
915 
916   if (RHS.isSigned() && RHS.isNegative()) {
917     const SourceInfo &Loc = S.Current->getSource(OpPC);
918     S.CCEDiag(Loc, diag::note_constexpr_negative_shift) << RHS.toAPSInt();
919     return ShiftRight<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, -RHS));
920   } else {
921     return ShiftLeft<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, RHS));
922   }
923 }
924 
925 //===----------------------------------------------------------------------===//
926 // NoRet
927 //===----------------------------------------------------------------------===//
928 
929 inline bool NoRet(InterpState &S, CodePtr OpPC) {
930   SourceLocation EndLoc = S.Current->getCallee()->getEndLoc();
931   S.FFDiag(EndLoc, diag::note_constexpr_no_return);
932   return false;
933 }
934 
935 //===----------------------------------------------------------------------===//
936 // NarrowPtr, ExpandPtr
937 //===----------------------------------------------------------------------===//
938 
939 inline bool NarrowPtr(InterpState &S, CodePtr OpPC) {
940   const Pointer &Ptr = S.Stk.pop<Pointer>();
941   S.Stk.push<Pointer>(Ptr.narrow());
942   return true;
943 }
944 
945 inline bool ExpandPtr(InterpState &S, CodePtr OpPC) {
946   const Pointer &Ptr = S.Stk.pop<Pointer>();
947   S.Stk.push<Pointer>(Ptr.expand());
948   return true;
949 }
950 
951 /// Interpreter entry point.
952 bool Interpret(InterpState &S, APValue &Result);
953 
954 } // namespace interp
955 } // namespace clang
956 
957 #endif
958