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