xref: /freebsd/contrib/llvm-project/clang/lib/AST/APValue.cpp (revision d4eeb02986980bf33dd56c41ceb9fc5f180c0d47) 
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->getTypeSizeInCharsIfKnown(InnerTy).getValueOr(
704                               CharUnits::Zero())
705                         : CharUnits::Zero();
706       if (!O.isZero()) {
707         if (IsReference)
708           Out << "*(";
709         if (S.isZero() || O % S) {
710           Out << "(char*)";
711           S = CharUnits::One();
712         }
713         Out << '&';
714       } else if (!IsReference) {
715         Out << '&';
716       }
717 
718       if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>())
719         Out << *VD;
720       else if (TypeInfoLValue TI = Base.dyn_cast<TypeInfoLValue>()) {
721         TI.print(Out, Policy);
722       } else if (DynamicAllocLValue DA = Base.dyn_cast<DynamicAllocLValue>()) {
723         Out << "{*new "
724             << Base.getDynamicAllocType().stream(Policy) << "#"
725             << DA.getIndex() << "}";
726       } else {
727         assert(Base.get<const Expr *>() != nullptr &&
728                "Expecting non-null Expr");
729         Base.get<const Expr*>()->printPretty(Out, nullptr, Policy);
730       }
731 
732       if (!O.isZero()) {
733         Out << " + " << (O / S);
734         if (IsReference)
735           Out << ')';
736       }
737       return;
738     }
739 
740     // We have an lvalue path. Print it out nicely.
741     if (!IsReference)
742       Out << '&';
743     else if (isLValueOnePastTheEnd())
744       Out << "*(&";
745 
746     QualType ElemTy = Base.getType();
747     if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>()) {
748       Out << *VD;
749     } else if (TypeInfoLValue TI = Base.dyn_cast<TypeInfoLValue>()) {
750       TI.print(Out, Policy);
751     } else if (DynamicAllocLValue DA = Base.dyn_cast<DynamicAllocLValue>()) {
752       Out << "{*new " << Base.getDynamicAllocType().stream(Policy) << "#"
753           << DA.getIndex() << "}";
754     } else {
755       const Expr *E = Base.get<const Expr*>();
756       assert(E != nullptr && "Expecting non-null Expr");
757       E->printPretty(Out, nullptr, Policy);
758     }
759 
760     ArrayRef<LValuePathEntry> Path = getLValuePath();
761     const CXXRecordDecl *CastToBase = nullptr;
762     for (unsigned I = 0, N = Path.size(); I != N; ++I) {
763       if (ElemTy->isRecordType()) {
764         // The lvalue refers to a class type, so the next path entry is a base
765         // or member.
766         const Decl *BaseOrMember = Path[I].getAsBaseOrMember().getPointer();
767         if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(BaseOrMember)) {
768           CastToBase = RD;
769           // Leave ElemTy referring to the most-derived class. The actual type
770           // doesn't matter except for array types.
771         } else {
772           const ValueDecl *VD = cast<ValueDecl>(BaseOrMember);
773           Out << ".";
774           if (CastToBase)
775             Out << *CastToBase << "::";
776           Out << *VD;
777           ElemTy = VD->getType();
778         }
779       } else {
780         // The lvalue must refer to an array.
781         Out << '[' << Path[I].getAsArrayIndex() << ']';
782         ElemTy = ElemTy->castAsArrayTypeUnsafe()->getElementType();
783       }
784     }
785 
786     // Handle formatting of one-past-the-end lvalues.
787     if (isLValueOnePastTheEnd()) {
788       // FIXME: If CastToBase is non-0, we should prefix the output with
789       // "(CastToBase*)".
790       Out << " + 1";
791       if (IsReference)
792         Out << ')';
793     }
794     return;
795   }
796   case APValue::Array: {
797     const ArrayType *AT = Ty->castAsArrayTypeUnsafe();
798     QualType ElemTy = AT->getElementType();
799     Out << '{';
800     if (unsigned N = getArrayInitializedElts()) {
801       getArrayInitializedElt(0).printPretty(Out, Policy, ElemTy, Ctx);
802       for (unsigned I = 1; I != N; ++I) {
803         Out << ", ";
804         if (I == 10) {
805           // Avoid printing out the entire contents of large arrays.
806           Out << "...";
807           break;
808         }
809         getArrayInitializedElt(I).printPretty(Out, Policy, ElemTy, Ctx);
810       }
811     }
812     Out << '}';
813     return;
814   }
815   case APValue::Struct: {
816     Out << '{';
817     const RecordDecl *RD = Ty->castAs<RecordType>()->getDecl();
818     bool First = true;
819     if (unsigned N = getStructNumBases()) {
820       const CXXRecordDecl *CD = cast<CXXRecordDecl>(RD);
821       CXXRecordDecl::base_class_const_iterator BI = CD->bases_begin();
822       for (unsigned I = 0; I != N; ++I, ++BI) {
823         assert(BI != CD->bases_end());
824         if (!First)
825           Out << ", ";
826         getStructBase(I).printPretty(Out, Policy, BI->getType(), Ctx);
827         First = false;
828       }
829     }
830     for (const auto *FI : RD->fields()) {
831       if (!First)
832         Out << ", ";
833       if (FI->isUnnamedBitfield()) continue;
834       getStructField(FI->getFieldIndex()).
835         printPretty(Out, Policy, FI->getType(), Ctx);
836       First = false;
837     }
838     Out << '}';
839     return;
840   }
841   case APValue::Union:
842     Out << '{';
843     if (const FieldDecl *FD = getUnionField()) {
844       Out << "." << *FD << " = ";
845       getUnionValue().printPretty(Out, Policy, FD->getType(), Ctx);
846     }
847     Out << '}';
848     return;
849   case APValue::MemberPointer:
850     // FIXME: This is not enough to unambiguously identify the member in a
851     // multiple-inheritance scenario.
852     if (const ValueDecl *VD = getMemberPointerDecl()) {
853       Out << '&' << *cast<CXXRecordDecl>(VD->getDeclContext()) << "::" << *VD;
854       return;
855     }
856     Out << "0";
857     return;
858   case APValue::AddrLabelDiff:
859     Out << "&&" << getAddrLabelDiffLHS()->getLabel()->getName();
860     Out << " - ";
861     Out << "&&" << getAddrLabelDiffRHS()->getLabel()->getName();
862     return;
863   }
864   llvm_unreachable("Unknown APValue kind!");
865 }
866 
867 std::string APValue::getAsString(const ASTContext &Ctx, QualType Ty) const {
868   std::string Result;
869   llvm::raw_string_ostream Out(Result);
870   printPretty(Out, Ctx, Ty);
871   Out.flush();
872   return Result;
873 }
874 
875 bool APValue::toIntegralConstant(APSInt &Result, QualType SrcTy,
876                                  const ASTContext &Ctx) const {
877   if (isInt()) {
878     Result = getInt();
879     return true;
880   }
881 
882   if (isLValue() && isNullPointer()) {
883     Result = Ctx.MakeIntValue(Ctx.getTargetNullPointerValue(SrcTy), SrcTy);
884     return true;
885   }
886 
887   if (isLValue() && !getLValueBase()) {
888     Result = Ctx.MakeIntValue(getLValueOffset().getQuantity(), SrcTy);
889     return true;
890   }
891 
892   return false;
893 }
894 
895 const APValue::LValueBase APValue::getLValueBase() const {
896   assert(isLValue() && "Invalid accessor");
897   return ((const LV *)(const void *)&Data)->Base;
898 }
899 
900 bool APValue::isLValueOnePastTheEnd() const {
901   assert(isLValue() && "Invalid accessor");
902   return ((const LV *)(const void *)&Data)->IsOnePastTheEnd;
903 }
904 
905 CharUnits &APValue::getLValueOffset() {
906   assert(isLValue() && "Invalid accessor");
907   return ((LV *)(void *)&Data)->Offset;
908 }
909 
910 bool APValue::hasLValuePath() const {
911   assert(isLValue() && "Invalid accessor");
912   return ((const LV *)(const char *)&Data)->hasPath();
913 }
914 
915 ArrayRef<APValue::LValuePathEntry> APValue::getLValuePath() const {
916   assert(isLValue() && hasLValuePath() && "Invalid accessor");
917   const LV &LVal = *((const LV *)(const char *)&Data);
918   return llvm::makeArrayRef(LVal.getPath(), LVal.PathLength);
919 }
920 
921 unsigned APValue::getLValueCallIndex() const {
922   assert(isLValue() && "Invalid accessor");
923   return ((const LV *)(const char *)&Data)->Base.getCallIndex();
924 }
925 
926 unsigned APValue::getLValueVersion() const {
927   assert(isLValue() && "Invalid accessor");
928   return ((const LV *)(const char *)&Data)->Base.getVersion();
929 }
930 
931 bool APValue::isNullPointer() const {
932   assert(isLValue() && "Invalid usage");
933   return ((const LV *)(const char *)&Data)->IsNullPtr;
934 }
935 
936 void APValue::setLValue(LValueBase B, const CharUnits &O, NoLValuePath,
937                         bool IsNullPtr) {
938   assert(isLValue() && "Invalid accessor");
939   LV &LVal = *((LV *)(char *)&Data);
940   LVal.Base = B;
941   LVal.IsOnePastTheEnd = false;
942   LVal.Offset = O;
943   LVal.resizePath((unsigned)-1);
944   LVal.IsNullPtr = IsNullPtr;
945 }
946 
947 MutableArrayRef<APValue::LValuePathEntry>
948 APValue::setLValueUninit(LValueBase B, const CharUnits &O, unsigned Size,
949                          bool IsOnePastTheEnd, bool IsNullPtr) {
950   assert(isLValue() && "Invalid accessor");
951   LV &LVal = *((LV *)(char *)&Data);
952   LVal.Base = B;
953   LVal.IsOnePastTheEnd = IsOnePastTheEnd;
954   LVal.Offset = O;
955   LVal.IsNullPtr = IsNullPtr;
956   LVal.resizePath(Size);
957   return {LVal.getPath(), Size};
958 }
959 
960 void APValue::setLValue(LValueBase B, const CharUnits &O,
961                         ArrayRef<LValuePathEntry> Path, bool IsOnePastTheEnd,
962                         bool IsNullPtr) {
963   MutableArrayRef<APValue::LValuePathEntry> InternalPath =
964       setLValueUninit(B, O, Path.size(), IsOnePastTheEnd, IsNullPtr);
965   if (Path.size()) {
966     memcpy(InternalPath.data(), Path.data(),
967            Path.size() * sizeof(LValuePathEntry));
968   }
969 }
970 
971 void APValue::setUnion(const FieldDecl *Field, const APValue &Value) {
972   assert(isUnion() && "Invalid accessor");
973   ((UnionData *)(char *)&Data)->Field =
974       Field ? Field->getCanonicalDecl() : nullptr;
975   *((UnionData *)(char *)&Data)->Value = Value;
976 }
977 
978 const ValueDecl *APValue::getMemberPointerDecl() const {
979   assert(isMemberPointer() && "Invalid accessor");
980   const MemberPointerData &MPD =
981       *((const MemberPointerData *)(const char *)&Data);
982   return MPD.MemberAndIsDerivedMember.getPointer();
983 }
984 
985 bool APValue::isMemberPointerToDerivedMember() const {
986   assert(isMemberPointer() && "Invalid accessor");
987   const MemberPointerData &MPD =
988       *((const MemberPointerData *)(const char *)&Data);
989   return MPD.MemberAndIsDerivedMember.getInt();
990 }
991 
992 ArrayRef<const CXXRecordDecl*> APValue::getMemberPointerPath() const {
993   assert(isMemberPointer() && "Invalid accessor");
994   const MemberPointerData &MPD =
995       *((const MemberPointerData *)(const char *)&Data);
996   return llvm::makeArrayRef(MPD.getPath(), MPD.PathLength);
997 }
998 
999 void APValue::MakeLValue() {
1000   assert(isAbsent() && "Bad state change");
1001   static_assert(sizeof(LV) <= DataSize, "LV too big");
1002   new ((void *)(char *)&Data) LV();
1003   Kind = LValue;
1004 }
1005 
1006 void APValue::MakeArray(unsigned InitElts, unsigned Size) {
1007   assert(isAbsent() && "Bad state change");
1008   new ((void *)(char *)&Data) Arr(InitElts, Size);
1009   Kind = Array;
1010 }
1011 
1012 MutableArrayRef<APValue::LValuePathEntry>
1013 setLValueUninit(APValue::LValueBase B, const CharUnits &O, unsigned Size,
1014                 bool OnePastTheEnd, bool IsNullPtr);
1015 
1016 MutableArrayRef<const CXXRecordDecl *>
1017 APValue::setMemberPointerUninit(const ValueDecl *Member, bool IsDerivedMember,
1018                                 unsigned Size) {
1019   assert(isAbsent() && "Bad state change");
1020   MemberPointerData *MPD = new ((void *)(char *)&Data) MemberPointerData;
1021   Kind = MemberPointer;
1022   MPD->MemberAndIsDerivedMember.setPointer(
1023       Member ? cast<ValueDecl>(Member->getCanonicalDecl()) : nullptr);
1024   MPD->MemberAndIsDerivedMember.setInt(IsDerivedMember);
1025   MPD->resizePath(Size);
1026   return {MPD->getPath(), MPD->PathLength};
1027 }
1028 
1029 void APValue::MakeMemberPointer(const ValueDecl *Member, bool IsDerivedMember,
1030                                 ArrayRef<const CXXRecordDecl *> Path) {
1031   MutableArrayRef<const CXXRecordDecl *> InternalPath =
1032       setMemberPointerUninit(Member, IsDerivedMember, Path.size());
1033   for (unsigned I = 0; I != Path.size(); ++I)
1034     InternalPath[I] = Path[I]->getCanonicalDecl();
1035 }
1036 
1037 LinkageInfo LinkageComputer::getLVForValue(const APValue &V,
1038                                            LVComputationKind computation) {
1039   LinkageInfo LV = LinkageInfo::external();
1040 
1041   auto MergeLV = [&](LinkageInfo MergeLV) {
1042     LV.merge(MergeLV);
1043     return LV.getLinkage() == InternalLinkage;
1044   };
1045   auto Merge = [&](const APValue &V) {
1046     return MergeLV(getLVForValue(V, computation));
1047   };
1048 
1049   switch (V.getKind()) {
1050   case APValue::None:
1051   case APValue::Indeterminate:
1052   case APValue::Int:
1053   case APValue::Float:
1054   case APValue::FixedPoint:
1055   case APValue::ComplexInt:
1056   case APValue::ComplexFloat:
1057   case APValue::Vector:
1058     break;
1059 
1060   case APValue::AddrLabelDiff:
1061     // Even for an inline function, it's not reasonable to treat a difference
1062     // between the addresses of labels as an external value.
1063     return LinkageInfo::internal();
1064 
1065   case APValue::Struct: {
1066     for (unsigned I = 0, N = V.getStructNumBases(); I != N; ++I)
1067       if (Merge(V.getStructBase(I)))
1068         break;
1069     for (unsigned I = 0, N = V.getStructNumFields(); I != N; ++I)
1070       if (Merge(V.getStructField(I)))
1071         break;
1072     break;
1073   }
1074 
1075   case APValue::Union:
1076     if (V.getUnionField())
1077       Merge(V.getUnionValue());
1078     break;
1079 
1080   case APValue::Array: {
1081     for (unsigned I = 0, N = V.getArrayInitializedElts(); I != N; ++I)
1082       if (Merge(V.getArrayInitializedElt(I)))
1083         break;
1084     if (V.hasArrayFiller())
1085       Merge(V.getArrayFiller());
1086     break;
1087   }
1088 
1089   case APValue::LValue: {
1090     if (!V.getLValueBase()) {
1091       // Null or absolute address: this is external.
1092     } else if (const auto *VD =
1093                    V.getLValueBase().dyn_cast<const ValueDecl *>()) {
1094       if (VD && MergeLV(getLVForDecl(VD, computation)))
1095         break;
1096     } else if (const auto TI = V.getLValueBase().dyn_cast<TypeInfoLValue>()) {
1097       if (MergeLV(getLVForType(*TI.getType(), computation)))
1098         break;
1099     } else if (const Expr *E = V.getLValueBase().dyn_cast<const Expr *>()) {
1100       // Almost all expression bases are internal. The exception is
1101       // lifetime-extended temporaries.
1102       // FIXME: These should be modeled as having the
1103       // LifetimeExtendedTemporaryDecl itself as the base.
1104       // FIXME: If we permit Objective-C object literals in template arguments,
1105       // they should not imply internal linkage.
1106       auto *MTE = dyn_cast<MaterializeTemporaryExpr>(E);
1107       if (!MTE || MTE->getStorageDuration() == SD_FullExpression)
1108         return LinkageInfo::internal();
1109       if (MergeLV(getLVForDecl(MTE->getExtendingDecl(), computation)))
1110         break;
1111     } else {
1112       assert(V.getLValueBase().is<DynamicAllocLValue>() &&
1113              "unexpected LValueBase kind");
1114       return LinkageInfo::internal();
1115     }
1116     // The lvalue path doesn't matter: pointers to all subobjects always have
1117     // the same visibility as pointers to the complete object.
1118     break;
1119   }
1120 
1121   case APValue::MemberPointer:
1122     if (const NamedDecl *D = V.getMemberPointerDecl())
1123       MergeLV(getLVForDecl(D, computation));
1124     // Note that we could have a base-to-derived conversion here to a member of
1125     // a derived class with less linkage/visibility. That's covered by the
1126     // linkage and visibility of the value's type.
1127     break;
1128   }
1129 
1130   return LV;
1131 }
1132