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