xref: /llvm-project/clang/lib/AST/APValue.cpp (revision e04ba2bc052f20fe745894b24b0f9b335db5abbc) 
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 "clang/AST/ASTContext.h"
15 #include "clang/AST/CharUnits.h"
16 #include "clang/AST/DeclCXX.h"
17 #include "clang/AST/Expr.h"
18 #include "clang/AST/Type.h"
19 #include "llvm/Support/ErrorHandling.h"
20 #include "llvm/Support/raw_ostream.h"
21 using namespace clang;
22 
23 /// The identity of a type_info object depends on the canonical unqualified
24 /// type only.
25 TypeInfoLValue::TypeInfoLValue(const Type *T)
26     : T(T->getCanonicalTypeUnqualified().getTypePtr()) {}
27 
28 void TypeInfoLValue::print(llvm::raw_ostream &Out,
29                            const PrintingPolicy &Policy) const {
30   Out << "typeid(";
31   QualType(getType(), 0).print(Out, Policy);
32   Out << ")";
33 }
34 
35 static_assert(
36     1 << llvm::PointerLikeTypeTraits<TypeInfoLValue>::NumLowBitsAvailable <=
37         alignof(Type),
38     "Type is insufficiently aligned");
39 
40 APValue::LValueBase::LValueBase(const ValueDecl *P, unsigned I, unsigned V)
41     : Ptr(P ? cast<ValueDecl>(P->getCanonicalDecl()) : nullptr), Local{I, V} {}
42 APValue::LValueBase::LValueBase(const Expr *P, unsigned I, unsigned V)
43     : Ptr(P), Local{I, V} {}
44 
45 APValue::LValueBase APValue::LValueBase::getDynamicAlloc(DynamicAllocLValue LV,
46                                                          QualType Type) {
47   LValueBase Base;
48   Base.Ptr = LV;
49   Base.DynamicAllocType = Type.getAsOpaquePtr();
50   return Base;
51 }
52 
53 APValue::LValueBase APValue::LValueBase::getTypeInfo(TypeInfoLValue LV,
54                                                      QualType TypeInfo) {
55   LValueBase Base;
56   Base.Ptr = LV;
57   Base.TypeInfoType = TypeInfo.getAsOpaquePtr();
58   return Base;
59 }
60 
61 unsigned APValue::LValueBase::getCallIndex() const {
62   return (is<TypeInfoLValue>() || is<DynamicAllocLValue>()) ? 0
63                                                             : Local.CallIndex;
64 }
65 
66 unsigned APValue::LValueBase::getVersion() const {
67   return (is<TypeInfoLValue>() || is<DynamicAllocLValue>()) ? 0 : Local.Version;
68 }
69 
70 QualType APValue::LValueBase::getTypeInfoType() const {
71   assert(is<TypeInfoLValue>() && "not a type_info lvalue");
72   return QualType::getFromOpaquePtr(TypeInfoType);
73 }
74 
75 QualType APValue::LValueBase::getDynamicAllocType() const {
76   assert(is<DynamicAllocLValue>() && "not a dynamic allocation lvalue");
77   return QualType::getFromOpaquePtr(DynamicAllocType);
78 }
79 
80 void APValue::LValueBase::Profile(llvm::FoldingSetNodeID &ID) const {
81   ID.AddPointer(Ptr.getOpaqueValue());
82   if (is<TypeInfoLValue>() || is<DynamicAllocLValue>())
83     return;
84   ID.AddInteger(Local.CallIndex);
85   ID.AddInteger(Local.Version);
86 }
87 
88 namespace clang {
89 bool operator==(const APValue::LValueBase &LHS,
90                 const APValue::LValueBase &RHS) {
91   if (LHS.Ptr != RHS.Ptr)
92     return false;
93   if (LHS.is<TypeInfoLValue>() || LHS.is<DynamicAllocLValue>())
94     return true;
95   return LHS.Local.CallIndex == RHS.Local.CallIndex &&
96          LHS.Local.Version == RHS.Local.Version;
97 }
98 }
99 
100 APValue::LValuePathEntry::LValuePathEntry(BaseOrMemberType BaseOrMember) {
101   if (const Decl *D = BaseOrMember.getPointer())
102     BaseOrMember.setPointer(D->getCanonicalDecl());
103   Value = reinterpret_cast<uintptr_t>(BaseOrMember.getOpaqueValue());
104 }
105 
106 void APValue::LValuePathEntry::Profile(llvm::FoldingSetNodeID &ID) const {
107   ID.AddInteger(Value);
108 }
109 
110 namespace {
111   struct LVBase {
112     APValue::LValueBase Base;
113     CharUnits Offset;
114     unsigned PathLength;
115     bool IsNullPtr : 1;
116     bool IsOnePastTheEnd : 1;
117   };
118 }
119 
120 void *APValue::LValueBase::getOpaqueValue() const {
121   return Ptr.getOpaqueValue();
122 }
123 
124 bool APValue::LValueBase::isNull() const {
125   return Ptr.isNull();
126 }
127 
128 APValue::LValueBase::operator bool () const {
129   return static_cast<bool>(Ptr);
130 }
131 
132 clang::APValue::LValueBase
133 llvm::DenseMapInfo<clang::APValue::LValueBase>::getEmptyKey() {
134   clang::APValue::LValueBase B;
135   B.Ptr = DenseMapInfo<const ValueDecl*>::getEmptyKey();
136   return B;
137 }
138 
139 clang::APValue::LValueBase
140 llvm::DenseMapInfo<clang::APValue::LValueBase>::getTombstoneKey() {
141   clang::APValue::LValueBase B;
142   B.Ptr = DenseMapInfo<const ValueDecl*>::getTombstoneKey();
143   return B;
144 }
145 
146 namespace clang {
147 llvm::hash_code hash_value(const APValue::LValueBase &Base) {
148   if (Base.is<TypeInfoLValue>() || Base.is<DynamicAllocLValue>())
149     return llvm::hash_value(Base.getOpaqueValue());
150   return llvm::hash_combine(Base.getOpaqueValue(), Base.getCallIndex(),
151                             Base.getVersion());
152 }
153 }
154 
155 unsigned llvm::DenseMapInfo<clang::APValue::LValueBase>::getHashValue(
156     const clang::APValue::LValueBase &Base) {
157   return hash_value(Base);
158 }
159 
160 bool llvm::DenseMapInfo<clang::APValue::LValueBase>::isEqual(
161     const clang::APValue::LValueBase &LHS,
162     const clang::APValue::LValueBase &RHS) {
163   return LHS == RHS;
164 }
165 
166 struct APValue::LV : LVBase {
167   static const unsigned InlinePathSpace =
168       (DataSize - sizeof(LVBase)) / sizeof(LValuePathEntry);
169 
170   /// Path - The sequence of base classes, fields and array indices to follow to
171   /// walk from Base to the subobject. When performing GCC-style folding, there
172   /// may not be such a path.
173   union {
174     LValuePathEntry Path[InlinePathSpace];
175     LValuePathEntry *PathPtr;
176   };
177 
178   LV() { PathLength = (unsigned)-1; }
179   ~LV() { resizePath(0); }
180 
181   void resizePath(unsigned Length) {
182     if (Length == PathLength)
183       return;
184     if (hasPathPtr())
185       delete [] PathPtr;
186     PathLength = Length;
187     if (hasPathPtr())
188       PathPtr = new LValuePathEntry[Length];
189   }
190 
191   bool hasPath() const { return PathLength != (unsigned)-1; }
192   bool hasPathPtr() const { return hasPath() && PathLength > InlinePathSpace; }
193 
194   LValuePathEntry *getPath() { return hasPathPtr() ? PathPtr : Path; }
195   const LValuePathEntry *getPath() const {
196     return hasPathPtr() ? PathPtr : Path;
197   }
198 };
199 
200 namespace {
201   struct MemberPointerBase {
202     llvm::PointerIntPair<const ValueDecl*, 1, bool> MemberAndIsDerivedMember;
203     unsigned PathLength;
204   };
205 }
206 
207 struct APValue::MemberPointerData : MemberPointerBase {
208   static const unsigned InlinePathSpace =
209       (DataSize - sizeof(MemberPointerBase)) / sizeof(const CXXRecordDecl*);
210   typedef const CXXRecordDecl *PathElem;
211   union {
212     PathElem Path[InlinePathSpace];
213     PathElem *PathPtr;
214   };
215 
216   MemberPointerData() { PathLength = 0; }
217   ~MemberPointerData() { resizePath(0); }
218 
219   void resizePath(unsigned Length) {
220     if (Length == PathLength)
221       return;
222     if (hasPathPtr())
223       delete [] PathPtr;
224     PathLength = Length;
225     if (hasPathPtr())
226       PathPtr = new PathElem[Length];
227   }
228 
229   bool hasPathPtr() const { return PathLength > InlinePathSpace; }
230 
231   PathElem *getPath() { return hasPathPtr() ? PathPtr : Path; }
232   const PathElem *getPath() const {
233     return hasPathPtr() ? PathPtr : Path;
234   }
235 };
236 
237 // FIXME: Reduce the malloc traffic here.
238 
239 APValue::Arr::Arr(unsigned NumElts, unsigned Size) :
240   Elts(new APValue[NumElts + (NumElts != Size ? 1 : 0)]),
241   NumElts(NumElts), ArrSize(Size) {}
242 APValue::Arr::~Arr() { delete [] Elts; }
243 
244 APValue::StructData::StructData(unsigned NumBases, unsigned NumFields) :
245   Elts(new APValue[NumBases+NumFields]),
246   NumBases(NumBases), NumFields(NumFields) {}
247 APValue::StructData::~StructData() {
248   delete [] Elts;
249 }
250 
251 APValue::UnionData::UnionData() : Field(nullptr), Value(new APValue) {}
252 APValue::UnionData::~UnionData () {
253   delete Value;
254 }
255 
256 APValue::APValue(const APValue &RHS) : Kind(None) {
257   switch (RHS.getKind()) {
258   case None:
259   case Indeterminate:
260     Kind = RHS.getKind();
261     break;
262   case Int:
263     MakeInt();
264     setInt(RHS.getInt());
265     break;
266   case Float:
267     MakeFloat();
268     setFloat(RHS.getFloat());
269     break;
270   case FixedPoint: {
271     APFixedPoint FXCopy = RHS.getFixedPoint();
272     MakeFixedPoint(std::move(FXCopy));
273     break;
274   }
275   case Vector:
276     MakeVector();
277     setVector(((const Vec *)(const char *)RHS.Data.buffer)->Elts,
278               RHS.getVectorLength());
279     break;
280   case ComplexInt:
281     MakeComplexInt();
282     setComplexInt(RHS.getComplexIntReal(), RHS.getComplexIntImag());
283     break;
284   case ComplexFloat:
285     MakeComplexFloat();
286     setComplexFloat(RHS.getComplexFloatReal(), RHS.getComplexFloatImag());
287     break;
288   case LValue:
289     MakeLValue();
290     if (RHS.hasLValuePath())
291       setLValue(RHS.getLValueBase(), RHS.getLValueOffset(), RHS.getLValuePath(),
292                 RHS.isLValueOnePastTheEnd(), RHS.isNullPointer());
293     else
294       setLValue(RHS.getLValueBase(), RHS.getLValueOffset(), NoLValuePath(),
295                 RHS.isNullPointer());
296     break;
297   case Array:
298     MakeArray(RHS.getArrayInitializedElts(), RHS.getArraySize());
299     for (unsigned I = 0, N = RHS.getArrayInitializedElts(); I != N; ++I)
300       getArrayInitializedElt(I) = RHS.getArrayInitializedElt(I);
301     if (RHS.hasArrayFiller())
302       getArrayFiller() = RHS.getArrayFiller();
303     break;
304   case Struct:
305     MakeStruct(RHS.getStructNumBases(), RHS.getStructNumFields());
306     for (unsigned I = 0, N = RHS.getStructNumBases(); I != N; ++I)
307       getStructBase(I) = RHS.getStructBase(I);
308     for (unsigned I = 0, N = RHS.getStructNumFields(); I != N; ++I)
309       getStructField(I) = RHS.getStructField(I);
310     break;
311   case Union:
312     MakeUnion();
313     setUnion(RHS.getUnionField(), RHS.getUnionValue());
314     break;
315   case MemberPointer:
316     MakeMemberPointer(RHS.getMemberPointerDecl(),
317                       RHS.isMemberPointerToDerivedMember(),
318                       RHS.getMemberPointerPath());
319     break;
320   case AddrLabelDiff:
321     MakeAddrLabelDiff();
322     setAddrLabelDiff(RHS.getAddrLabelDiffLHS(), RHS.getAddrLabelDiffRHS());
323     break;
324   }
325 }
326 
327 APValue::APValue(APValue &&RHS) : Kind(RHS.Kind), Data(RHS.Data) {
328   RHS.Kind = None;
329 }
330 
331 APValue &APValue::operator=(const APValue &RHS) {
332   if (this != &RHS)
333     *this = APValue(RHS);
334   return *this;
335 }
336 
337 APValue &APValue::operator=(APValue &&RHS) {
338   if (Kind != None && Kind != Indeterminate)
339     DestroyDataAndMakeUninit();
340   Kind = RHS.Kind;
341   Data = RHS.Data;
342   RHS.Kind = None;
343   return *this;
344 }
345 
346 void APValue::DestroyDataAndMakeUninit() {
347   if (Kind == Int)
348     ((APSInt*)(char*)Data.buffer)->~APSInt();
349   else if (Kind == Float)
350     ((APFloat*)(char*)Data.buffer)->~APFloat();
351   else if (Kind == FixedPoint)
352     ((APFixedPoint *)(char *)Data.buffer)->~APFixedPoint();
353   else if (Kind == Vector)
354     ((Vec*)(char*)Data.buffer)->~Vec();
355   else if (Kind == ComplexInt)
356     ((ComplexAPSInt*)(char*)Data.buffer)->~ComplexAPSInt();
357   else if (Kind == ComplexFloat)
358     ((ComplexAPFloat*)(char*)Data.buffer)->~ComplexAPFloat();
359   else if (Kind == LValue)
360     ((LV*)(char*)Data.buffer)->~LV();
361   else if (Kind == Array)
362     ((Arr*)(char*)Data.buffer)->~Arr();
363   else if (Kind == Struct)
364     ((StructData*)(char*)Data.buffer)->~StructData();
365   else if (Kind == Union)
366     ((UnionData*)(char*)Data.buffer)->~UnionData();
367   else if (Kind == MemberPointer)
368     ((MemberPointerData*)(char*)Data.buffer)->~MemberPointerData();
369   else if (Kind == AddrLabelDiff)
370     ((AddrLabelDiffData*)(char*)Data.buffer)->~AddrLabelDiffData();
371   Kind = None;
372 }
373 
374 bool APValue::needsCleanup() const {
375   switch (getKind()) {
376   case None:
377   case Indeterminate:
378   case AddrLabelDiff:
379     return false;
380   case Struct:
381   case Union:
382   case Array:
383   case Vector:
384     return true;
385   case Int:
386     return getInt().needsCleanup();
387   case Float:
388     return getFloat().needsCleanup();
389   case FixedPoint:
390     return getFixedPoint().getValue().needsCleanup();
391   case ComplexFloat:
392     assert(getComplexFloatImag().needsCleanup() ==
393                getComplexFloatReal().needsCleanup() &&
394            "In _Complex float types, real and imaginary values always have the "
395            "same size.");
396     return getComplexFloatReal().needsCleanup();
397   case ComplexInt:
398     assert(getComplexIntImag().needsCleanup() ==
399                getComplexIntReal().needsCleanup() &&
400            "In _Complex int types, real and imaginary values must have the "
401            "same size.");
402     return getComplexIntReal().needsCleanup();
403   case LValue:
404     return reinterpret_cast<const LV *>(Data.buffer)->hasPathPtr();
405   case MemberPointer:
406     return reinterpret_cast<const MemberPointerData *>(Data.buffer)
407         ->hasPathPtr();
408   }
409   llvm_unreachable("Unknown APValue kind!");
410 }
411 
412 void APValue::swap(APValue &RHS) {
413   std::swap(Kind, RHS.Kind);
414   std::swap(Data, RHS.Data);
415 }
416 
417 /// Profile the value of an APInt, excluding its bit-width.
418 static void profileIntValue(llvm::FoldingSetNodeID &ID, const llvm::APInt &V) {
419   for (unsigned I = 0, N = V.getBitWidth(); I < N; I += 32)
420     ID.AddInteger((uint32_t)V.extractBitsAsZExtValue(std::min(32u, N - I), I));
421 }
422 
423 void APValue::Profile(llvm::FoldingSetNodeID &ID) const {
424   // Note that our profiling assumes that only APValues of the same type are
425   // ever compared. As a result, we don't consider collisions that could only
426   // happen if the types are different. (For example, structs with different
427   // numbers of members could profile the same.)
428 
429   ID.AddInteger(Kind);
430 
431   switch (Kind) {
432   case None:
433   case Indeterminate:
434     return;
435 
436   case AddrLabelDiff:
437     ID.AddPointer(getAddrLabelDiffLHS()->getLabel()->getCanonicalDecl());
438     ID.AddPointer(getAddrLabelDiffRHS()->getLabel()->getCanonicalDecl());
439     return;
440 
441   case Struct:
442     for (unsigned I = 0, N = getStructNumBases(); I != N; ++I)
443       getStructBase(I).Profile(ID);
444     for (unsigned I = 0, N = getStructNumFields(); I != N; ++I)
445       getStructField(I).Profile(ID);
446     return;
447 
448   case Union:
449     if (!getUnionField()) {
450       ID.AddInteger(0);
451       return;
452     }
453     ID.AddInteger(getUnionField()->getFieldIndex() + 1);
454     getUnionValue().Profile(ID);
455     return;
456 
457   case Array: {
458     if (getArraySize() == 0)
459       return;
460 
461     // The profile should not depend on whether the array is expanded or
462     // not, but we don't want to profile the array filler many times for
463     // a large array. So treat all equal trailing elements as the filler.
464     // Elements are profiled in reverse order to support this, and the
465     // first profiled element is followed by a count. For example:
466     //
467     //   ['a', 'c', 'x', 'x', 'x'] is profiled as
468     //   [5, 'x', 3, 'c', 'a']
469     llvm::FoldingSetNodeID FillerID;
470     (hasArrayFiller() ? getArrayFiller()
471                       : getArrayInitializedElt(getArrayInitializedElts() - 1))
472         .Profile(FillerID);
473     ID.AddNodeID(FillerID);
474     unsigned NumFillers = getArraySize() - getArrayInitializedElts();
475     unsigned N = getArrayInitializedElts();
476 
477     // Count the number of elements equal to the last one. This loop ends
478     // by adding an integer indicating the number of such elements, with
479     // N set to the number of elements left to profile.
480     while (true) {
481       if (N == 0) {
482         // All elements are fillers.
483         assert(NumFillers == getArraySize());
484         ID.AddInteger(NumFillers);
485         break;
486       }
487 
488       // No need to check if the last element is equal to the last
489       // element.
490       if (N != getArraySize()) {
491         llvm::FoldingSetNodeID ElemID;
492         getArrayInitializedElt(N - 1).Profile(ElemID);
493         if (ElemID != FillerID) {
494           ID.AddInteger(NumFillers);
495           ID.AddNodeID(ElemID);
496           --N;
497           break;
498         }
499       }
500 
501       // This is a filler.
502       ++NumFillers;
503       --N;
504     }
505 
506     // Emit the remaining elements.
507     for (; N != 0; --N)
508       getArrayInitializedElt(N - 1).Profile(ID);
509     return;
510   }
511 
512   case Vector:
513     for (unsigned I = 0, N = getVectorLength(); I != N; ++I)
514       getVectorElt(I).Profile(ID);
515     return;
516 
517   case Int:
518     profileIntValue(ID, getInt());
519     return;
520 
521   case Float:
522     profileIntValue(ID, getFloat().bitcastToAPInt());
523     return;
524 
525   case FixedPoint:
526     profileIntValue(ID, getFixedPoint().getValue());
527     return;
528 
529   case ComplexFloat:
530     profileIntValue(ID, getComplexFloatReal().bitcastToAPInt());
531     profileIntValue(ID, getComplexFloatImag().bitcastToAPInt());
532     return;
533 
534   case ComplexInt:
535     profileIntValue(ID, getComplexIntReal());
536     profileIntValue(ID, getComplexIntImag());
537     return;
538 
539   case LValue:
540     getLValueBase().Profile(ID);
541     ID.AddInteger(getLValueOffset().getQuantity());
542     ID.AddInteger((isNullPointer() ? 1 : 0) |
543                   (isLValueOnePastTheEnd() ? 2 : 0) |
544                   (hasLValuePath() ? 4 : 0));
545     if (hasLValuePath()) {
546       ID.AddInteger(getLValuePath().size());
547       // For uniqueness, we only need to profile the entries corresponding
548       // to union members, but we don't have the type here so we don't know
549       // how to interpret the entries.
550       for (LValuePathEntry E : getLValuePath())
551         E.Profile(ID);
552     }
553     return;
554 
555   case MemberPointer:
556     ID.AddPointer(getMemberPointerDecl());
557     ID.AddInteger(isMemberPointerToDerivedMember());
558     for (const CXXRecordDecl *D : getMemberPointerPath())
559       ID.AddPointer(D);
560     return;
561   }
562 
563   llvm_unreachable("Unknown APValue kind!");
564 }
565 
566 static double GetApproxValue(const llvm::APFloat &F) {
567   llvm::APFloat V = F;
568   bool ignored;
569   V.convert(llvm::APFloat::IEEEdouble(), llvm::APFloat::rmNearestTiesToEven,
570             &ignored);
571   return V.convertToDouble();
572 }
573 
574 void APValue::printPretty(raw_ostream &Out, const ASTContext &Ctx,
575                           QualType Ty) const {
576   // There are no objects of type 'void', but values of this type can be
577   // returned from functions.
578   if (Ty->isVoidType()) {
579     Out << "void()";
580     return;
581   }
582 
583   switch (getKind()) {
584   case APValue::None:
585     Out << "<out of lifetime>";
586     return;
587   case APValue::Indeterminate:
588     Out << "<uninitialized>";
589     return;
590   case APValue::Int:
591     if (Ty->isBooleanType())
592       Out << (getInt().getBoolValue() ? "true" : "false");
593     else
594       Out << getInt();
595     return;
596   case APValue::Float:
597     Out << GetApproxValue(getFloat());
598     return;
599   case APValue::FixedPoint:
600     Out << getFixedPoint();
601     return;
602   case APValue::Vector: {
603     Out << '{';
604     QualType ElemTy = Ty->castAs<VectorType>()->getElementType();
605     getVectorElt(0).printPretty(Out, Ctx, ElemTy);
606     for (unsigned i = 1; i != getVectorLength(); ++i) {
607       Out << ", ";
608       getVectorElt(i).printPretty(Out, Ctx, ElemTy);
609     }
610     Out << '}';
611     return;
612   }
613   case APValue::ComplexInt:
614     Out << getComplexIntReal() << "+" << getComplexIntImag() << "i";
615     return;
616   case APValue::ComplexFloat:
617     Out << GetApproxValue(getComplexFloatReal()) << "+"
618         << GetApproxValue(getComplexFloatImag()) << "i";
619     return;
620   case APValue::LValue: {
621     bool IsReference = Ty->isReferenceType();
622     QualType InnerTy
623       = IsReference ? Ty.getNonReferenceType() : Ty->getPointeeType();
624     if (InnerTy.isNull())
625       InnerTy = Ty;
626 
627     LValueBase Base = getLValueBase();
628     if (!Base) {
629       if (isNullPointer()) {
630         Out << (Ctx.getLangOpts().CPlusPlus11 ? "nullptr" : "0");
631       } else if (IsReference) {
632         Out << "*(" << InnerTy.stream(Ctx.getPrintingPolicy()) << "*)"
633             << getLValueOffset().getQuantity();
634       } else {
635         Out << "(" << Ty.stream(Ctx.getPrintingPolicy()) << ")"
636             << getLValueOffset().getQuantity();
637       }
638       return;
639     }
640 
641     if (!hasLValuePath()) {
642       // No lvalue path: just print the offset.
643       CharUnits O = getLValueOffset();
644       CharUnits S = Ctx.getTypeSizeInChars(InnerTy);
645       if (!O.isZero()) {
646         if (IsReference)
647           Out << "*(";
648         if (O % S) {
649           Out << "(char*)";
650           S = CharUnits::One();
651         }
652         Out << '&';
653       } else if (!IsReference) {
654         Out << '&';
655       }
656 
657       if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>())
658         Out << *VD;
659       else if (TypeInfoLValue TI = Base.dyn_cast<TypeInfoLValue>()) {
660         TI.print(Out, Ctx.getPrintingPolicy());
661       } else if (DynamicAllocLValue DA = Base.dyn_cast<DynamicAllocLValue>()) {
662         Out << "{*new "
663             << Base.getDynamicAllocType().stream(Ctx.getPrintingPolicy()) << "#"
664             << DA.getIndex() << "}";
665       } else {
666         assert(Base.get<const Expr *>() != nullptr &&
667                "Expecting non-null Expr");
668         Base.get<const Expr*>()->printPretty(Out, nullptr,
669                                              Ctx.getPrintingPolicy());
670       }
671 
672       if (!O.isZero()) {
673         Out << " + " << (O / S);
674         if (IsReference)
675           Out << ')';
676       }
677       return;
678     }
679 
680     // We have an lvalue path. Print it out nicely.
681     if (!IsReference)
682       Out << '&';
683     else if (isLValueOnePastTheEnd())
684       Out << "*(&";
685 
686     QualType ElemTy;
687     if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>()) {
688       Out << *VD;
689       ElemTy = VD->getType();
690     } else if (TypeInfoLValue TI = Base.dyn_cast<TypeInfoLValue>()) {
691       TI.print(Out, Ctx.getPrintingPolicy());
692       ElemTy = Base.getTypeInfoType();
693     } else if (DynamicAllocLValue DA = Base.dyn_cast<DynamicAllocLValue>()) {
694       Out << "{*new "
695           << Base.getDynamicAllocType().stream(Ctx.getPrintingPolicy()) << "#"
696           << DA.getIndex() << "}";
697       ElemTy = Base.getDynamicAllocType();
698     } else {
699       const Expr *E = Base.get<const Expr*>();
700       assert(E != nullptr && "Expecting non-null Expr");
701       E->printPretty(Out, nullptr, Ctx.getPrintingPolicy());
702       // FIXME: This is wrong if E is a MaterializeTemporaryExpr with an lvalue
703       // adjustment.
704       ElemTy = E->getType();
705     }
706 
707     ArrayRef<LValuePathEntry> Path = getLValuePath();
708     const CXXRecordDecl *CastToBase = nullptr;
709     for (unsigned I = 0, N = Path.size(); I != N; ++I) {
710       if (ElemTy->getAs<RecordType>()) {
711         // The lvalue refers to a class type, so the next path entry is a base
712         // or member.
713         const Decl *BaseOrMember = Path[I].getAsBaseOrMember().getPointer();
714         if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(BaseOrMember)) {
715           CastToBase = RD;
716           ElemTy = Ctx.getRecordType(RD);
717         } else {
718           const ValueDecl *VD = cast<ValueDecl>(BaseOrMember);
719           Out << ".";
720           if (CastToBase)
721             Out << *CastToBase << "::";
722           Out << *VD;
723           ElemTy = VD->getType();
724         }
725       } else {
726         // The lvalue must refer to an array.
727         Out << '[' << Path[I].getAsArrayIndex() << ']';
728         ElemTy = Ctx.getAsArrayType(ElemTy)->getElementType();
729       }
730     }
731 
732     // Handle formatting of one-past-the-end lvalues.
733     if (isLValueOnePastTheEnd()) {
734       // FIXME: If CastToBase is non-0, we should prefix the output with
735       // "(CastToBase*)".
736       Out << " + 1";
737       if (IsReference)
738         Out << ')';
739     }
740     return;
741   }
742   case APValue::Array: {
743     const ArrayType *AT = Ctx.getAsArrayType(Ty);
744     QualType ElemTy = AT->getElementType();
745     Out << '{';
746     if (unsigned N = getArrayInitializedElts()) {
747       getArrayInitializedElt(0).printPretty(Out, Ctx, ElemTy);
748       for (unsigned I = 1; I != N; ++I) {
749         Out << ", ";
750         if (I == 10) {
751           // Avoid printing out the entire contents of large arrays.
752           Out << "...";
753           break;
754         }
755         getArrayInitializedElt(I).printPretty(Out, Ctx, ElemTy);
756       }
757     }
758     Out << '}';
759     return;
760   }
761   case APValue::Struct: {
762     Out << '{';
763     const RecordDecl *RD = Ty->castAs<RecordType>()->getDecl();
764     bool First = true;
765     if (unsigned N = getStructNumBases()) {
766       const CXXRecordDecl *CD = cast<CXXRecordDecl>(RD);
767       CXXRecordDecl::base_class_const_iterator BI = CD->bases_begin();
768       for (unsigned I = 0; I != N; ++I, ++BI) {
769         assert(BI != CD->bases_end());
770         if (!First)
771           Out << ", ";
772         getStructBase(I).printPretty(Out, Ctx, BI->getType());
773         First = false;
774       }
775     }
776     for (const auto *FI : RD->fields()) {
777       if (!First)
778         Out << ", ";
779       if (FI->isUnnamedBitfield()) continue;
780       getStructField(FI->getFieldIndex()).
781         printPretty(Out, Ctx, FI->getType());
782       First = false;
783     }
784     Out << '}';
785     return;
786   }
787   case APValue::Union:
788     Out << '{';
789     if (const FieldDecl *FD = getUnionField()) {
790       Out << "." << *FD << " = ";
791       getUnionValue().printPretty(Out, Ctx, FD->getType());
792     }
793     Out << '}';
794     return;
795   case APValue::MemberPointer:
796     // FIXME: This is not enough to unambiguously identify the member in a
797     // multiple-inheritance scenario.
798     if (const ValueDecl *VD = getMemberPointerDecl()) {
799       Out << '&' << *cast<CXXRecordDecl>(VD->getDeclContext()) << "::" << *VD;
800       return;
801     }
802     Out << "0";
803     return;
804   case APValue::AddrLabelDiff:
805     Out << "&&" << getAddrLabelDiffLHS()->getLabel()->getName();
806     Out << " - ";
807     Out << "&&" << getAddrLabelDiffRHS()->getLabel()->getName();
808     return;
809   }
810   llvm_unreachable("Unknown APValue kind!");
811 }
812 
813 std::string APValue::getAsString(const ASTContext &Ctx, QualType Ty) const {
814   std::string Result;
815   llvm::raw_string_ostream Out(Result);
816   printPretty(Out, Ctx, Ty);
817   Out.flush();
818   return Result;
819 }
820 
821 bool APValue::toIntegralConstant(APSInt &Result, QualType SrcTy,
822                                  const ASTContext &Ctx) const {
823   if (isInt()) {
824     Result = getInt();
825     return true;
826   }
827 
828   if (isLValue() && isNullPointer()) {
829     Result = Ctx.MakeIntValue(Ctx.getTargetNullPointerValue(SrcTy), SrcTy);
830     return true;
831   }
832 
833   if (isLValue() && !getLValueBase()) {
834     Result = Ctx.MakeIntValue(getLValueOffset().getQuantity(), SrcTy);
835     return true;
836   }
837 
838   return false;
839 }
840 
841 const APValue::LValueBase APValue::getLValueBase() const {
842   assert(isLValue() && "Invalid accessor");
843   return ((const LV*)(const void*)Data.buffer)->Base;
844 }
845 
846 bool APValue::isLValueOnePastTheEnd() const {
847   assert(isLValue() && "Invalid accessor");
848   return ((const LV*)(const void*)Data.buffer)->IsOnePastTheEnd;
849 }
850 
851 CharUnits &APValue::getLValueOffset() {
852   assert(isLValue() && "Invalid accessor");
853   return ((LV*)(void*)Data.buffer)->Offset;
854 }
855 
856 bool APValue::hasLValuePath() const {
857   assert(isLValue() && "Invalid accessor");
858   return ((const LV*)(const char*)Data.buffer)->hasPath();
859 }
860 
861 ArrayRef<APValue::LValuePathEntry> APValue::getLValuePath() const {
862   assert(isLValue() && hasLValuePath() && "Invalid accessor");
863   const LV &LVal = *((const LV*)(const char*)Data.buffer);
864   return llvm::makeArrayRef(LVal.getPath(), LVal.PathLength);
865 }
866 
867 unsigned APValue::getLValueCallIndex() const {
868   assert(isLValue() && "Invalid accessor");
869   return ((const LV*)(const char*)Data.buffer)->Base.getCallIndex();
870 }
871 
872 unsigned APValue::getLValueVersion() const {
873   assert(isLValue() && "Invalid accessor");
874   return ((const LV*)(const char*)Data.buffer)->Base.getVersion();
875 }
876 
877 bool APValue::isNullPointer() const {
878   assert(isLValue() && "Invalid usage");
879   return ((const LV*)(const char*)Data.buffer)->IsNullPtr;
880 }
881 
882 void APValue::setLValue(LValueBase B, const CharUnits &O, NoLValuePath,
883                         bool IsNullPtr) {
884   assert(isLValue() && "Invalid accessor");
885   LV &LVal = *((LV*)(char*)Data.buffer);
886   LVal.Base = B;
887   LVal.IsOnePastTheEnd = false;
888   LVal.Offset = O;
889   LVal.resizePath((unsigned)-1);
890   LVal.IsNullPtr = IsNullPtr;
891 }
892 
893 MutableArrayRef<APValue::LValuePathEntry>
894 APValue::setLValueUninit(LValueBase B, const CharUnits &O, unsigned Size,
895                          bool IsOnePastTheEnd, bool IsNullPtr) {
896   assert(isLValue() && "Invalid accessor");
897   LV &LVal = *((LV *)(char *)Data.buffer);
898   LVal.Base = B;
899   LVal.IsOnePastTheEnd = IsOnePastTheEnd;
900   LVal.Offset = O;
901   LVal.IsNullPtr = IsNullPtr;
902   LVal.resizePath(Size);
903   return {LVal.getPath(), Size};
904 }
905 
906 void APValue::setLValue(LValueBase B, const CharUnits &O,
907                         ArrayRef<LValuePathEntry> Path, bool IsOnePastTheEnd,
908                         bool IsNullPtr) {
909   MutableArrayRef<APValue::LValuePathEntry> InternalPath =
910       setLValueUninit(B, O, Path.size(), IsOnePastTheEnd, IsNullPtr);
911   memcpy(InternalPath.data(), Path.data(),
912          Path.size() * sizeof(LValuePathEntry));
913 }
914 
915 void APValue::setUnion(const FieldDecl *Field, const APValue &Value) {
916   assert(isUnion() && "Invalid accessor");
917   ((UnionData *)(char *)Data.buffer)->Field =
918       Field ? Field->getCanonicalDecl() : nullptr;
919   *((UnionData*)(char*)Data.buffer)->Value = Value;
920 }
921 
922 const ValueDecl *APValue::getMemberPointerDecl() const {
923   assert(isMemberPointer() && "Invalid accessor");
924   const MemberPointerData &MPD =
925       *((const MemberPointerData *)(const char *)Data.buffer);
926   return MPD.MemberAndIsDerivedMember.getPointer();
927 }
928 
929 bool APValue::isMemberPointerToDerivedMember() const {
930   assert(isMemberPointer() && "Invalid accessor");
931   const MemberPointerData &MPD =
932       *((const MemberPointerData *)(const char *)Data.buffer);
933   return MPD.MemberAndIsDerivedMember.getInt();
934 }
935 
936 ArrayRef<const CXXRecordDecl*> APValue::getMemberPointerPath() const {
937   assert(isMemberPointer() && "Invalid accessor");
938   const MemberPointerData &MPD =
939       *((const MemberPointerData *)(const char *)Data.buffer);
940   return llvm::makeArrayRef(MPD.getPath(), MPD.PathLength);
941 }
942 
943 void APValue::MakeLValue() {
944   assert(isAbsent() && "Bad state change");
945   static_assert(sizeof(LV) <= DataSize, "LV too big");
946   new ((void*)(char*)Data.buffer) LV();
947   Kind = LValue;
948 }
949 
950 void APValue::MakeArray(unsigned InitElts, unsigned Size) {
951   assert(isAbsent() && "Bad state change");
952   new ((void*)(char*)Data.buffer) Arr(InitElts, Size);
953   Kind = Array;
954 }
955 
956 MutableArrayRef<APValue::LValuePathEntry>
957 setLValueUninit(APValue::LValueBase B, const CharUnits &O, unsigned Size,
958                 bool OnePastTheEnd, bool IsNullPtr);
959 
960 MutableArrayRef<const CXXRecordDecl *>
961 APValue::setMemberPointerUninit(const ValueDecl *Member, bool IsDerivedMember,
962                                 unsigned Size) {
963   assert(isAbsent() && "Bad state change");
964   MemberPointerData *MPD = new ((void *)(char *)Data.buffer) MemberPointerData;
965   Kind = MemberPointer;
966   MPD->MemberAndIsDerivedMember.setPointer(
967       Member ? cast<ValueDecl>(Member->getCanonicalDecl()) : nullptr);
968   MPD->MemberAndIsDerivedMember.setInt(IsDerivedMember);
969   MPD->resizePath(Size);
970   return {MPD->getPath(), MPD->PathLength};
971 }
972 
973 void APValue::MakeMemberPointer(const ValueDecl *Member, bool IsDerivedMember,
974                                 ArrayRef<const CXXRecordDecl *> Path) {
975   MutableArrayRef<const CXXRecordDecl *> InternalPath =
976       setMemberPointerUninit(Member, IsDerivedMember, Path.size());
977   for (unsigned I = 0; I != Path.size(); ++I)
978     InternalPath[I] = Path[I]->getCanonicalDecl();
979 }
980