lib/AST/Interp/Interp.h

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