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