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