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