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