Home | History | Annotate | Line # | Download | only in AST 
      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           clang::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     : ElemTy((const void *)ElemTy.getTypePtrOrNull()), Path(Path) {}
    160 
    161 QualType APValue::LValuePathSerializationHelper::getType() {
    162   return QualType::getFromOpaquePtr(ElemTy);
    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 (Kind != None && Kind != Indeterminate)
    394     DestroyDataAndMakeUninit();
    395   Kind = RHS.Kind;
    396   Data = RHS.Data;
    397   RHS.Kind = None;
    398   return *this;
    399 }
    400 
    401 void APValue::DestroyDataAndMakeUninit() {
    402   if (Kind == Int)
    403     ((APSInt *)(char *)&Data)->~APSInt();
    404   else if (Kind == Float)
    405     ((APFloat *)(char *)&Data)->~APFloat();
    406   else if (Kind == FixedPoint)
    407     ((APFixedPoint *)(char *)&Data)->~APFixedPoint();
    408   else if (Kind == Vector)
    409     ((Vec *)(char *)&Data)->~Vec();
    410   else if (Kind == ComplexInt)
    411     ((ComplexAPSInt *)(char *)&Data)->~ComplexAPSInt();
    412   else if (Kind == ComplexFloat)
    413     ((ComplexAPFloat *)(char *)&Data)->~ComplexAPFloat();
    414   else if (Kind == LValue)
    415     ((LV *)(char *)&Data)->~LV();
    416   else if (Kind == Array)
    417     ((Arr *)(char *)&Data)->~Arr();
    418   else if (Kind == Struct)
    419     ((StructData *)(char *)&Data)->~StructData();
    420   else if (Kind == Union)
    421     ((UnionData *)(char *)&Data)->~UnionData();
    422   else if (Kind == MemberPointer)
    423     ((MemberPointerData *)(char *)&Data)->~MemberPointerData();
    424   else if (Kind == AddrLabelDiff)
    425     ((AddrLabelDiffData *)(char *)&Data)->~AddrLabelDiffData();
    426   Kind = None;
    427 }
    428 
    429 bool APValue::needsCleanup() const {
    430   switch (getKind()) {
    431   case None:
    432   case Indeterminate:
    433   case AddrLabelDiff:
    434     return false;
    435   case Struct:
    436   case Union:
    437   case Array:
    438   case Vector:
    439     return true;
    440   case Int:
    441     return getInt().needsCleanup();
    442   case Float:
    443     return getFloat().needsCleanup();
    444   case FixedPoint:
    445     return getFixedPoint().getValue().needsCleanup();
    446   case ComplexFloat:
    447     assert(getComplexFloatImag().needsCleanup() ==
    448                getComplexFloatReal().needsCleanup() &&
    449            "In _Complex float types, real and imaginary values always have the "
    450            "same size.");
    451     return getComplexFloatReal().needsCleanup();
    452   case ComplexInt:
    453     assert(getComplexIntImag().needsCleanup() ==
    454                getComplexIntReal().needsCleanup() &&
    455            "In _Complex int types, real and imaginary values must have the "
    456            "same size.");
    457     return getComplexIntReal().needsCleanup();
    458   case LValue:
    459     return reinterpret_cast<const LV *>(&Data)->hasPathPtr();
    460   case MemberPointer:
    461     return reinterpret_cast<const MemberPointerData *>(&Data)->hasPathPtr();
    462   }
    463   llvm_unreachable("Unknown APValue kind!");
    464 }
    465 
    466 void APValue::swap(APValue &RHS) {
    467   std::swap(Kind, RHS.Kind);
    468   std::swap(Data, RHS.Data);
    469 }
    470 
    471 /// Profile the value of an APInt, excluding its bit-width.
    472 static void profileIntValue(llvm::FoldingSetNodeID &ID, const llvm::APInt &V) {
    473   for (unsigned I = 0, N = V.getBitWidth(); I < N; I += 32)
    474     ID.AddInteger((uint32_t)V.extractBitsAsZExtValue(std::min(32u, N - I), I));
    475 }
    476 
    477 void APValue::Profile(llvm::FoldingSetNodeID &ID) const {
    478   // Note that our profiling assumes that only APValues of the same type are
    479   // ever compared. As a result, we don't consider collisions that could only
    480   // happen if the types are different. (For example, structs with different
    481   // numbers of members could profile the same.)
    482 
    483   ID.AddInteger(Kind);
    484 
    485   switch (Kind) {
    486   case None:
    487   case Indeterminate:
    488     return;
    489 
    490   case AddrLabelDiff:
    491     ID.AddPointer(getAddrLabelDiffLHS()->getLabel()->getCanonicalDecl());
    492     ID.AddPointer(getAddrLabelDiffRHS()->getLabel()->getCanonicalDecl());
    493     return;
    494 
    495   case Struct:
    496     for (unsigned I = 0, N = getStructNumBases(); I != N; ++I)
    497       getStructBase(I).Profile(ID);
    498     for (unsigned I = 0, N = getStructNumFields(); I != N; ++I)
    499       getStructField(I).Profile(ID);
    500     return;
    501 
    502   case Union:
    503     if (!getUnionField()) {
    504       ID.AddInteger(0);
    505       return;
    506     }
    507     ID.AddInteger(getUnionField()->getFieldIndex() + 1);
    508     getUnionValue().Profile(ID);
    509     return;
    510 
    511   case Array: {
    512     if (getArraySize() == 0)
    513       return;
    514 
    515     // The profile should not depend on whether the array is expanded or
    516     // not, but we don't want to profile the array filler many times for
    517     // a large array. So treat all equal trailing elements as the filler.
    518     // Elements are profiled in reverse order to support this, and the
    519     // first profiled element is followed by a count. For example:
    520     //
    521     //   ['a', 'c', 'x', 'x', 'x'] is profiled as
    522     //   [5, 'x', 3, 'c', 'a']
    523     llvm::FoldingSetNodeID FillerID;
    524     (hasArrayFiller() ? getArrayFiller()
    525                       : getArrayInitializedElt(getArrayInitializedElts() - 1))
    526         .Profile(FillerID);
    527     ID.AddNodeID(FillerID);
    528     unsigned NumFillers = getArraySize() - getArrayInitializedElts();
    529     unsigned N = getArrayInitializedElts();
    530 
    531     // Count the number of elements equal to the last one. This loop ends
    532     // by adding an integer indicating the number of such elements, with
    533     // N set to the number of elements left to profile.
    534     while (true) {
    535       if (N == 0) {
    536         // All elements are fillers.
    537         assert(NumFillers == getArraySize());
    538         ID.AddInteger(NumFillers);
    539         break;
    540       }
    541 
    542       // No need to check if the last element is equal to the last
    543       // element.
    544       if (N != getArraySize()) {
    545         llvm::FoldingSetNodeID ElemID;
    546         getArrayInitializedElt(N - 1).Profile(ElemID);
    547         if (ElemID != FillerID) {
    548           ID.AddInteger(NumFillers);
    549           ID.AddNodeID(ElemID);
    550           --N;
    551           break;
    552         }
    553       }
    554 
    555       // This is a filler.
    556       ++NumFillers;
    557       --N;
    558     }
    559 
    560     // Emit the remaining elements.
    561     for (; N != 0; --N)
    562       getArrayInitializedElt(N - 1).Profile(ID);
    563     return;
    564   }
    565 
    566   case Vector:
    567     for (unsigned I = 0, N = getVectorLength(); I != N; ++I)
    568       getVectorElt(I).Profile(ID);
    569     return;
    570 
    571   case Int:
    572     profileIntValue(ID, getInt());
    573     return;
    574 
    575   case Float:
    576     profileIntValue(ID, getFloat().bitcastToAPInt());
    577     return;
    578 
    579   case FixedPoint:
    580     profileIntValue(ID, getFixedPoint().getValue());
    581     return;
    582 
    583   case ComplexFloat:
    584     profileIntValue(ID, getComplexFloatReal().bitcastToAPInt());
    585     profileIntValue(ID, getComplexFloatImag().bitcastToAPInt());
    586     return;
    587 
    588   case ComplexInt:
    589     profileIntValue(ID, getComplexIntReal());
    590     profileIntValue(ID, getComplexIntImag());
    591     return;
    592 
    593   case LValue:
    594     getLValueBase().Profile(ID);
    595     ID.AddInteger(getLValueOffset().getQuantity());
    596     ID.AddInteger((isNullPointer() ? 1 : 0) |
    597                   (isLValueOnePastTheEnd() ? 2 : 0) |
    598                   (hasLValuePath() ? 4 : 0));
    599     if (hasLValuePath()) {
    600       ID.AddInteger(getLValuePath().size());
    601       // For uniqueness, we only need to profile the entries corresponding
    602       // to union members, but we don't have the type here so we don't know
    603       // how to interpret the entries.
    604       for (LValuePathEntry E : getLValuePath())
    605         E.Profile(ID);
    606     }
    607     return;
    608 
    609   case MemberPointer:
    610     ID.AddPointer(getMemberPointerDecl());
    611     ID.AddInteger(isMemberPointerToDerivedMember());
    612     for (const CXXRecordDecl *D : getMemberPointerPath())
    613       ID.AddPointer(D);
    614     return;
    615   }
    616 
    617   llvm_unreachable("Unknown APValue kind!");
    618 }
    619 
    620 static double GetApproxValue(const llvm::APFloat &F) {
    621   llvm::APFloat V = F;
    622   bool ignored;
    623   V.convert(llvm::APFloat::IEEEdouble(), llvm::APFloat::rmNearestTiesToEven,
    624             &ignored);
    625   return V.convertToDouble();
    626 }
    627 
    628 void APValue::printPretty(raw_ostream &Out, const ASTContext &Ctx,
    629                           QualType Ty) const {
    630   printPretty(Out, Ctx.getPrintingPolicy(), Ty, &Ctx);
    631 }
    632 
    633 void APValue::printPretty(raw_ostream &Out, const PrintingPolicy &Policy,
    634                           QualType Ty, const ASTContext *Ctx) const {
    635   // There are no objects of type 'void', but values of this type can be
    636   // returned from functions.
    637   if (Ty->isVoidType()) {
    638     Out << "void()";
    639     return;
    640   }
    641 
    642   switch (getKind()) {
    643   case APValue::None:
    644     Out << "<out of lifetime>";
    645     return;
    646   case APValue::Indeterminate:
    647     Out << "<uninitialized>";
    648     return;
    649   case APValue::Int:
    650     if (Ty->isBooleanType())
    651       Out << (getInt().getBoolValue() ? "true" : "false");
    652     else
    653       Out << getInt();
    654     return;
    655   case APValue::Float:
    656     Out << GetApproxValue(getFloat());
    657     return;
    658   case APValue::FixedPoint:
    659     Out << getFixedPoint();
    660     return;
    661   case APValue::Vector: {
    662     Out << '{';
    663     QualType ElemTy = Ty->castAs<VectorType>()->getElementType();
    664     getVectorElt(0).printPretty(Out, Policy, ElemTy, Ctx);
    665     for (unsigned i = 1; i != getVectorLength(); ++i) {
    666       Out << ", ";
    667       getVectorElt(i).printPretty(Out, Policy, ElemTy, Ctx);
    668     }
    669     Out << '}';
    670     return;
    671   }
    672   case APValue::ComplexInt:
    673     Out << getComplexIntReal() << "+" << getComplexIntImag() << "i";
    674     return;
    675   case APValue::ComplexFloat:
    676     Out << GetApproxValue(getComplexFloatReal()) << "+"
    677         << GetApproxValue(getComplexFloatImag()) << "i";
    678     return;
    679   case APValue::LValue: {
    680     bool IsReference = Ty->isReferenceType();
    681     QualType InnerTy
    682       = IsReference ? Ty.getNonReferenceType() : Ty->getPointeeType();
    683     if (InnerTy.isNull())
    684       InnerTy = Ty;
    685 
    686     LValueBase Base = getLValueBase();
    687     if (!Base) {
    688       if (isNullPointer()) {
    689         Out << (Policy.Nullptr ? "nullptr" : "0");
    690       } else if (IsReference) {
    691         Out << "*(" << InnerTy.stream(Policy) << "*)"
    692             << getLValueOffset().getQuantity();
    693       } else {
    694         Out << "(" << Ty.stream(Policy) << ")"
    695             << getLValueOffset().getQuantity();
    696       }
    697       return;
    698     }
    699 
    700     if (!hasLValuePath()) {
    701       // No lvalue path: just print the offset.
    702       CharUnits O = getLValueOffset();
    703       CharUnits S = Ctx ? Ctx->getTypeSizeInChars(InnerTy) : CharUnits::Zero();
    704       if (!O.isZero()) {
    705         if (IsReference)
    706           Out << "*(";
    707         if (S.isZero() || O % S) {
    708           Out << "(char*)";
    709           S = CharUnits::One();
    710         }
    711         Out << '&';
    712       } else if (!IsReference) {
    713         Out << '&';
    714       }
    715 
    716       if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>())
    717         Out << *VD;
    718       else if (TypeInfoLValue TI = Base.dyn_cast<TypeInfoLValue>()) {
    719         TI.print(Out, Policy);
    720       } else if (DynamicAllocLValue DA = Base.dyn_cast<DynamicAllocLValue>()) {
    721         Out << "{*new "
    722             << Base.getDynamicAllocType().stream(Policy) << "#"
    723             << DA.getIndex() << "}";
    724       } else {
    725         assert(Base.get<const Expr *>() != nullptr &&
    726                "Expecting non-null Expr");
    727         Base.get<const Expr*>()->printPretty(Out, nullptr, Policy);
    728       }
    729 
    730       if (!O.isZero()) {
    731         Out << " + " << (O / S);
    732         if (IsReference)
    733           Out << ')';
    734       }
    735       return;
    736     }
    737 
    738     // We have an lvalue path. Print it out nicely.
    739     if (!IsReference)
    740       Out << '&';
    741     else if (isLValueOnePastTheEnd())
    742       Out << "*(&";
    743 
    744     QualType ElemTy = Base.getType();
    745     if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>()) {
    746       Out << *VD;
    747     } else if (TypeInfoLValue TI = Base.dyn_cast<TypeInfoLValue>()) {
    748       TI.print(Out, Policy);
    749     } else if (DynamicAllocLValue DA = Base.dyn_cast<DynamicAllocLValue>()) {
    750       Out << "{*new " << Base.getDynamicAllocType().stream(Policy) << "#"
    751           << DA.getIndex() << "}";
    752     } else {
    753       const Expr *E = Base.get<const Expr*>();
    754       assert(E != nullptr && "Expecting non-null Expr");
    755       E->printPretty(Out, nullptr, Policy);
    756     }
    757 
    758     ArrayRef<LValuePathEntry> Path = getLValuePath();
    759     const CXXRecordDecl *CastToBase = nullptr;
    760     for (unsigned I = 0, N = Path.size(); I != N; ++I) {
    761       if (ElemTy->isRecordType()) {
    762         // The lvalue refers to a class type, so the next path entry is a base
    763         // or member.
    764         const Decl *BaseOrMember = Path[I].getAsBaseOrMember().getPointer();
    765         if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(BaseOrMember)) {
    766           CastToBase = RD;
    767           // Leave ElemTy referring to the most-derived class. The actual type
    768           // doesn't matter except for array types.
    769         } else {
    770           const ValueDecl *VD = cast<ValueDecl>(BaseOrMember);
    771           Out << ".";
    772           if (CastToBase)
    773             Out << *CastToBase << "::";
    774           Out << *VD;
    775           ElemTy = VD->getType();
    776         }
    777       } else {
    778         // The lvalue must refer to an array.
    779         Out << '[' << Path[I].getAsArrayIndex() << ']';
    780         ElemTy = ElemTy->castAsArrayTypeUnsafe()->getElementType();
    781       }
    782     }
    783 
    784     // Handle formatting of one-past-the-end lvalues.
    785     if (isLValueOnePastTheEnd()) {
    786       // FIXME: If CastToBase is non-0, we should prefix the output with
    787       // "(CastToBase*)".
    788       Out << " + 1";
    789       if (IsReference)
    790         Out << ')';
    791     }
    792     return;
    793   }
    794   case APValue::Array: {
    795     const ArrayType *AT = Ty->castAsArrayTypeUnsafe();
    796     QualType ElemTy = AT->getElementType();
    797     Out << '{';
    798     if (unsigned N = getArrayInitializedElts()) {
    799       getArrayInitializedElt(0).printPretty(Out, Policy, ElemTy, Ctx);
    800       for (unsigned I = 1; I != N; ++I) {
    801         Out << ", ";
    802         if (I == 10) {
    803           // Avoid printing out the entire contents of large arrays.
    804           Out << "...";
    805           break;
    806         }
    807         getArrayInitializedElt(I).printPretty(Out, Policy, ElemTy, Ctx);
    808       }
    809     }
    810     Out << '}';
    811     return;
    812   }
    813   case APValue::Struct: {
    814     Out << '{';
    815     const RecordDecl *RD = Ty->castAs<RecordType>()->getDecl();
    816     bool First = true;
    817     if (unsigned N = getStructNumBases()) {
    818       const CXXRecordDecl *CD = cast<CXXRecordDecl>(RD);
    819       CXXRecordDecl::base_class_const_iterator BI = CD->bases_begin();
    820       for (unsigned I = 0; I != N; ++I, ++BI) {
    821         assert(BI != CD->bases_end());
    822         if (!First)
    823           Out << ", ";
    824         getStructBase(I).printPretty(Out, Policy, BI->getType(), Ctx);
    825         First = false;
    826       }
    827     }
    828     for (const auto *FI : RD->fields()) {
    829       if (!First)
    830         Out << ", ";
    831       if (FI->isUnnamedBitfield()) continue;
    832       getStructField(FI->getFieldIndex()).
    833         printPretty(Out, Policy, FI->getType(), Ctx);
    834       First = false;
    835     }
    836     Out << '}';
    837     return;
    838   }
    839   case APValue::Union:
    840     Out << '{';
    841     if (const FieldDecl *FD = getUnionField()) {
    842       Out << "." << *FD << " = ";
    843       getUnionValue().printPretty(Out, Policy, FD->getType(), Ctx);
    844     }
    845     Out << '}';
    846     return;
    847   case APValue::MemberPointer:
    848     // FIXME: This is not enough to unambiguously identify the member in a
    849     // multiple-inheritance scenario.
    850     if (const ValueDecl *VD = getMemberPointerDecl()) {
    851       Out << '&' << *cast<CXXRecordDecl>(VD->getDeclContext()) << "::" << *VD;
    852       return;
    853     }
    854     Out << "0";
    855     return;
    856   case APValue::AddrLabelDiff:
    857     Out << "&&" << getAddrLabelDiffLHS()->getLabel()->getName();
    858     Out << " - ";
    859     Out << "&&" << getAddrLabelDiffRHS()->getLabel()->getName();
    860     return;
    861   }
    862   llvm_unreachable("Unknown APValue kind!");
    863 }
    864 
    865 std::string APValue::getAsString(const ASTContext &Ctx, QualType Ty) const {
    866   std::string Result;
    867   llvm::raw_string_ostream Out(Result);
    868   printPretty(Out, Ctx, Ty);
    869   Out.flush();
    870   return Result;
    871 }
    872 
    873 bool APValue::toIntegralConstant(APSInt &Result, QualType SrcTy,
    874                                  const ASTContext &Ctx) const {
    875   if (isInt()) {
    876     Result = getInt();
    877     return true;
    878   }
    879 
    880   if (isLValue() && isNullPointer()) {
    881     Result = Ctx.MakeIntValue(Ctx.getTargetNullPointerValue(SrcTy), SrcTy);
    882     return true;
    883   }
    884 
    885   if (isLValue() && !getLValueBase()) {
    886     Result = Ctx.MakeIntValue(getLValueOffset().getQuantity(), SrcTy);
    887     return true;
    888   }
    889 
    890   return false;
    891 }
    892 
    893 const APValue::LValueBase APValue::getLValueBase() const {
    894   assert(isLValue() && "Invalid accessor");
    895   return ((const LV *)(const void *)&Data)->Base;
    896 }
    897 
    898 bool APValue::isLValueOnePastTheEnd() const {
    899   assert(isLValue() && "Invalid accessor");
    900   return ((const LV *)(const void *)&Data)->IsOnePastTheEnd;
    901 }
    902 
    903 CharUnits &APValue::getLValueOffset() {
    904   assert(isLValue() && "Invalid accessor");
    905   return ((LV *)(void *)&Data)->Offset;
    906 }
    907 
    908 bool APValue::hasLValuePath() const {
    909   assert(isLValue() && "Invalid accessor");
    910   return ((const LV *)(const char *)&Data)->hasPath();
    911 }
    912 
    913 ArrayRef<APValue::LValuePathEntry> APValue::getLValuePath() const {
    914   assert(isLValue() && hasLValuePath() && "Invalid accessor");
    915   const LV &LVal = *((const LV *)(const char *)&Data);
    916   return llvm::makeArrayRef(LVal.getPath(), LVal.PathLength);
    917 }
    918 
    919 unsigned APValue::getLValueCallIndex() const {
    920   assert(isLValue() && "Invalid accessor");
    921   return ((const LV *)(const char *)&Data)->Base.getCallIndex();
    922 }
    923 
    924 unsigned APValue::getLValueVersion() const {
    925   assert(isLValue() && "Invalid accessor");
    926   return ((const LV *)(const char *)&Data)->Base.getVersion();
    927 }
    928 
    929 bool APValue::isNullPointer() const {
    930   assert(isLValue() && "Invalid usage");
    931   return ((const LV *)(const char *)&Data)->IsNullPtr;
    932 }
    933 
    934 void APValue::setLValue(LValueBase B, const CharUnits &O, NoLValuePath,
    935                         bool IsNullPtr) {
    936   assert(isLValue() && "Invalid accessor");
    937   LV &LVal = *((LV *)(char *)&Data);
    938   LVal.Base = B;
    939   LVal.IsOnePastTheEnd = false;
    940   LVal.Offset = O;
    941   LVal.resizePath((unsigned)-1);
    942   LVal.IsNullPtr = IsNullPtr;
    943 }
    944 
    945 MutableArrayRef<APValue::LValuePathEntry>
    946 APValue::setLValueUninit(LValueBase B, const CharUnits &O, unsigned Size,
    947                          bool IsOnePastTheEnd, bool IsNullPtr) {
    948   assert(isLValue() && "Invalid accessor");
    949   LV &LVal = *((LV *)(char *)&Data);
    950   LVal.Base = B;
    951   LVal.IsOnePastTheEnd = IsOnePastTheEnd;
    952   LVal.Offset = O;
    953   LVal.IsNullPtr = IsNullPtr;
    954   LVal.resizePath(Size);
    955   return {LVal.getPath(), Size};
    956 }
    957 
    958 void APValue::setLValue(LValueBase B, const CharUnits &O,
    959                         ArrayRef<LValuePathEntry> Path, bool IsOnePastTheEnd,
    960                         bool IsNullPtr) {
    961   MutableArrayRef<APValue::LValuePathEntry> InternalPath =
    962       setLValueUninit(B, O, Path.size(), IsOnePastTheEnd, IsNullPtr);
    963   if (Path.size()) {
    964     memcpy(InternalPath.data(), Path.data(),
    965            Path.size() * sizeof(LValuePathEntry));
    966   }
    967 }
    968 
    969 void APValue::setUnion(const FieldDecl *Field, const APValue &Value) {
    970   assert(isUnion() && "Invalid accessor");
    971   ((UnionData *)(char *)&Data)->Field =
    972       Field ? Field->getCanonicalDecl() : nullptr;
    973   *((UnionData *)(char *)&Data)->Value = Value;
    974 }
    975 
    976 const ValueDecl *APValue::getMemberPointerDecl() const {
    977   assert(isMemberPointer() && "Invalid accessor");
    978   const MemberPointerData &MPD =
    979       *((const MemberPointerData *)(const char *)&Data);
    980   return MPD.MemberAndIsDerivedMember.getPointer();
    981 }
    982 
    983 bool APValue::isMemberPointerToDerivedMember() const {
    984   assert(isMemberPointer() && "Invalid accessor");
    985   const MemberPointerData &MPD =
    986       *((const MemberPointerData *)(const char *)&Data);
    987   return MPD.MemberAndIsDerivedMember.getInt();
    988 }
    989 
    990 ArrayRef<const CXXRecordDecl*> APValue::getMemberPointerPath() const {
    991   assert(isMemberPointer() && "Invalid accessor");
    992   const MemberPointerData &MPD =
    993       *((const MemberPointerData *)(const char *)&Data);
    994   return llvm::makeArrayRef(MPD.getPath(), MPD.PathLength);
    995 }
    996 
    997 void APValue::MakeLValue() {
    998   assert(isAbsent() && "Bad state change");
    999   static_assert(sizeof(LV) <= DataSize, "LV too big");
   1000   new ((void *)(char *)&Data) LV();
   1001   Kind = LValue;
   1002 }
   1003 
   1004 void APValue::MakeArray(unsigned InitElts, unsigned Size) {
   1005   assert(isAbsent() && "Bad state change");
   1006   new ((void *)(char *)&Data) Arr(InitElts, Size);
   1007   Kind = Array;
   1008 }
   1009 
   1010 MutableArrayRef<APValue::LValuePathEntry>
   1011 setLValueUninit(APValue::LValueBase B, const CharUnits &O, unsigned Size,
   1012                 bool OnePastTheEnd, bool IsNullPtr);
   1013 
   1014 MutableArrayRef<const CXXRecordDecl *>
   1015 APValue::setMemberPointerUninit(const ValueDecl *Member, bool IsDerivedMember,
   1016                                 unsigned Size) {
   1017   assert(isAbsent() && "Bad state change");
   1018   MemberPointerData *MPD = new ((void *)(char *)&Data) MemberPointerData;
   1019   Kind = MemberPointer;
   1020   MPD->MemberAndIsDerivedMember.setPointer(
   1021       Member ? cast<ValueDecl>(Member->getCanonicalDecl()) : nullptr);
   1022   MPD->MemberAndIsDerivedMember.setInt(IsDerivedMember);
   1023   MPD->resizePath(Size);
   1024   return {MPD->getPath(), MPD->PathLength};
   1025 }
   1026 
   1027 void APValue::MakeMemberPointer(const ValueDecl *Member, bool IsDerivedMember,
   1028                                 ArrayRef<const CXXRecordDecl *> Path) {
   1029   MutableArrayRef<const CXXRecordDecl *> InternalPath =
   1030       setMemberPointerUninit(Member, IsDerivedMember, Path.size());
   1031   for (unsigned I = 0; I != Path.size(); ++I)
   1032     InternalPath[I] = Path[I]->getCanonicalDecl();
   1033 }
   1034 
   1035 LinkageInfo LinkageComputer::getLVForValue(const APValue &V,
   1036                                            LVComputationKind computation) {
   1037   LinkageInfo LV = LinkageInfo::external();
   1038 
   1039   auto MergeLV = [&](LinkageInfo MergeLV) {
   1040     LV.merge(MergeLV);
   1041     return LV.getLinkage() == InternalLinkage;
   1042   };
   1043   auto Merge = [&](const APValue &V) {
   1044     return MergeLV(getLVForValue(V, computation));
   1045   };
   1046 
   1047   switch (V.getKind()) {
   1048   case APValue::None:
   1049   case APValue::Indeterminate:
   1050   case APValue::Int:
   1051   case APValue::Float:
   1052   case APValue::FixedPoint:
   1053   case APValue::ComplexInt:
   1054   case APValue::ComplexFloat:
   1055   case APValue::Vector:
   1056     break;
   1057 
   1058   case APValue::AddrLabelDiff:
   1059     // Even for an inline function, it's not reasonable to treat a difference
   1060     // between the addresses of labels as an external value.
   1061     return LinkageInfo::internal();
   1062 
   1063   case APValue::Struct: {
   1064     for (unsigned I = 0, N = V.getStructNumBases(); I != N; ++I)
   1065       if (Merge(V.getStructBase(I)))
   1066         break;
   1067     for (unsigned I = 0, N = V.getStructNumFields(); I != N; ++I)
   1068       if (Merge(V.getStructField(I)))
   1069         break;
   1070     break;
   1071   }
   1072 
   1073   case APValue::Union:
   1074     if (V.getUnionField())
   1075       Merge(V.getUnionValue());
   1076     break;
   1077 
   1078   case APValue::Array: {
   1079     for (unsigned I = 0, N = V.getArrayInitializedElts(); I != N; ++I)
   1080       if (Merge(V.getArrayInitializedElt(I)))
   1081         break;
   1082     if (V.hasArrayFiller())
   1083       Merge(V.getArrayFiller());
   1084     break;
   1085   }
   1086 
   1087   case APValue::LValue: {
   1088     if (!V.getLValueBase()) {
   1089       // Null or absolute address: this is external.
   1090     } else if (const auto *VD =
   1091                    V.getLValueBase().dyn_cast<const ValueDecl *>()) {
   1092       if (VD && MergeLV(getLVForDecl(VD, computation)))
   1093         break;
   1094     } else if (const auto TI = V.getLValueBase().dyn_cast<TypeInfoLValue>()) {
   1095       if (MergeLV(getLVForType(*TI.getType(), computation)))
   1096         break;
   1097     } else if (const Expr *E = V.getLValueBase().dyn_cast<const Expr *>()) {
   1098       // Almost all expression bases are internal. The exception is
   1099       // lifetime-extended temporaries.
   1100       // FIXME: These should be modeled as having the
   1101       // LifetimeExtendedTemporaryDecl itself as the base.
   1102       // FIXME: If we permit Objective-C object literals in template arguments,
   1103       // they should not imply internal linkage.
   1104       auto *MTE = dyn_cast<MaterializeTemporaryExpr>(E);
   1105       if (!MTE || MTE->getStorageDuration() == SD_FullExpression)
   1106         return LinkageInfo::internal();
   1107       if (MergeLV(getLVForDecl(MTE->getExtendingDecl(), computation)))
   1108         break;
   1109     } else {
   1110       assert(V.getLValueBase().is<DynamicAllocLValue>() &&
   1111              "unexpected LValueBase kind");
   1112       return LinkageInfo::internal();
   1113     }
   1114     // The lvalue path doesn't matter: pointers to all subobjects always have
   1115     // the same visibility as pointers to the complete object.
   1116     break;
   1117   }
   1118 
   1119   case APValue::MemberPointer:
   1120     if (const NamedDecl *D = V.getMemberPointerDecl())
   1121       MergeLV(getLVForDecl(D, computation));
   1122     // Note that we could have a base-to-derived conversion here to a member of
   1123     // a derived class with less linkage/visibility. That's covered by the
   1124     // linkage and visibility of the value's type.
   1125     break;
   1126   }
   1127 
   1128   return LV;
   1129 }
   1130