clang/lib/AST/APValue.cpp

   1 //===--- APValue.cpp - Union class for APFloat/APSInt/Complex -------------===//
   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 //  This file implements the APValue class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/AST/APValue.h"
  14 #include "Linkage.h"
  15 #include "clang/AST/ASTContext.h"
  16 #include "clang/AST/CharUnits.h"
  17 #include "clang/AST/DeclCXX.h"
  18 #include "clang/AST/Expr.h"
  19 #include "clang/AST/ExprCXX.h"
  20 #include "clang/AST/Type.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 using namespace clang;
  24
  25 /// The identity of a type_info object depends on the canonical unqualified
  26 /// type only.
  27 TypeInfoLValue::TypeInfoLValue(const Type *T)
  28     : T(T->getCanonicalTypeUnqualified().getTypePtr()) {}
  29
  30 void TypeInfoLValue::print(llvm::raw_ostream &Out,
  31                            const PrintingPolicy &Policy) const {
  32   Out << "typeid(";
  33   QualType(getType(), 0).print(Out, Policy);
  34   Out << ")";
  35 }
  36
  37 static_assert(
  38     1 << llvm::PointerLikeTypeTraits<TypeInfoLValue>::NumLowBitsAvailable <=
  39         alignof(Type),
  40     "Type is insufficiently aligned");
  41
  42 APValue::LValueBase::LValueBase(const ValueDecl *P, unsigned I, unsigned V)
  43     : Ptr(P ? cast<ValueDecl>(P->getCanonicalDecl()) : nullptr), Local{I, V} {}
  44 APValue::LValueBase::LValueBase(const Expr *P, unsigned I, unsigned V)
  45     : Ptr(P), Local{I, V} {}
  46
  47 APValue::LValueBase APValue::LValueBase::getDynamicAlloc(DynamicAllocLValue LV,
  48                                                          QualType Type) {
  49   LValueBase Base;
  50   Base.Ptr = LV;
  51   Base.DynamicAllocType = Type.getAsOpaquePtr();
  52   return Base;
  53 }
  54
  55 APValue::LValueBase APValue::LValueBase::getTypeInfo(TypeInfoLValue LV,
  56                                                      QualType TypeInfo) {
  57   LValueBase Base;
  58   Base.Ptr = LV;
  59   Base.TypeInfoType = TypeInfo.getAsOpaquePtr();
  60   return Base;
  61 }
  62
  63 QualType APValue::LValueBase::getType() const {
  64   if (!*this) return QualType();
  65   if (const ValueDecl *D = dyn_cast<const ValueDecl*>()) {
  66     // FIXME: It's unclear where we're supposed to take the type from, and
  67     // this actually matters for arrays of unknown bound. Eg:
  68     //
  69     // extern int arr[]; void f() { extern int arr[3]; };
  70     // constexpr int *p = &arr[1]; // valid?
  71     //
  72     // For now, we take the most complete type we can find.
  73     for (auto *Redecl = cast<ValueDecl>(D->getMostRecentDecl()); Redecl;
  74          Redecl = cast_or_null<ValueDecl>(Redecl->getPreviousDecl())) {
  75       QualType T = Redecl->getType();
  76       if (!T->isIncompleteArrayType())
  77         return T;
  78     }
  79     return D->getType();
  80   }
  81
  82   if (is<TypeInfoLValue>())
  83     return getTypeInfoType();
  84
  85   if (is<DynamicAllocLValue>())
  86     return getDynamicAllocType();
  87
  88   const Expr *Base = get<const Expr*>();
  89
  90   // For a materialized temporary, the type of the temporary we materialized
  91   // may not be the type of the expression.
  92   if (const MaterializeTemporaryExpr *MTE =
  93           llvm::dyn_cast<MaterializeTemporaryExpr>(Base)) {
  94     SmallVector<const Expr *, 2> CommaLHSs;
  95     SmallVector<SubobjectAdjustment, 2> Adjustments;
  96     const Expr *Temp = MTE->getSubExpr();
  97     const Expr *Inner = Temp->skipRValueSubobjectAdjustments(CommaLHSs,
  98                                                              Adjustments);
  99     // Keep any cv-qualifiers from the reference if we generated a temporary
 100     // for it directly. Otherwise use the type after adjustment.
 101     if (!Adjustments.empty())
 102       return Inner->getType();
 103   }
 104
 105   return Base->getType();
 106 }
 107
 108 unsigned APValue::LValueBase::getCallIndex() const {
 109   return (is<TypeInfoLValue>() || is<DynamicAllocLValue>()) ? 0
 110                                                             : Local.CallIndex;
 111 }
 112
 113 unsigned APValue::LValueBase::getVersion() const {
 114   return (is<TypeInfoLValue>() || is<DynamicAllocLValue>()) ? 0 : Local.Version;
 115 }
 116
 117 QualType APValue::LValueBase::getTypeInfoType() const {
 118   assert(is<TypeInfoLValue>() && "not a type_info lvalue");
 119   return QualType::getFromOpaquePtr(TypeInfoType);
 120 }
 121
 122 QualType APValue::LValueBase::getDynamicAllocType() const {
 123   assert(is<DynamicAllocLValue>() && "not a dynamic allocation lvalue");
 124   return QualType::getFromOpaquePtr(DynamicAllocType);
 125 }
 126
 127 void APValue::LValueBase::Profile(llvm::FoldingSetNodeID &ID) const {
 128   ID.AddPointer(Ptr.getOpaqueValue());
 129   if (is<TypeInfoLValue>() || is<DynamicAllocLValue>())
 130     return;
 131   ID.AddInteger(Local.CallIndex);
 132   ID.AddInteger(Local.Version);
 133 }
 134
 135 namespace clang {
 136 bool operator==(const APValue::LValueBase &LHS,
 137                 const APValue::LValueBase &RHS) {
 138   if (LHS.Ptr != RHS.Ptr)
 139     return false;
 140   if (LHS.is<TypeInfoLValue>() || LHS.is<DynamicAllocLValue>())
 141     return true;
 142   return LHS.Local.CallIndex == RHS.Local.CallIndex &&
 143          LHS.Local.Version == RHS.Local.Version;
 144 }
 145 }
 146
 147 APValue::LValuePathEntry::LValuePathEntry(BaseOrMemberType BaseOrMember) {
 148   if (const Decl *D = BaseOrMember.getPointer())
 149     BaseOrMember.setPointer(D->getCanonicalDecl());
 150   Value = reinterpret_cast<uintptr_t>(BaseOrMember.getOpaqueValue());
 151 }
 152
 153 void APValue::LValuePathEntry::Profile(llvm::FoldingSetNodeID &ID) const {
 154   ID.AddInteger(Value);
 155 }
 156
 157 APValue::LValuePathSerializationHelper::LValuePathSerializationHelper(
 158     ArrayRef<LValuePathEntry> Path, QualType ElemTy)
 159     : Ty((const void *)ElemTy.getTypePtrOrNull()), Path(Path) {}
 160
 161 QualType APValue::LValuePathSerializationHelper::getType() {
 162   return QualType::getFromOpaquePtr(Ty);
 163 }
 164
 165 namespace {
 166   struct LVBase {
 167     APValue::LValueBase Base;
 168     CharUnits Offset;
 169     unsigned PathLength;
 170     bool IsNullPtr : 1;
 171     bool IsOnePastTheEnd : 1;
 172   };
 173 }
 174
 175 void *APValue::LValueBase::getOpaqueValue() const {
 176   return Ptr.getOpaqueValue();
 177 }
 178
 179 bool APValue::LValueBase::isNull() const {
 180   return Ptr.isNull();
 181 }
 182
 183 APValue::LValueBase::operator bool () const {
 184   return static_cast<bool>(Ptr);
 185 }
 186
 187 clang::APValue::LValueBase
 188 llvm::DenseMapInfo<clang::APValue::LValueBase>::getEmptyKey() {
 189   clang::APValue::LValueBase B;
 190   B.Ptr = DenseMapInfo<const ValueDecl*>::getEmptyKey();
 191   return B;
 192 }
 193
 194 clang::APValue::LValueBase
 195 llvm::DenseMapInfo<clang::APValue::LValueBase>::getTombstoneKey() {
 196   clang::APValue::LValueBase B;
 197   B.Ptr = DenseMapInfo<const ValueDecl*>::getTombstoneKey();
 198   return B;
 199 }
 200
 201 namespace clang {
 202 llvm::hash_code hash_value(const APValue::LValueBase &Base) {
 203   if (Base.is<TypeInfoLValue>() || Base.is<DynamicAllocLValue>())
 204     return llvm::hash_value(Base.getOpaqueValue());
 205   return llvm::hash_combine(Base.getOpaqueValue(), Base.getCallIndex(),
 206                             Base.getVersion());
 207 }
 208 }
 209
 210 unsigned llvm::DenseMapInfo<clang::APValue::LValueBase>::getHashValue(
 211     const clang::APValue::LValueBase &Base) {
 212   return hash_value(Base);
 213 }
 214
 215 bool llvm::DenseMapInfo<clang::APValue::LValueBase>::isEqual(
 216     const clang::APValue::LValueBase &LHS,
 217     const clang::APValue::LValueBase &RHS) {
 218   return LHS == RHS;
 219 }
 220
 221 struct APValue::LV : LVBase {
 222   static const unsigned InlinePathSpace =
 223       (DataSize - sizeof(LVBase)) / sizeof(LValuePathEntry);
 224
 225   /// Path - The sequence of base classes, fields and array indices to follow to
 226   /// walk from Base to the subobject. When performing GCC-style folding, there
 227   /// may not be such a path.
 228   union {
 229     LValuePathEntry Path[InlinePathSpace];
 230     LValuePathEntry *PathPtr;
 231   };
 232
 233   LV() { PathLength = (unsigned)-1; }
 234   ~LV() { resizePath(0); }
 235
 236   void resizePath(unsigned Length) {
 237     if (Length == PathLength)
 238       return;
 239     if (hasPathPtr())
 240       delete [] PathPtr;
 241     PathLength = Length;
 242     if (hasPathPtr())
 243       PathPtr = new LValuePathEntry[Length];
 244   }
 245
 246   bool hasPath() const { return PathLength != (unsigned)-1; }
 247   bool hasPathPtr() const { return hasPath() && PathLength > InlinePathSpace; }
 248
 249   LValuePathEntry *getPath() { return hasPathPtr() ? PathPtr : Path; }
 250   const LValuePathEntry *getPath() const {
 251     return hasPathPtr() ? PathPtr : Path;
 252   }
 253 };
 254
 255 namespace {
 256   struct MemberPointerBase {
 257     llvm::PointerIntPair<const ValueDecl*, 1, bool> MemberAndIsDerivedMember;
 258     unsigned PathLength;
 259   };
 260 }
 261
 262 struct APValue::MemberPointerData : MemberPointerBase {
 263   static const unsigned InlinePathSpace =
 264       (DataSize - sizeof(MemberPointerBase)) / sizeof(const CXXRecordDecl*);
 265   typedef const CXXRecordDecl *PathElem;
 266   union {
 267     PathElem Path[InlinePathSpace];
 268     PathElem *PathPtr;
 269   };
 270
 271   MemberPointerData() { PathLength = 0; }
 272   ~MemberPointerData() { resizePath(0); }
 273
 274   void resizePath(unsigned Length) {
 275     if (Length == PathLength)
 276       return;
 277     if (hasPathPtr())
 278       delete [] PathPtr;
 279     PathLength = Length;
 280     if (hasPathPtr())
 281       PathPtr = new PathElem[Length];
 282   }
 283
 284   bool hasPathPtr() const { return PathLength > InlinePathSpace; }
 285
 286   PathElem *getPath() { return hasPathPtr() ? PathPtr : Path; }
 287   const PathElem *getPath() const {
 288     return hasPathPtr() ? PathPtr : Path;
 289   }
 290 };
 291
 292 // FIXME: Reduce the malloc traffic here.
 293
 294 APValue::Arr::Arr(unsigned NumElts, unsigned Size) :
 295   Elts(new APValue[NumElts + (NumElts != Size ? 1 : 0)]),
 296   NumElts(NumElts), ArrSize(Size) {}
 297 APValue::Arr::~Arr() { delete [] Elts; }
 298
 299 APValue::StructData::StructData(unsigned NumBases, unsigned NumFields) :
 300   Elts(new APValue[NumBases+NumFields]),
 301   NumBases(NumBases), NumFields(NumFields) {}
 302 APValue::StructData::~StructData() {
 303   delete [] Elts;
 304 }
 305
 306 APValue::UnionData::UnionData() : Field(nullptr), Value(new APValue) {}
 307 APValue::UnionData::~UnionData () {
 308   delete Value;
 309 }
 310
 311 APValue::APValue(const APValue &RHS) : Kind(None) {
 312   switch (RHS.getKind()) {
 313   case None:
 314   case Indeterminate:
 315     Kind = RHS.getKind();
 316     break;
 317   case Int:
 318     MakeInt();
 319     setInt(RHS.getInt());
 320     break;
 321   case Float:
 322     MakeFloat();
 323     setFloat(RHS.getFloat());
 324     break;
 325   case FixedPoint: {
 326     APFixedPoint FXCopy = RHS.getFixedPoint();
 327     MakeFixedPoint(std::move(FXCopy));
 328     break;
 329   }
 330   case Vector:
 331     MakeVector();
 332     setVector(((const Vec *)(const char *)&RHS.Data)->Elts,
 333               RHS.getVectorLength());
 334     break;
 335   case ComplexInt:
 336     MakeComplexInt();
 337     setComplexInt(RHS.getComplexIntReal(), RHS.getComplexIntImag());
 338     break;
 339   case ComplexFloat:
 340     MakeComplexFloat();
 341     setComplexFloat(RHS.getComplexFloatReal(), RHS.getComplexFloatImag());
 342     break;
 343   case LValue:
 344     MakeLValue();
 345     if (RHS.hasLValuePath())
 346       setLValue(RHS.getLValueBase(), RHS.getLValueOffset(), RHS.getLValuePath(),
 347                 RHS.isLValueOnePastTheEnd(), RHS.isNullPointer());
 348     else
 349       setLValue(RHS.getLValueBase(), RHS.getLValueOffset(), NoLValuePath(),
 350                 RHS.isNullPointer());
 351     break;
 352   case Array:
 353     MakeArray(RHS.getArrayInitializedElts(), RHS.getArraySize());
 354     for (unsigned I = 0, N = RHS.getArrayInitializedElts(); I != N; ++I)
 355       getArrayInitializedElt(I) = RHS.getArrayInitializedElt(I);
 356     if (RHS.hasArrayFiller())
 357       getArrayFiller() = RHS.getArrayFiller();
 358     break;
 359   case Struct:
 360     MakeStruct(RHS.getStructNumBases(), RHS.getStructNumFields());
 361     for (unsigned I = 0, N = RHS.getStructNumBases(); I != N; ++I)
 362       getStructBase(I) = RHS.getStructBase(I);
 363     for (unsigned I = 0, N = RHS.getStructNumFields(); I != N; ++I)
 364       getStructField(I) = RHS.getStructField(I);
 365     break;
 366   case Union:
 367     MakeUnion();
 368     setUnion(RHS.getUnionField(), RHS.getUnionValue());
 369     break;
 370   case MemberPointer:
 371     MakeMemberPointer(RHS.getMemberPointerDecl(),
 372                       RHS.isMemberPointerToDerivedMember(),
 373                       RHS.getMemberPointerPath());
 374     break;
 375   case AddrLabelDiff:
 376     MakeAddrLabelDiff();
 377     setAddrLabelDiff(RHS.getAddrLabelDiffLHS(), RHS.getAddrLabelDiffRHS());
 378     break;
 379   }
 380 }
 381
 382 APValue::APValue(APValue &&RHS) : Kind(RHS.Kind), Data(RHS.Data) {
 383   RHS.Kind = None;
 384 }
 385
 386 APValue &APValue::operator=(const APValue &RHS) {
 387   if (this != &RHS)
 388     *this = APValue(RHS);
 389   return *this;
 390 }
 391
 392 APValue &APValue::operator=(APValue &&RHS) {
 393   if (this != &RHS) {
 394     if (Kind != None && Kind != Indeterminate)
 395       DestroyDataAndMakeUninit();
 396     Kind = RHS.Kind;
 397     Data = RHS.Data;
 398     RHS.Kind = None;
 399   }
 400   return *this;
 401 }
 402
 403 void APValue::DestroyDataAndMakeUninit() {
 404   if (Kind == Int)
 405     ((APSInt *)(char *)&Data)->~APSInt();
 406   else if (Kind == Float)
 407     ((APFloat *)(char *)&Data)->~APFloat();
 408   else if (Kind == FixedPoint)
 409     ((APFixedPoint *)(char *)&Data)->~APFixedPoint();
 410   else if (Kind == Vector)
 411     ((Vec *)(char *)&Data)->~Vec();
 412   else if (Kind == ComplexInt)
 413     ((ComplexAPSInt *)(char *)&Data)->~ComplexAPSInt();
 414   else if (Kind == ComplexFloat)
 415     ((ComplexAPFloat *)(char *)&Data)->~ComplexAPFloat();
 416   else if (Kind == LValue)
 417     ((LV *)(char *)&Data)->~LV();
 418   else if (Kind == Array)
 419     ((Arr *)(char *)&Data)->~Arr();
 420   else if (Kind == Struct)
 421     ((StructData *)(char *)&Data)->~StructData();
 422   else if (Kind == Union)
 423     ((UnionData *)(char *)&Data)->~UnionData();
 424   else if (Kind == MemberPointer)
 425     ((MemberPointerData *)(char *)&Data)->~MemberPointerData();
 426   else if (Kind == AddrLabelDiff)
 427     ((AddrLabelDiffData *)(char *)&Data)->~AddrLabelDiffData();
 428   Kind = None;
 429 }
 430
 431 bool APValue::needsCleanup() const {
 432   switch (getKind()) {
 433   case None:
 434   case Indeterminate:
 435   case AddrLabelDiff:
 436     return false;
 437   case Struct:
 438   case Union:
 439   case Array:
 440   case Vector:
 441     return true;
 442   case Int:
 443     return getInt().needsCleanup();
 444   case Float:
 445     return getFloat().needsCleanup();
 446   case FixedPoint:
 447     return getFixedPoint().getValue().needsCleanup();
 448   case ComplexFloat:
 449     assert(getComplexFloatImag().needsCleanup() ==
 450                getComplexFloatReal().needsCleanup() &&
 451            "In _Complex float types, real and imaginary values always have the "
 452            "same size.");
 453     return getComplexFloatReal().needsCleanup();
 454   case ComplexInt:
 455     assert(getComplexIntImag().needsCleanup() ==
 456                getComplexIntReal().needsCleanup() &&
 457            "In _Complex int types, real and imaginary values must have the "
 458            "same size.");
 459     return getComplexIntReal().needsCleanup();
 460   case LValue:
 461     return reinterpret_cast<const LV *>(&Data)->hasPathPtr();
 462   case MemberPointer:
 463     return reinterpret_cast<const MemberPointerData *>(&Data)->hasPathPtr();
 464   }
 465   llvm_unreachable("Unknown APValue kind!");
 466 }
 467
 468 void APValue::swap(APValue &RHS) {
 469   std::swap(Kind, RHS.Kind);
 470   std::swap(Data, RHS.Data);
 471 }
 472
 473 /// Profile the value of an APInt, excluding its bit-width.
 474 static void profileIntValue(llvm::FoldingSetNodeID &ID, const llvm::APInt &V) {
 475   for (unsigned I = 0, N = V.getBitWidth(); I < N; I += 32)
 476     ID.AddInteger((uint32_t)V.extractBitsAsZExtValue(std::min(32u, N - I), I));
 477 }
 478
 479 void APValue::Profile(llvm::FoldingSetNodeID &ID) const {
 480   // Note that our profiling assumes that only APValues of the same type are
 481   // ever compared. As a result, we don't consider collisions that could only
 482   // happen if the types are different. (For example, structs with different
 483   // numbers of members could profile the same.)
 484
 485   ID.AddInteger(Kind);
 486
 487   switch (Kind) {
 488   case None:
 489   case Indeterminate:
 490     return;
 491
 492   case AddrLabelDiff:
 493     ID.AddPointer(getAddrLabelDiffLHS()->getLabel()->getCanonicalDecl());
 494     ID.AddPointer(getAddrLabelDiffRHS()->getLabel()->getCanonicalDecl());
 495     return;
 496
 497   case Struct:
 498     for (unsigned I = 0, N = getStructNumBases(); I != N; ++I)
 499       getStructBase(I).Profile(ID);
 500     for (unsigned I = 0, N = getStructNumFields(); I != N; ++I)
 501       getStructField(I).Profile(ID);
 502     return;
 503
 504   case Union:
 505     if (!getUnionField()) {
 506       ID.AddInteger(0);
 507       return;
 508     }
 509     ID.AddInteger(getUnionField()->getFieldIndex() + 1);
 510     getUnionValue().Profile(ID);
 511     return;
 512
 513   case Array: {
 514     if (getArraySize() == 0)
 515       return;
 516
 517     // The profile should not depend on whether the array is expanded or
 518     // not, but we don't want to profile the array filler many times for
 519     // a large array. So treat all equal trailing elements as the filler.
 520     // Elements are profiled in reverse order to support this, and the
 521     // first profiled element is followed by a count. For example:
 522     //
 523     //   ['a', 'c', 'x', 'x', 'x'] is profiled as
 524     //   [5, 'x', 3, 'c', 'a']
 525     llvm::FoldingSetNodeID FillerID;
 526     (hasArrayFiller() ? getArrayFiller()
 527                       : getArrayInitializedElt(getArrayInitializedElts() - 1))
 528         .Profile(FillerID);
 529     ID.AddNodeID(FillerID);
 530     unsigned NumFillers = getArraySize() - getArrayInitializedElts();
 531     unsigned N = getArrayInitializedElts();
 532
 533     // Count the number of elements equal to the last one. This loop ends
 534     // by adding an integer indicating the number of such elements, with
 535     // N set to the number of elements left to profile.
 536     while (true) {
 537       if (N == 0) {
 538         // All elements are fillers.
 539         assert(NumFillers == getArraySize());
 540         ID.AddInteger(NumFillers);
 541         break;
 542       }
 543
 544       // No need to check if the last element is equal to the last
 545       // element.
 546       if (N != getArraySize()) {
 547         llvm::FoldingSetNodeID ElemID;
 548         getArrayInitializedElt(N - 1).Profile(ElemID);
 549         if (ElemID != FillerID) {
 550           ID.AddInteger(NumFillers);
 551           ID.AddNodeID(ElemID);
 552           --N;
 553           break;
 554         }
 555       }
 556
 557       // This is a filler.
 558       ++NumFillers;
 559       --N;
 560     }
 561
 562     // Emit the remaining elements.
 563     for (; N != 0; --N)
 564       getArrayInitializedElt(N - 1).Profile(ID);
 565     return;
 566   }
 567
 568   case Vector:
 569     for (unsigned I = 0, N = getVectorLength(); I != N; ++I)
 570       getVectorElt(I).Profile(ID);
 571     return;
 572
 573   case Int:
 574     profileIntValue(ID, getInt());
 575     return;
 576
 577   case Float:
 578     profileIntValue(ID, getFloat().bitcastToAPInt());
 579     return;
 580
 581   case FixedPoint:
 582     profileIntValue(ID, getFixedPoint().getValue());
 583     return;
 584
 585   case ComplexFloat:
 586     profileIntValue(ID, getComplexFloatReal().bitcastToAPInt());
 587     profileIntValue(ID, getComplexFloatImag().bitcastToAPInt());
 588     return;
 589
 590   case ComplexInt:
 591     profileIntValue(ID, getComplexIntReal());
 592     profileIntValue(ID, getComplexIntImag());
 593     return;
 594
 595   case LValue:
 596     getLValueBase().Profile(ID);
 597     ID.AddInteger(getLValueOffset().getQuantity());
 598     ID.AddInteger((isNullPointer() ? 1 : 0) |
 599                   (isLValueOnePastTheEnd() ? 2 : 0) |
 600                   (hasLValuePath() ? 4 : 0));
 601     if (hasLValuePath()) {
 602       ID.AddInteger(getLValuePath().size());
 603       // For uniqueness, we only need to profile the entries corresponding
 604       // to union members, but we don't have the type here so we don't know
 605       // how to interpret the entries.
 606       for (LValuePathEntry E : getLValuePath())
 607         E.Profile(ID);
 608     }
 609     return;
 610
 611   case MemberPointer:
 612     ID.AddPointer(getMemberPointerDecl());
 613     ID.AddInteger(isMemberPointerToDerivedMember());
 614     for (const CXXRecordDecl *D : getMemberPointerPath())
 615       ID.AddPointer(D);
 616     return;
 617   }
 618
 619   llvm_unreachable("Unknown APValue kind!");
 620 }
 621
 622 static double GetApproxValue(const llvm::APFloat &F) {
 623   llvm::APFloat V = F;
 624   bool ignored;
 625   V.convert(llvm::APFloat::IEEEdouble(), llvm::APFloat::rmNearestTiesToEven,
 626             &ignored);
 627   return V.convertToDouble();
 628 }
 629
 630 static bool TryPrintAsStringLiteral(raw_ostream &Out,
 631                                     const PrintingPolicy &Policy,
 632                                     const ArrayType *ATy,
 633                                     ArrayRef<APValue> Inits) {
 634   if (Inits.empty())
 635     return false;
 636
 637   QualType Ty = ATy->getElementType();
 638   if (!Ty->isAnyCharacterType())
 639     return false;
 640
 641   // Nothing we can do about a sequence that is not null-terminated
 642   if (!Inits.back().isInt() || !Inits.back().getInt().isZero())
 643     return false;
 644
 645   Inits = Inits.drop_back();
 646
 647   llvm::SmallString<40> Buf;
 648   Buf.push_back('"');
 649
 650   // Better than printing a two-digit sequence of 10 integers.
 651   constexpr size_t MaxN = 36;
 652   StringRef Ellipsis;
 653   if (Inits.size() > MaxN && !Policy.EntireContentsOfLargeArray) {
 654     Ellipsis = "[...]";
 655     Inits =
 656         Inits.take_front(std::min(MaxN - Ellipsis.size() / 2, Inits.size()));
 657   }
 658
 659   for (auto &Val : Inits) {
 660     if (!Val.isInt())
 661       return false;
 662     int64_t Char64 = Val.getInt().getExtValue();
 663     if (!isASCII(Char64))
 664       return false; // Bye bye, see you in integers.
 665     auto Ch = static_cast<unsigned char>(Char64);
 666     // The diagnostic message is 'quoted'
 667     StringRef Escaped = escapeCStyle<EscapeChar::SingleAndDouble>(Ch);
 668     if (Escaped.empty()) {
 669       if (!isPrintable(Ch))
 670         return false;
 671       Buf.emplace_back(Ch);
 672     } else {
 673       Buf.append(Escaped);
 674     }
 675   }
 676
 677   Buf.append(Ellipsis);
 678   Buf.push_back('"');
 679
 680   if (Ty->isWideCharType())
 681     Out << 'L';
 682   else if (Ty->isChar8Type())
 683     Out << "u8";
 684   else if (Ty->isChar16Type())
 685     Out << 'u';
 686   else if (Ty->isChar32Type())
 687     Out << 'U';
 688
 689   Out << Buf;
 690   return true;
 691 }
 692
 693 void APValue::printPretty(raw_ostream &Out, const ASTContext &Ctx,
 694                           QualType Ty) const {
 695   printPretty(Out, Ctx.getPrintingPolicy(), Ty, &Ctx);
 696 }
 697
 698 void APValue::printPretty(raw_ostream &Out, const PrintingPolicy &Policy,
 699                           QualType Ty, const ASTContext *Ctx) const {
 700   // There are no objects of type 'void', but values of this type can be
 701   // returned from functions.
 702   if (Ty->isVoidType()) {
 703     Out << "void()";
 704     return;
 705   }
 706
 707   if (const auto *AT = Ty->getAs<AtomicType>())
 708     Ty = AT->getValueType();
 709
 710   switch (getKind()) {
 711   case APValue::None:
 712     Out << "<out of lifetime>";
 713     return;
 714   case APValue::Indeterminate:
 715     Out << "<uninitialized>";
 716     return;
 717   case APValue::Int:
 718     if (Ty->isBooleanType())
 719       Out << (getInt().getBoolValue() ? "true" : "false");
 720     else
 721       Out << getInt();
 722     return;
 723   case APValue::Float:
 724     Out << GetApproxValue(getFloat());
 725     return;
 726   case APValue::FixedPoint:
 727     Out << getFixedPoint();
 728     return;
 729   case APValue::Vector: {
 730     Out << '{';
 731     QualType ElemTy = Ty->castAs<VectorType>()->getElementType();
 732     getVectorElt(0).printPretty(Out, Policy, ElemTy, Ctx);
 733     for (unsigned i = 1; i != getVectorLength(); ++i) {
 734       Out << ", ";
 735       getVectorElt(i).printPretty(Out, Policy, ElemTy, Ctx);
 736     }
 737     Out << '}';
 738     return;
 739   }
 740   case APValue::ComplexInt:
 741     Out << getComplexIntReal() << "+" << getComplexIntImag() << "i";
 742     return;
 743   case APValue::ComplexFloat:
 744     Out << GetApproxValue(getComplexFloatReal()) << "+"
 745         << GetApproxValue(getComplexFloatImag()) << "i";
 746     return;
 747   case APValue::LValue: {
 748     bool IsReference = Ty->isReferenceType();
 749     QualType InnerTy
 750       = IsReference ? Ty.getNonReferenceType() : Ty->getPointeeType();
 751     if (InnerTy.isNull())
 752       InnerTy = Ty;
 753
 754     LValueBase Base = getLValueBase();
 755     if (!Base) {
 756       if (isNullPointer()) {
 757         Out << (Policy.Nullptr ? "nullptr" : "0");
 758       } else if (IsReference) {
 759         Out << "*(" << InnerTy.stream(Policy) << "*)"
 760             << getLValueOffset().getQuantity();
 761       } else {
 762         Out << "(" << Ty.stream(Policy) << ")"
 763             << getLValueOffset().getQuantity();
 764       }
 765       return;
 766     }
 767
 768     if (!hasLValuePath()) {
 769       // No lvalue path: just print the offset.
 770       CharUnits O = getLValueOffset();
 771       CharUnits S = Ctx ? Ctx->getTypeSizeInCharsIfKnown(InnerTy).value_or(
 772                               CharUnits::Zero())
 773                         : CharUnits::Zero();
 774       if (!O.isZero()) {
 775         if (IsReference)
 776           Out << "*(";
 777         if (S.isZero() || O % S) {
 778           Out << "(char*)";
 779           S = CharUnits::One();
 780         }
 781         Out << '&';
 782       } else if (!IsReference) {
 783         Out << '&';
 784       }
 785
 786       if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>())
 787         Out << *VD;
 788       else if (TypeInfoLValue TI = Base.dyn_cast<TypeInfoLValue>()) {
 789         TI.print(Out, Policy);
 790       } else if (DynamicAllocLValue DA = Base.dyn_cast<DynamicAllocLValue>()) {
 791         Out << "{*new "
 792             << Base.getDynamicAllocType().stream(Policy) << "#"
 793             << DA.getIndex() << "}";
 794       } else {
 795         assert(Base.get<const Expr *>() != nullptr &&
 796                "Expecting non-null Expr");
 797         Base.get<const Expr*>()->printPretty(Out, nullptr, Policy);
 798       }
 799
 800       if (!O.isZero()) {
 801         Out << " + " << (O / S);
 802         if (IsReference)
 803           Out << ')';
 804       }
 805       return;
 806     }
 807
 808     // We have an lvalue path. Print it out nicely.
 809     if (!IsReference)
 810       Out << '&';
 811     else if (isLValueOnePastTheEnd())
 812       Out << "*(&";
 813
 814     QualType ElemTy = Base.getType();
 815     if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>()) {
 816       Out << *VD;
 817     } else if (TypeInfoLValue TI = Base.dyn_cast<TypeInfoLValue>()) {
 818       TI.print(Out, Policy);
 819     } else if (DynamicAllocLValue DA = Base.dyn_cast<DynamicAllocLValue>()) {
 820       Out << "{*new " << Base.getDynamicAllocType().stream(Policy) << "#"
 821           << DA.getIndex() << "}";
 822     } else {
 823       const Expr *E = Base.get<const Expr*>();
 824       assert(E != nullptr && "Expecting non-null Expr");
 825       E->printPretty(Out, nullptr, Policy);
 826     }
 827
 828     ArrayRef<LValuePathEntry> Path = getLValuePath();
 829     const CXXRecordDecl *CastToBase = nullptr;
 830     for (unsigned I = 0, N = Path.size(); I != N; ++I) {
 831       if (ElemTy->isRecordType()) {
 832         // The lvalue refers to a class type, so the next path entry is a base
 833         // or member.
 834         const Decl *BaseOrMember = Path[I].getAsBaseOrMember().getPointer();
 835         if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(BaseOrMember)) {
 836           CastToBase = RD;
 837           // Leave ElemTy referring to the most-derived class. The actual type
 838           // doesn't matter except for array types.
 839         } else {
 840           const ValueDecl *VD = cast<ValueDecl>(BaseOrMember);
 841           Out << ".";
 842           if (CastToBase)
 843             Out << *CastToBase << "::";
 844           Out << *VD;
 845           ElemTy = VD->getType();
 846         }
 847       } else if (ElemTy->isAnyComplexType()) {
 848         // The lvalue refers to a complex type
 849         Out << (Path[I].getAsArrayIndex() == 0 ? ".real" : ".imag");
 850         ElemTy = ElemTy->castAs<ComplexType>()->getElementType();
 851       } else {
 852         // The lvalue must refer to an array.
 853         Out << '[' << Path[I].getAsArrayIndex() << ']';
 854         ElemTy = ElemTy->castAsArrayTypeUnsafe()->getElementType();
 855       }
 856     }
 857
 858     // Handle formatting of one-past-the-end lvalues.
 859     if (isLValueOnePastTheEnd()) {
 860       // FIXME: If CastToBase is non-0, we should prefix the output with
 861       // "(CastToBase*)".
 862       Out << " + 1";
 863       if (IsReference)
 864         Out << ')';
 865     }
 866     return;
 867   }
 868   case APValue::Array: {
 869     const ArrayType *AT = Ty->castAsArrayTypeUnsafe();
 870     unsigned N = getArrayInitializedElts();
 871     if (N != 0 && TryPrintAsStringLiteral(Out, Policy, AT,
 872                                           {&getArrayInitializedElt(0), N}))
 873       return;
 874     QualType ElemTy = AT->getElementType();
 875     Out << '{';
 876     unsigned I = 0;
 877     switch (N) {
 878     case 0:
 879       for (; I != N; ++I) {
 880         Out << ", ";
 881         if (I == 10 && !Policy.EntireContentsOfLargeArray) {
 882           Out << "...}";
 883           return;
 884         }
 885         [[fallthrough]];
 886       default:
 887         getArrayInitializedElt(I).printPretty(Out, Policy, ElemTy, Ctx);
 888       }
 889     }
 890     Out << '}';
 891     return;
 892   }
 893   case APValue::Struct: {
 894     Out << '{';
 895     const RecordDecl *RD = Ty->castAs<RecordType>()->getDecl();
 896     bool First = true;
 897     if (unsigned N = getStructNumBases()) {
 898       const CXXRecordDecl *CD = cast<CXXRecordDecl>(RD);
 899       CXXRecordDecl::base_class_const_iterator BI = CD->bases_begin();
 900       for (unsigned I = 0; I != N; ++I, ++BI) {
 901         assert(BI != CD->bases_end());
 902         if (!First)
 903           Out << ", ";
 904         getStructBase(I).printPretty(Out, Policy, BI->getType(), Ctx);
 905         First = false;
 906       }
 907     }
 908     for (const auto *FI : RD->fields()) {
 909       if (!First)
 910         Out << ", ";
 911       if (FI->isUnnamedBitField())
 912         continue;
 913       getStructField(FI->getFieldIndex()).
 914         printPretty(Out, Policy, FI->getType(), Ctx);
 915       First = false;
 916     }
 917     Out << '}';
 918     return;
 919   }
 920   case APValue::Union:
 921     Out << '{';
 922     if (const FieldDecl *FD = getUnionField()) {
 923       Out << "." << *FD << " = ";
 924       getUnionValue().printPretty(Out, Policy, FD->getType(), Ctx);
 925     }
 926     Out << '}';
 927     return;
 928   case APValue::MemberPointer:
 929     // FIXME: This is not enough to unambiguously identify the member in a
 930     // multiple-inheritance scenario.
 931     if (const ValueDecl *VD = getMemberPointerDecl()) {
 932       Out << '&' << *cast<CXXRecordDecl>(VD->getDeclContext()) << "::" << *VD;
 933       return;
 934     }
 935     Out << "0";
 936     return;
 937   case APValue::AddrLabelDiff:
 938     Out << "&&" << getAddrLabelDiffLHS()->getLabel()->getName();
 939     Out << " - ";
 940     Out << "&&" << getAddrLabelDiffRHS()->getLabel()->getName();
 941     return;
 942   }
 943   llvm_unreachable("Unknown APValue kind!");
 944 }
 945
 946 std::string APValue::getAsString(const ASTContext &Ctx, QualType Ty) const {
 947   std::string Result;
 948   llvm::raw_string_ostream Out(Result);
 949   printPretty(Out, Ctx, Ty);
 950   return Result;
 951 }
 952
 953 bool APValue::toIntegralConstant(APSInt &Result, QualType SrcTy,
 954                                  const ASTContext &Ctx) const {
 955   if (isInt()) {
 956     Result = getInt();
 957     return true;
 958   }
 959
 960   if (isLValue() && isNullPointer()) {
 961     Result = Ctx.MakeIntValue(Ctx.getTargetNullPointerValue(SrcTy), SrcTy);
 962     return true;
 963   }
 964
 965   if (isLValue() && !getLValueBase()) {
 966     Result = Ctx.MakeIntValue(getLValueOffset().getQuantity(), SrcTy);
 967     return true;
 968   }
 969
 970   return false;
 971 }
 972
 973 const APValue::LValueBase APValue::getLValueBase() const {
 974   assert(isLValue() && "Invalid accessor");
 975   return ((const LV *)(const void *)&Data)->Base;
 976 }
 977
 978 bool APValue::isLValueOnePastTheEnd() const {
 979   assert(isLValue() && "Invalid accessor");
 980   return ((const LV *)(const void *)&Data)->IsOnePastTheEnd;
 981 }
 982
 983 CharUnits &APValue::getLValueOffset() {
 984   assert(isLValue() && "Invalid accessor");
 985   return ((LV *)(void *)&Data)->Offset;
 986 }
 987
 988 bool APValue::hasLValuePath() const {
 989   assert(isLValue() && "Invalid accessor");
 990   return ((const LV *)(const char *)&Data)->hasPath();
 991 }
 992
 993 ArrayRef<APValue::LValuePathEntry> APValue::getLValuePath() const {
 994   assert(isLValue() && hasLValuePath() && "Invalid accessor");
 995   const LV &LVal = *((const LV *)(const char *)&Data);
 996   return llvm::ArrayRef(LVal.getPath(), LVal.PathLength);
 997 }
 998
 999 unsigned APValue::getLValueCallIndex() const {
1000   assert(isLValue() && "Invalid accessor");
1001   return ((const LV *)(const char *)&Data)->Base.getCallIndex();
1002 }
1003
1004 unsigned APValue::getLValueVersion() const {
1005   assert(isLValue() && "Invalid accessor");
1006   return ((const LV *)(const char *)&Data)->Base.getVersion();
1007 }
1008
1009 bool APValue::isNullPointer() const {
1010   assert(isLValue() && "Invalid usage");
1011   return ((const LV *)(const char *)&Data)->IsNullPtr;
1012 }
1013
1014 void APValue::setLValue(LValueBase B, const CharUnits &O, NoLValuePath,
1015                         bool IsNullPtr) {
1016   assert(isLValue() && "Invalid accessor");
1017   LV &LVal = *((LV *)(char *)&Data);
1018   LVal.Base = B;
1019   LVal.IsOnePastTheEnd = false;
1020   LVal.Offset = O;
1021   LVal.resizePath((unsigned)-1);
1022   LVal.IsNullPtr = IsNullPtr;
1023 }
1024
1025 MutableArrayRef<APValue::LValuePathEntry>
1026 APValue::setLValueUninit(LValueBase B, const CharUnits &O, unsigned Size,
1027                          bool IsOnePastTheEnd, bool IsNullPtr) {
1028   assert(isLValue() && "Invalid accessor");
1029   LV &LVal = *((LV *)(char *)&Data);
1030   LVal.Base = B;
1031   LVal.IsOnePastTheEnd = IsOnePastTheEnd;
1032   LVal.Offset = O;
1033   LVal.IsNullPtr = IsNullPtr;
1034   LVal.resizePath(Size);
1035   return {LVal.getPath(), Size};
1036 }
1037
1038 void APValue::setLValue(LValueBase B, const CharUnits &O,
1039                         ArrayRef<LValuePathEntry> Path, bool IsOnePastTheEnd,
1040                         bool IsNullPtr) {
1041   MutableArrayRef<APValue::LValuePathEntry> InternalPath =
1042       setLValueUninit(B, O, Path.size(), IsOnePastTheEnd, IsNullPtr);
1043   if (Path.size()) {
1044     memcpy(InternalPath.data(), Path.data(),
1045            Path.size() * sizeof(LValuePathEntry));
1046   }
1047 }
1048
1049 void APValue::setUnion(const FieldDecl *Field, const APValue &Value) {
1050   assert(isUnion() && "Invalid accessor");
1051   ((UnionData *)(char *)&Data)->Field =
1052       Field ? Field->getCanonicalDecl() : nullptr;
1053   *((UnionData *)(char *)&Data)->Value = Value;
1054 }
1055
1056 const ValueDecl *APValue::getMemberPointerDecl() const {
1057   assert(isMemberPointer() && "Invalid accessor");
1058   const MemberPointerData &MPD =
1059       *((const MemberPointerData *)(const char *)&Data);
1060   return MPD.MemberAndIsDerivedMember.getPointer();
1061 }
1062
1063 bool APValue::isMemberPointerToDerivedMember() const {
1064   assert(isMemberPointer() && "Invalid accessor");
1065   const MemberPointerData &MPD =
1066       *((const MemberPointerData *)(const char *)&Data);
1067   return MPD.MemberAndIsDerivedMember.getInt();
1068 }
1069
1070 ArrayRef<const CXXRecordDecl*> APValue::getMemberPointerPath() const {
1071   assert(isMemberPointer() && "Invalid accessor");
1072   const MemberPointerData &MPD =
1073       *((const MemberPointerData *)(const char *)&Data);
1074   return llvm::ArrayRef(MPD.getPath(), MPD.PathLength);
1075 }
1076
1077 void APValue::MakeLValue() {
1078   assert(isAbsent() && "Bad state change");
1079   static_assert(sizeof(LV) <= DataSize, "LV too big");
1080   new ((void *)(char *)&Data) LV();
1081   Kind = LValue;
1082 }
1083
1084 void APValue::MakeArray(unsigned InitElts, unsigned Size) {
1085   assert(isAbsent() && "Bad state change");
1086   new ((void *)(char *)&Data) Arr(InitElts, Size);
1087   Kind = Array;
1088 }
1089
1090 MutableArrayRef<APValue::LValuePathEntry>
1091 setLValueUninit(APValue::LValueBase B, const CharUnits &O, unsigned Size,
1092                 bool OnePastTheEnd, bool IsNullPtr);
1093
1094 MutableArrayRef<const CXXRecordDecl *>
1095 APValue::setMemberPointerUninit(const ValueDecl *Member, bool IsDerivedMember,
1096                                 unsigned Size) {
1097   assert(isAbsent() && "Bad state change");
1098   MemberPointerData *MPD = new ((void *)(char *)&Data) MemberPointerData;
1099   Kind = MemberPointer;
1100   MPD->MemberAndIsDerivedMember.setPointer(
1101       Member ? cast<ValueDecl>(Member->getCanonicalDecl()) : nullptr);
1102   MPD->MemberAndIsDerivedMember.setInt(IsDerivedMember);
1103   MPD->resizePath(Size);
1104   return {MPD->getPath(), MPD->PathLength};
1105 }
1106
1107 void APValue::MakeMemberPointer(const ValueDecl *Member, bool IsDerivedMember,
1108                                 ArrayRef<const CXXRecordDecl *> Path) {
1109   MutableArrayRef<const CXXRecordDecl *> InternalPath =
1110       setMemberPointerUninit(Member, IsDerivedMember, Path.size());
1111   for (unsigned I = 0; I != Path.size(); ++I)
1112     InternalPath[I] = Path[I]->getCanonicalDecl();
1113 }
1114
1115 LinkageInfo LinkageComputer::getLVForValue(const APValue &V,
1116                                            LVComputationKind computation) {
1117   LinkageInfo LV = LinkageInfo::external();
1118
1119   auto MergeLV = [&](LinkageInfo MergeLV) {
1120     LV.merge(MergeLV);
1121     return LV.getLinkage() == Linkage::Internal;
1122   };
1123   auto Merge = [&](const APValue &V) {
1124     return MergeLV(getLVForValue(V, computation));
1125   };
1126
1127   switch (V.getKind()) {
1128   case APValue::None:
1129   case APValue::Indeterminate:
1130   case APValue::Int:
1131   case APValue::Float:
1132   case APValue::FixedPoint:
1133   case APValue::ComplexInt:
1134   case APValue::ComplexFloat:
1135   case APValue::Vector:
1136     break;
1137
1138   case APValue::AddrLabelDiff:
1139     // Even for an inline function, it's not reasonable to treat a difference
1140     // between the addresses of labels as an external value.
1141     return LinkageInfo::internal();
1142
1143   case APValue::Struct: {
1144     for (unsigned I = 0, N = V.getStructNumBases(); I != N; ++I)
1145       if (Merge(V.getStructBase(I)))
1146         break;
1147     for (unsigned I = 0, N = V.getStructNumFields(); I != N; ++I)
1148       if (Merge(V.getStructField(I)))
1149         break;
1150     break;
1151   }
1152
1153   case APValue::Union:
1154     if (V.getUnionField())
1155       Merge(V.getUnionValue());
1156     break;
1157
1158   case APValue::Array: {
1159     for (unsigned I = 0, N = V.getArrayInitializedElts(); I != N; ++I)
1160       if (Merge(V.getArrayInitializedElt(I)))
1161         break;
1162     if (V.hasArrayFiller())
1163       Merge(V.getArrayFiller());
1164     break;
1165   }
1166
1167   case APValue::LValue: {
1168     if (!V.getLValueBase()) {
1169       // Null or absolute address: this is external.
1170     } else if (const auto *VD =
1171                    V.getLValueBase().dyn_cast<const ValueDecl *>()) {
1172       if (VD && MergeLV(getLVForDecl(VD, computation)))
1173         break;
1174     } else if (const auto TI = V.getLValueBase().dyn_cast<TypeInfoLValue>()) {
1175       if (MergeLV(getLVForType(*TI.getType(), computation)))
1176         break;
1177     } else if (const Expr *E = V.getLValueBase().dyn_cast<const Expr *>()) {
1178       // Almost all expression bases are internal. The exception is
1179       // lifetime-extended temporaries.
1180       // FIXME: These should be modeled as having the
1181       // LifetimeExtendedTemporaryDecl itself as the base.
1182       // FIXME: If we permit Objective-C object literals in template arguments,
1183       // they should not imply internal linkage.
1184       auto *MTE = dyn_cast<MaterializeTemporaryExpr>(E);
1185       if (!MTE || MTE->getStorageDuration() == SD_FullExpression)
1186         return LinkageInfo::internal();
1187       if (MergeLV(getLVForDecl(MTE->getExtendingDecl(), computation)))
1188         break;
1189     } else {
1190       assert(V.getLValueBase().is<DynamicAllocLValue>() &&
1191              "unexpected LValueBase kind");
1192       return LinkageInfo::internal();
1193     }
1194     // The lvalue path doesn't matter: pointers to all subobjects always have
1195     // the same visibility as pointers to the complete object.
1196     break;
1197   }
1198
1199   case APValue::MemberPointer:
1200     if (const NamedDecl *D = V.getMemberPointerDecl())
1201       MergeLV(getLVForDecl(D, computation));
1202     // Note that we could have a base-to-derived conversion here to a member of
1203     // a derived class with less linkage/visibility. That's covered by the
1204     // linkage and visibility of the value's type.
1205     break;
1206   }
1207
1208   return LV;
1209 }