1 //===--- CGExprConstant.cpp - Emit LLVM Code from Constant Expressions ----===//
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 contains code to emit Constant Expr nodes as LLVM code.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "CGCXXABI.h"
14 #include "CGObjCRuntime.h"
15 #include "CGRecordLayout.h"
16 #include "CodeGenFunction.h"
17 #include "CodeGenModule.h"
18 #include "ConstantEmitter.h"
19 #include "TargetInfo.h"
20 #include "clang/AST/APValue.h"
21 #include "clang/AST/ASTContext.h"
22 #include "clang/AST/Attr.h"
23 #include "clang/AST/RecordLayout.h"
24 #include "clang/AST/StmtVisitor.h"
25 #include "clang/Basic/Builtins.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/ADT/Sequence.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/Function.h"
31 #include "llvm/IR/GlobalVariable.h"
32 #include <optional>
33 using namespace clang;
34 using namespace CodeGen;
35 
36 //===----------------------------------------------------------------------===//
37 //                            ConstantAggregateBuilder
38 //===----------------------------------------------------------------------===//
39 
40 namespace {
41 class ConstExprEmitter;
42 
43 struct ConstantAggregateBuilderUtils {
44   CodeGenModule &CGM;
45 
46   ConstantAggregateBuilderUtils(CodeGenModule &CGM) : CGM(CGM) {}
47 
48   CharUnits getAlignment(const llvm::Constant *C) const {
49     return CharUnits::fromQuantity(
50         CGM.getDataLayout().getABITypeAlign(C->getType()));
51   }
52 
53   CharUnits getSize(llvm::Type *Ty) const {
54     return CharUnits::fromQuantity(CGM.getDataLayout().getTypeAllocSize(Ty));
55   }
56 
57   CharUnits getSize(const llvm::Constant *C) const {
58     return getSize(C->getType());
59   }
60 
61   llvm::Constant *getPadding(CharUnits PadSize) const {
62     llvm::Type *Ty = CGM.CharTy;
63     if (PadSize > CharUnits::One())
64       Ty = llvm::ArrayType::get(Ty, PadSize.getQuantity());
65     return llvm::UndefValue::get(Ty);
66   }
67 
68   llvm::Constant *getZeroes(CharUnits ZeroSize) const {
69     llvm::Type *Ty = llvm::ArrayType::get(CGM.CharTy, ZeroSize.getQuantity());
70     return llvm::ConstantAggregateZero::get(Ty);
71   }
72 };
73 
74 /// Incremental builder for an llvm::Constant* holding a struct or array
75 /// constant.
76 class ConstantAggregateBuilder : private ConstantAggregateBuilderUtils {
77   /// The elements of the constant. These two arrays must have the same size;
78   /// Offsets[i] describes the offset of Elems[i] within the constant. The
79   /// elements are kept in increasing offset order, and we ensure that there
80   /// is no overlap: Offsets[i+1] >= Offsets[i] + getSize(Elemes[i]).
81   ///
82   /// This may contain explicit padding elements (in order to create a
83   /// natural layout), but need not. Gaps between elements are implicitly
84   /// considered to be filled with undef.
85   llvm::SmallVector<llvm::Constant*, 32> Elems;
86   llvm::SmallVector<CharUnits, 32> Offsets;
87 
88   /// The size of the constant (the maximum end offset of any added element).
89   /// May be larger than the end of Elems.back() if we split the last element
90   /// and removed some trailing undefs.
91   CharUnits Size = CharUnits::Zero();
92 
93   /// This is true only if laying out Elems in order as the elements of a
94   /// non-packed LLVM struct will give the correct layout.
95   bool NaturalLayout = true;
96 
97   bool split(size_t Index, CharUnits Hint);
98   std::optional<size_t> splitAt(CharUnits Pos);
99 
100   static llvm::Constant *buildFrom(CodeGenModule &CGM,
101                                    ArrayRef<llvm::Constant *> Elems,
102                                    ArrayRef<CharUnits> Offsets,
103                                    CharUnits StartOffset, CharUnits Size,
104                                    bool NaturalLayout, llvm::Type *DesiredTy,
105                                    bool AllowOversized);
106 
107 public:
108   ConstantAggregateBuilder(CodeGenModule &CGM)
109       : ConstantAggregateBuilderUtils(CGM) {}
110 
111   /// Update or overwrite the value starting at \p Offset with \c C.
112   ///
113   /// \param AllowOverwrite If \c true, this constant might overwrite (part of)
114   ///        a constant that has already been added. This flag is only used to
115   ///        detect bugs.
116   bool add(llvm::Constant *C, CharUnits Offset, bool AllowOverwrite);
117 
118   /// Update or overwrite the bits starting at \p OffsetInBits with \p Bits.
119   bool addBits(llvm::APInt Bits, uint64_t OffsetInBits, bool AllowOverwrite);
120 
121   /// Attempt to condense the value starting at \p Offset to a constant of type
122   /// \p DesiredTy.
123   void condense(CharUnits Offset, llvm::Type *DesiredTy);
124 
125   /// Produce a constant representing the entire accumulated value, ideally of
126   /// the specified type. If \p AllowOversized, the constant might be larger
127   /// than implied by \p DesiredTy (eg, if there is a flexible array member).
128   /// Otherwise, the constant will be of exactly the same size as \p DesiredTy
129   /// even if we can't represent it as that type.
130   llvm::Constant *build(llvm::Type *DesiredTy, bool AllowOversized) const {
131     return buildFrom(CGM, Elems, Offsets, CharUnits::Zero(), Size,
132                      NaturalLayout, DesiredTy, AllowOversized);
133   }
134 };
135 
136 template<typename Container, typename Range = std::initializer_list<
137                                  typename Container::value_type>>
138 static void replace(Container &C, size_t BeginOff, size_t EndOff, Range Vals) {
139   assert(BeginOff <= EndOff && "invalid replacement range");
140   llvm::replace(C, C.begin() + BeginOff, C.begin() + EndOff, Vals);
141 }
142 
143 bool ConstantAggregateBuilder::add(llvm::Constant *C, CharUnits Offset,
144                           bool AllowOverwrite) {
145   // Common case: appending to a layout.
146   if (Offset >= Size) {
147     CharUnits Align = getAlignment(C);
148     CharUnits AlignedSize = Size.alignTo(Align);
149     if (AlignedSize > Offset || Offset.alignTo(Align) != Offset)
150       NaturalLayout = false;
151     else if (AlignedSize < Offset) {
152       Elems.push_back(getPadding(Offset - Size));
153       Offsets.push_back(Size);
154     }
155     Elems.push_back(C);
156     Offsets.push_back(Offset);
157     Size = Offset + getSize(C);
158     return true;
159   }
160 
161   // Uncommon case: constant overlaps what we've already created.
162   std::optional<size_t> FirstElemToReplace = splitAt(Offset);
163   if (!FirstElemToReplace)
164     return false;
165 
166   CharUnits CSize = getSize(C);
167   std::optional<size_t> LastElemToReplace = splitAt(Offset + CSize);
168   if (!LastElemToReplace)
169     return false;
170 
171   assert((FirstElemToReplace == LastElemToReplace || AllowOverwrite) &&
172          "unexpectedly overwriting field");
173 
174   replace(Elems, *FirstElemToReplace, *LastElemToReplace, {C});
175   replace(Offsets, *FirstElemToReplace, *LastElemToReplace, {Offset});
176   Size = std::max(Size, Offset + CSize);
177   NaturalLayout = false;
178   return true;
179 }
180 
181 bool ConstantAggregateBuilder::addBits(llvm::APInt Bits, uint64_t OffsetInBits,
182                               bool AllowOverwrite) {
183   const ASTContext &Context = CGM.getContext();
184   const uint64_t CharWidth = CGM.getContext().getCharWidth();
185 
186   // Offset of where we want the first bit to go within the bits of the
187   // current char.
188   unsigned OffsetWithinChar = OffsetInBits % CharWidth;
189 
190   // We split bit-fields up into individual bytes. Walk over the bytes and
191   // update them.
192   for (CharUnits OffsetInChars =
193            Context.toCharUnitsFromBits(OffsetInBits - OffsetWithinChar);
194        /**/; ++OffsetInChars) {
195     // Number of bits we want to fill in this char.
196     unsigned WantedBits =
197         std::min((uint64_t)Bits.getBitWidth(), CharWidth - OffsetWithinChar);
198 
199     // Get a char containing the bits we want in the right places. The other
200     // bits have unspecified values.
201     llvm::APInt BitsThisChar = Bits;
202     if (BitsThisChar.getBitWidth() < CharWidth)
203       BitsThisChar = BitsThisChar.zext(CharWidth);
204     if (CGM.getDataLayout().isBigEndian()) {
205       // Figure out how much to shift by. We may need to left-shift if we have
206       // less than one byte of Bits left.
207       int Shift = Bits.getBitWidth() - CharWidth + OffsetWithinChar;
208       if (Shift > 0)
209         BitsThisChar.lshrInPlace(Shift);
210       else if (Shift < 0)
211         BitsThisChar = BitsThisChar.shl(-Shift);
212     } else {
213       BitsThisChar = BitsThisChar.shl(OffsetWithinChar);
214     }
215     if (BitsThisChar.getBitWidth() > CharWidth)
216       BitsThisChar = BitsThisChar.trunc(CharWidth);
217 
218     if (WantedBits == CharWidth) {
219       // Got a full byte: just add it directly.
220       add(llvm::ConstantInt::get(CGM.getLLVMContext(), BitsThisChar),
221           OffsetInChars, AllowOverwrite);
222     } else {
223       // Partial byte: update the existing integer if there is one. If we
224       // can't split out a 1-CharUnit range to update, then we can't add
225       // these bits and fail the entire constant emission.
226       std::optional<size_t> FirstElemToUpdate = splitAt(OffsetInChars);
227       if (!FirstElemToUpdate)
228         return false;
229       std::optional<size_t> LastElemToUpdate =
230           splitAt(OffsetInChars + CharUnits::One());
231       if (!LastElemToUpdate)
232         return false;
233       assert(*LastElemToUpdate - *FirstElemToUpdate < 2 &&
234              "should have at most one element covering one byte");
235 
236       // Figure out which bits we want and discard the rest.
237       llvm::APInt UpdateMask(CharWidth, 0);
238       if (CGM.getDataLayout().isBigEndian())
239         UpdateMask.setBits(CharWidth - OffsetWithinChar - WantedBits,
240                            CharWidth - OffsetWithinChar);
241       else
242         UpdateMask.setBits(OffsetWithinChar, OffsetWithinChar + WantedBits);
243       BitsThisChar &= UpdateMask;
244 
245       if (*FirstElemToUpdate == *LastElemToUpdate ||
246           Elems[*FirstElemToUpdate]->isNullValue() ||
247           isa<llvm::UndefValue>(Elems[*FirstElemToUpdate])) {
248         // All existing bits are either zero or undef.
249         add(llvm::ConstantInt::get(CGM.getLLVMContext(), BitsThisChar),
250             OffsetInChars, /*AllowOverwrite*/ true);
251       } else {
252         llvm::Constant *&ToUpdate = Elems[*FirstElemToUpdate];
253         // In order to perform a partial update, we need the existing bitwise
254         // value, which we can only extract for a constant int.
255         auto *CI = dyn_cast<llvm::ConstantInt>(ToUpdate);
256         if (!CI)
257           return false;
258         // Because this is a 1-CharUnit range, the constant occupying it must
259         // be exactly one CharUnit wide.
260         assert(CI->getBitWidth() == CharWidth && "splitAt failed");
261         assert((!(CI->getValue() & UpdateMask) || AllowOverwrite) &&
262                "unexpectedly overwriting bitfield");
263         BitsThisChar |= (CI->getValue() & ~UpdateMask);
264         ToUpdate = llvm::ConstantInt::get(CGM.getLLVMContext(), BitsThisChar);
265       }
266     }
267 
268     // Stop if we've added all the bits.
269     if (WantedBits == Bits.getBitWidth())
270       break;
271 
272     // Remove the consumed bits from Bits.
273     if (!CGM.getDataLayout().isBigEndian())
274       Bits.lshrInPlace(WantedBits);
275     Bits = Bits.trunc(Bits.getBitWidth() - WantedBits);
276 
277     // The remanining bits go at the start of the following bytes.
278     OffsetWithinChar = 0;
279   }
280 
281   return true;
282 }
283 
284 /// Returns a position within Elems and Offsets such that all elements
285 /// before the returned index end before Pos and all elements at or after
286 /// the returned index begin at or after Pos. Splits elements as necessary
287 /// to ensure this. Returns std::nullopt if we find something we can't split.
288 std::optional<size_t> ConstantAggregateBuilder::splitAt(CharUnits Pos) {
289   if (Pos >= Size)
290     return Offsets.size();
291 
292   while (true) {
293     auto FirstAfterPos = llvm::upper_bound(Offsets, Pos);
294     if (FirstAfterPos == Offsets.begin())
295       return 0;
296 
297     // If we already have an element starting at Pos, we're done.
298     size_t LastAtOrBeforePosIndex = FirstAfterPos - Offsets.begin() - 1;
299     if (Offsets[LastAtOrBeforePosIndex] == Pos)
300       return LastAtOrBeforePosIndex;
301 
302     // We found an element starting before Pos. Check for overlap.
303     if (Offsets[LastAtOrBeforePosIndex] +
304         getSize(Elems[LastAtOrBeforePosIndex]) <= Pos)
305       return LastAtOrBeforePosIndex + 1;
306 
307     // Try to decompose it into smaller constants.
308     if (!split(LastAtOrBeforePosIndex, Pos))
309       return std::nullopt;
310   }
311 }
312 
313 /// Split the constant at index Index, if possible. Return true if we did.
314 /// Hint indicates the location at which we'd like to split, but may be
315 /// ignored.
316 bool ConstantAggregateBuilder::split(size_t Index, CharUnits Hint) {
317   NaturalLayout = false;
318   llvm::Constant *C = Elems[Index];
319   CharUnits Offset = Offsets[Index];
320 
321   if (auto *CA = dyn_cast<llvm::ConstantAggregate>(C)) {
322     // Expand the sequence into its contained elements.
323     // FIXME: This assumes vector elements are byte-sized.
324     replace(Elems, Index, Index + 1,
325             llvm::map_range(llvm::seq(0u, CA->getNumOperands()),
326                             [&](unsigned Op) { return CA->getOperand(Op); }));
327     if (isa<llvm::ArrayType>(CA->getType()) ||
328         isa<llvm::VectorType>(CA->getType())) {
329       // Array or vector.
330       llvm::Type *ElemTy =
331           llvm::GetElementPtrInst::getTypeAtIndex(CA->getType(), (uint64_t)0);
332       CharUnits ElemSize = getSize(ElemTy);
333       replace(
334           Offsets, Index, Index + 1,
335           llvm::map_range(llvm::seq(0u, CA->getNumOperands()),
336                           [&](unsigned Op) { return Offset + Op * ElemSize; }));
337     } else {
338       // Must be a struct.
339       auto *ST = cast<llvm::StructType>(CA->getType());
340       const llvm::StructLayout *Layout =
341           CGM.getDataLayout().getStructLayout(ST);
342       replace(Offsets, Index, Index + 1,
343               llvm::map_range(
344                   llvm::seq(0u, CA->getNumOperands()), [&](unsigned Op) {
345                     return Offset + CharUnits::fromQuantity(
346                                         Layout->getElementOffset(Op));
347                   }));
348     }
349     return true;
350   }
351 
352   if (auto *CDS = dyn_cast<llvm::ConstantDataSequential>(C)) {
353     // Expand the sequence into its contained elements.
354     // FIXME: This assumes vector elements are byte-sized.
355     // FIXME: If possible, split into two ConstantDataSequentials at Hint.
356     CharUnits ElemSize = getSize(CDS->getElementType());
357     replace(Elems, Index, Index + 1,
358             llvm::map_range(llvm::seq(0u, CDS->getNumElements()),
359                             [&](unsigned Elem) {
360                               return CDS->getElementAsConstant(Elem);
361                             }));
362     replace(Offsets, Index, Index + 1,
363             llvm::map_range(
364                 llvm::seq(0u, CDS->getNumElements()),
365                 [&](unsigned Elem) { return Offset + Elem * ElemSize; }));
366     return true;
367   }
368 
369   if (isa<llvm::ConstantAggregateZero>(C)) {
370     // Split into two zeros at the hinted offset.
371     CharUnits ElemSize = getSize(C);
372     assert(Hint > Offset && Hint < Offset + ElemSize && "nothing to split");
373     replace(Elems, Index, Index + 1,
374             {getZeroes(Hint - Offset), getZeroes(Offset + ElemSize - Hint)});
375     replace(Offsets, Index, Index + 1, {Offset, Hint});
376     return true;
377   }
378 
379   if (isa<llvm::UndefValue>(C)) {
380     // Drop undef; it doesn't contribute to the final layout.
381     replace(Elems, Index, Index + 1, {});
382     replace(Offsets, Index, Index + 1, {});
383     return true;
384   }
385 
386   // FIXME: We could split a ConstantInt if the need ever arose.
387   // We don't need to do this to handle bit-fields because we always eagerly
388   // split them into 1-byte chunks.
389 
390   return false;
391 }
392 
393 static llvm::Constant *
394 EmitArrayConstant(CodeGenModule &CGM, llvm::ArrayType *DesiredType,
395                   llvm::Type *CommonElementType, unsigned ArrayBound,
396                   SmallVectorImpl<llvm::Constant *> &Elements,
397                   llvm::Constant *Filler);
398 
399 llvm::Constant *ConstantAggregateBuilder::buildFrom(
400     CodeGenModule &CGM, ArrayRef<llvm::Constant *> Elems,
401     ArrayRef<CharUnits> Offsets, CharUnits StartOffset, CharUnits Size,
402     bool NaturalLayout, llvm::Type *DesiredTy, bool AllowOversized) {
403   ConstantAggregateBuilderUtils Utils(CGM);
404 
405   if (Elems.empty())
406     return llvm::UndefValue::get(DesiredTy);
407 
408   auto Offset = [&](size_t I) { return Offsets[I] - StartOffset; };
409 
410   // If we want an array type, see if all the elements are the same type and
411   // appropriately spaced.
412   if (llvm::ArrayType *ATy = dyn_cast<llvm::ArrayType>(DesiredTy)) {
413     assert(!AllowOversized && "oversized array emission not supported");
414 
415     bool CanEmitArray = true;
416     llvm::Type *CommonType = Elems[0]->getType();
417     llvm::Constant *Filler = llvm::Constant::getNullValue(CommonType);
418     CharUnits ElemSize = Utils.getSize(ATy->getElementType());
419     SmallVector<llvm::Constant*, 32> ArrayElements;
420     for (size_t I = 0; I != Elems.size(); ++I) {
421       // Skip zeroes; we'll use a zero value as our array filler.
422       if (Elems[I]->isNullValue())
423         continue;
424 
425       // All remaining elements must be the same type.
426       if (Elems[I]->getType() != CommonType ||
427           Offset(I) % ElemSize != 0) {
428         CanEmitArray = false;
429         break;
430       }
431       ArrayElements.resize(Offset(I) / ElemSize + 1, Filler);
432       ArrayElements.back() = Elems[I];
433     }
434 
435     if (CanEmitArray) {
436       return EmitArrayConstant(CGM, ATy, CommonType, ATy->getNumElements(),
437                                ArrayElements, Filler);
438     }
439 
440     // Can't emit as an array, carry on to emit as a struct.
441   }
442 
443   // The size of the constant we plan to generate.  This is usually just
444   // the size of the initialized type, but in AllowOversized mode (i.e.
445   // flexible array init), it can be larger.
446   CharUnits DesiredSize = Utils.getSize(DesiredTy);
447   if (Size > DesiredSize) {
448     assert(AllowOversized && "Elems are oversized");
449     DesiredSize = Size;
450   }
451 
452   // The natural alignment of an unpacked LLVM struct with the given elements.
453   CharUnits Align = CharUnits::One();
454   for (llvm::Constant *C : Elems)
455     Align = std::max(Align, Utils.getAlignment(C));
456 
457   // The natural size of an unpacked LLVM struct with the given elements.
458   CharUnits AlignedSize = Size.alignTo(Align);
459 
460   bool Packed = false;
461   ArrayRef<llvm::Constant*> UnpackedElems = Elems;
462   llvm::SmallVector<llvm::Constant*, 32> UnpackedElemStorage;
463   if (DesiredSize < AlignedSize || DesiredSize.alignTo(Align) != DesiredSize) {
464     // The natural layout would be too big; force use of a packed layout.
465     NaturalLayout = false;
466     Packed = true;
467   } else if (DesiredSize > AlignedSize) {
468     // The natural layout would be too small. Add padding to fix it. (This
469     // is ignored if we choose a packed layout.)
470     UnpackedElemStorage.assign(Elems.begin(), Elems.end());
471     UnpackedElemStorage.push_back(Utils.getPadding(DesiredSize - Size));
472     UnpackedElems = UnpackedElemStorage;
473   }
474 
475   // If we don't have a natural layout, insert padding as necessary.
476   // As we go, double-check to see if we can actually just emit Elems
477   // as a non-packed struct and do so opportunistically if possible.
478   llvm::SmallVector<llvm::Constant*, 32> PackedElems;
479   if (!NaturalLayout) {
480     CharUnits SizeSoFar = CharUnits::Zero();
481     for (size_t I = 0; I != Elems.size(); ++I) {
482       CharUnits Align = Utils.getAlignment(Elems[I]);
483       CharUnits NaturalOffset = SizeSoFar.alignTo(Align);
484       CharUnits DesiredOffset = Offset(I);
485       assert(DesiredOffset >= SizeSoFar && "elements out of order");
486 
487       if (DesiredOffset != NaturalOffset)
488         Packed = true;
489       if (DesiredOffset != SizeSoFar)
490         PackedElems.push_back(Utils.getPadding(DesiredOffset - SizeSoFar));
491       PackedElems.push_back(Elems[I]);
492       SizeSoFar = DesiredOffset + Utils.getSize(Elems[I]);
493     }
494     // If we're using the packed layout, pad it out to the desired size if
495     // necessary.
496     if (Packed) {
497       assert(SizeSoFar <= DesiredSize &&
498              "requested size is too small for contents");
499       if (SizeSoFar < DesiredSize)
500         PackedElems.push_back(Utils.getPadding(DesiredSize - SizeSoFar));
501     }
502   }
503 
504   llvm::StructType *STy = llvm::ConstantStruct::getTypeForElements(
505       CGM.getLLVMContext(), Packed ? PackedElems : UnpackedElems, Packed);
506 
507   // Pick the type to use.  If the type is layout identical to the desired
508   // type then use it, otherwise use whatever the builder produced for us.
509   if (llvm::StructType *DesiredSTy = dyn_cast<llvm::StructType>(DesiredTy)) {
510     if (DesiredSTy->isLayoutIdentical(STy))
511       STy = DesiredSTy;
512   }
513 
514   return llvm::ConstantStruct::get(STy, Packed ? PackedElems : UnpackedElems);
515 }
516 
517 void ConstantAggregateBuilder::condense(CharUnits Offset,
518                                         llvm::Type *DesiredTy) {
519   CharUnits Size = getSize(DesiredTy);
520 
521   std::optional<size_t> FirstElemToReplace = splitAt(Offset);
522   if (!FirstElemToReplace)
523     return;
524   size_t First = *FirstElemToReplace;
525 
526   std::optional<size_t> LastElemToReplace = splitAt(Offset + Size);
527   if (!LastElemToReplace)
528     return;
529   size_t Last = *LastElemToReplace;
530 
531   size_t Length = Last - First;
532   if (Length == 0)
533     return;
534 
535   if (Length == 1 && Offsets[First] == Offset &&
536       getSize(Elems[First]) == Size) {
537     // Re-wrap single element structs if necessary. Otherwise, leave any single
538     // element constant of the right size alone even if it has the wrong type.
539     auto *STy = dyn_cast<llvm::StructType>(DesiredTy);
540     if (STy && STy->getNumElements() == 1 &&
541         STy->getElementType(0) == Elems[First]->getType())
542       Elems[First] = llvm::ConstantStruct::get(STy, Elems[First]);
543     return;
544   }
545 
546   llvm::Constant *Replacement = buildFrom(
547       CGM, ArrayRef(Elems).slice(First, Length),
548       ArrayRef(Offsets).slice(First, Length), Offset, getSize(DesiredTy),
549       /*known to have natural layout=*/false, DesiredTy, false);
550   replace(Elems, First, Last, {Replacement});
551   replace(Offsets, First, Last, {Offset});
552 }
553 
554 //===----------------------------------------------------------------------===//
555 //                            ConstStructBuilder
556 //===----------------------------------------------------------------------===//
557 
558 class ConstStructBuilder {
559   CodeGenModule &CGM;
560   ConstantEmitter &Emitter;
561   ConstantAggregateBuilder &Builder;
562   CharUnits StartOffset;
563 
564 public:
565   static llvm::Constant *BuildStruct(ConstantEmitter &Emitter,
566                                      InitListExpr *ILE, QualType StructTy);
567   static llvm::Constant *BuildStruct(ConstantEmitter &Emitter,
568                                      const APValue &Value, QualType ValTy);
569   static bool UpdateStruct(ConstantEmitter &Emitter,
570                            ConstantAggregateBuilder &Const, CharUnits Offset,
571                            InitListExpr *Updater);
572 
573 private:
574   ConstStructBuilder(ConstantEmitter &Emitter,
575                      ConstantAggregateBuilder &Builder, CharUnits StartOffset)
576       : CGM(Emitter.CGM), Emitter(Emitter), Builder(Builder),
577         StartOffset(StartOffset) {}
578 
579   bool AppendField(const FieldDecl *Field, uint64_t FieldOffset,
580                    llvm::Constant *InitExpr, bool AllowOverwrite = false);
581 
582   bool AppendBytes(CharUnits FieldOffsetInChars, llvm::Constant *InitCst,
583                    bool AllowOverwrite = false);
584 
585   bool AppendBitField(const FieldDecl *Field, uint64_t FieldOffset,
586                       llvm::ConstantInt *InitExpr, bool AllowOverwrite = false);
587 
588   bool Build(InitListExpr *ILE, bool AllowOverwrite);
589   bool Build(const APValue &Val, const RecordDecl *RD, bool IsPrimaryBase,
590              const CXXRecordDecl *VTableClass, CharUnits BaseOffset);
591   llvm::Constant *Finalize(QualType Ty);
592 };
593 
594 bool ConstStructBuilder::AppendField(
595     const FieldDecl *Field, uint64_t FieldOffset, llvm::Constant *InitCst,
596     bool AllowOverwrite) {
597   const ASTContext &Context = CGM.getContext();
598 
599   CharUnits FieldOffsetInChars = Context.toCharUnitsFromBits(FieldOffset);
600 
601   return AppendBytes(FieldOffsetInChars, InitCst, AllowOverwrite);
602 }
603 
604 bool ConstStructBuilder::AppendBytes(CharUnits FieldOffsetInChars,
605                                      llvm::Constant *InitCst,
606                                      bool AllowOverwrite) {
607   return Builder.add(InitCst, StartOffset + FieldOffsetInChars, AllowOverwrite);
608 }
609 
610 bool ConstStructBuilder::AppendBitField(
611     const FieldDecl *Field, uint64_t FieldOffset, llvm::ConstantInt *CI,
612     bool AllowOverwrite) {
613   const CGRecordLayout &RL =
614       CGM.getTypes().getCGRecordLayout(Field->getParent());
615   const CGBitFieldInfo &Info = RL.getBitFieldInfo(Field);
616   llvm::APInt FieldValue = CI->getValue();
617 
618   // Promote the size of FieldValue if necessary
619   // FIXME: This should never occur, but currently it can because initializer
620   // constants are cast to bool, and because clang is not enforcing bitfield
621   // width limits.
622   if (Info.Size > FieldValue.getBitWidth())
623     FieldValue = FieldValue.zext(Info.Size);
624 
625   // Truncate the size of FieldValue to the bit field size.
626   if (Info.Size < FieldValue.getBitWidth())
627     FieldValue = FieldValue.trunc(Info.Size);
628 
629   return Builder.addBits(FieldValue,
630                          CGM.getContext().toBits(StartOffset) + FieldOffset,
631                          AllowOverwrite);
632 }
633 
634 static bool EmitDesignatedInitUpdater(ConstantEmitter &Emitter,
635                                       ConstantAggregateBuilder &Const,
636                                       CharUnits Offset, QualType Type,
637                                       InitListExpr *Updater) {
638   if (Type->isRecordType())
639     return ConstStructBuilder::UpdateStruct(Emitter, Const, Offset, Updater);
640 
641   auto CAT = Emitter.CGM.getContext().getAsConstantArrayType(Type);
642   if (!CAT)
643     return false;
644   QualType ElemType = CAT->getElementType();
645   CharUnits ElemSize = Emitter.CGM.getContext().getTypeSizeInChars(ElemType);
646   llvm::Type *ElemTy = Emitter.CGM.getTypes().ConvertTypeForMem(ElemType);
647 
648   llvm::Constant *FillC = nullptr;
649   if (Expr *Filler = Updater->getArrayFiller()) {
650     if (!isa<NoInitExpr>(Filler)) {
651       FillC = Emitter.tryEmitAbstractForMemory(Filler, ElemType);
652       if (!FillC)
653         return false;
654     }
655   }
656 
657   unsigned NumElementsToUpdate =
658       FillC ? CAT->getSize().getZExtValue() : Updater->getNumInits();
659   for (unsigned I = 0; I != NumElementsToUpdate; ++I, Offset += ElemSize) {
660     Expr *Init = nullptr;
661     if (I < Updater->getNumInits())
662       Init = Updater->getInit(I);
663 
664     if (!Init && FillC) {
665       if (!Const.add(FillC, Offset, true))
666         return false;
667     } else if (!Init || isa<NoInitExpr>(Init)) {
668       continue;
669     } else if (InitListExpr *ChildILE = dyn_cast<InitListExpr>(Init)) {
670       if (!EmitDesignatedInitUpdater(Emitter, Const, Offset, ElemType,
671                                      ChildILE))
672         return false;
673       // Attempt to reduce the array element to a single constant if necessary.
674       Const.condense(Offset, ElemTy);
675     } else {
676       llvm::Constant *Val = Emitter.tryEmitPrivateForMemory(Init, ElemType);
677       if (!Const.add(Val, Offset, true))
678         return false;
679     }
680   }
681 
682   return true;
683 }
684 
685 bool ConstStructBuilder::Build(InitListExpr *ILE, bool AllowOverwrite) {
686   RecordDecl *RD = ILE->getType()->castAs<RecordType>()->getDecl();
687   const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(RD);
688 
689   unsigned FieldNo = -1;
690   unsigned ElementNo = 0;
691 
692   // Bail out if we have base classes. We could support these, but they only
693   // arise in C++1z where we will have already constant folded most interesting
694   // cases. FIXME: There are still a few more cases we can handle this way.
695   if (auto *CXXRD = dyn_cast<CXXRecordDecl>(RD))
696     if (CXXRD->getNumBases())
697       return false;
698 
699   for (FieldDecl *Field : RD->fields()) {
700     ++FieldNo;
701 
702     // If this is a union, skip all the fields that aren't being initialized.
703     if (RD->isUnion() &&
704         !declaresSameEntity(ILE->getInitializedFieldInUnion(), Field))
705       continue;
706 
707     // Don't emit anonymous bitfields.
708     if (Field->isUnnamedBitfield())
709       continue;
710 
711     // Get the initializer.  A struct can include fields without initializers,
712     // we just use explicit null values for them.
713     Expr *Init = nullptr;
714     if (ElementNo < ILE->getNumInits())
715       Init = ILE->getInit(ElementNo++);
716     if (Init && isa<NoInitExpr>(Init))
717       continue;
718 
719     // Zero-sized fields are not emitted, but their initializers may still
720     // prevent emission of this struct as a constant.
721     if (Field->isZeroSize(CGM.getContext())) {
722       if (Init->HasSideEffects(CGM.getContext()))
723         return false;
724       continue;
725     }
726 
727     // When emitting a DesignatedInitUpdateExpr, a nested InitListExpr
728     // represents additional overwriting of our current constant value, and not
729     // a new constant to emit independently.
730     if (AllowOverwrite &&
731         (Field->getType()->isArrayType() || Field->getType()->isRecordType())) {
732       if (auto *SubILE = dyn_cast<InitListExpr>(Init)) {
733         CharUnits Offset = CGM.getContext().toCharUnitsFromBits(
734             Layout.getFieldOffset(FieldNo));
735         if (!EmitDesignatedInitUpdater(Emitter, Builder, StartOffset + Offset,
736                                        Field->getType(), SubILE))
737           return false;
738         // If we split apart the field's value, try to collapse it down to a
739         // single value now.
740         Builder.condense(StartOffset + Offset,
741                          CGM.getTypes().ConvertTypeForMem(Field->getType()));
742         continue;
743       }
744     }
745 
746     llvm::Constant *EltInit =
747         Init ? Emitter.tryEmitPrivateForMemory(Init, Field->getType())
748              : Emitter.emitNullForMemory(Field->getType());
749     if (!EltInit)
750       return false;
751 
752     if (!Field->isBitField()) {
753       // Handle non-bitfield members.
754       if (!AppendField(Field, Layout.getFieldOffset(FieldNo), EltInit,
755                        AllowOverwrite))
756         return false;
757       // After emitting a non-empty field with [[no_unique_address]], we may
758       // need to overwrite its tail padding.
759       if (Field->hasAttr<NoUniqueAddressAttr>())
760         AllowOverwrite = true;
761     } else {
762       // Otherwise we have a bitfield.
763       if (auto *CI = dyn_cast<llvm::ConstantInt>(EltInit)) {
764         if (!AppendBitField(Field, Layout.getFieldOffset(FieldNo), CI,
765                             AllowOverwrite))
766           return false;
767       } else {
768         // We are trying to initialize a bitfield with a non-trivial constant,
769         // this must require run-time code.
770         return false;
771       }
772     }
773   }
774 
775   return true;
776 }
777 
778 namespace {
779 struct BaseInfo {
780   BaseInfo(const CXXRecordDecl *Decl, CharUnits Offset, unsigned Index)
781     : Decl(Decl), Offset(Offset), Index(Index) {
782   }
783 
784   const CXXRecordDecl *Decl;
785   CharUnits Offset;
786   unsigned Index;
787 
788   bool operator<(const BaseInfo &O) const { return Offset < O.Offset; }
789 };
790 }
791 
792 bool ConstStructBuilder::Build(const APValue &Val, const RecordDecl *RD,
793                                bool IsPrimaryBase,
794                                const CXXRecordDecl *VTableClass,
795                                CharUnits Offset) {
796   const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(RD);
797 
798   if (const CXXRecordDecl *CD = dyn_cast<CXXRecordDecl>(RD)) {
799     // Add a vtable pointer, if we need one and it hasn't already been added.
800     if (Layout.hasOwnVFPtr()) {
801       llvm::Constant *VTableAddressPoint =
802           CGM.getCXXABI().getVTableAddressPointForConstExpr(
803               BaseSubobject(CD, Offset), VTableClass);
804       if (!AppendBytes(Offset, VTableAddressPoint))
805         return false;
806     }
807 
808     // Accumulate and sort bases, in order to visit them in address order, which
809     // may not be the same as declaration order.
810     SmallVector<BaseInfo, 8> Bases;
811     Bases.reserve(CD->getNumBases());
812     unsigned BaseNo = 0;
813     for (CXXRecordDecl::base_class_const_iterator Base = CD->bases_begin(),
814          BaseEnd = CD->bases_end(); Base != BaseEnd; ++Base, ++BaseNo) {
815       assert(!Base->isVirtual() && "should not have virtual bases here");
816       const CXXRecordDecl *BD = Base->getType()->getAsCXXRecordDecl();
817       CharUnits BaseOffset = Layout.getBaseClassOffset(BD);
818       Bases.push_back(BaseInfo(BD, BaseOffset, BaseNo));
819     }
820     llvm::stable_sort(Bases);
821 
822     for (unsigned I = 0, N = Bases.size(); I != N; ++I) {
823       BaseInfo &Base = Bases[I];
824 
825       bool IsPrimaryBase = Layout.getPrimaryBase() == Base.Decl;
826       Build(Val.getStructBase(Base.Index), Base.Decl, IsPrimaryBase,
827             VTableClass, Offset + Base.Offset);
828     }
829   }
830 
831   unsigned FieldNo = 0;
832   uint64_t OffsetBits = CGM.getContext().toBits(Offset);
833 
834   bool AllowOverwrite = false;
835   for (RecordDecl::field_iterator Field = RD->field_begin(),
836        FieldEnd = RD->field_end(); Field != FieldEnd; ++Field, ++FieldNo) {
837     // If this is a union, skip all the fields that aren't being initialized.
838     if (RD->isUnion() && !declaresSameEntity(Val.getUnionField(), *Field))
839       continue;
840 
841     // Don't emit anonymous bitfields or zero-sized fields.
842     if (Field->isUnnamedBitfield() || Field->isZeroSize(CGM.getContext()))
843       continue;
844 
845     // Emit the value of the initializer.
846     const APValue &FieldValue =
847       RD->isUnion() ? Val.getUnionValue() : Val.getStructField(FieldNo);
848     llvm::Constant *EltInit =
849       Emitter.tryEmitPrivateForMemory(FieldValue, Field->getType());
850     if (!EltInit)
851       return false;
852 
853     if (!Field->isBitField()) {
854       // Handle non-bitfield members.
855       if (!AppendField(*Field, Layout.getFieldOffset(FieldNo) + OffsetBits,
856                        EltInit, AllowOverwrite))
857         return false;
858       // After emitting a non-empty field with [[no_unique_address]], we may
859       // need to overwrite its tail padding.
860       if (Field->hasAttr<NoUniqueAddressAttr>())
861         AllowOverwrite = true;
862     } else {
863       // Otherwise we have a bitfield.
864       if (!AppendBitField(*Field, Layout.getFieldOffset(FieldNo) + OffsetBits,
865                           cast<llvm::ConstantInt>(EltInit), AllowOverwrite))
866         return false;
867     }
868   }
869 
870   return true;
871 }
872 
873 llvm::Constant *ConstStructBuilder::Finalize(QualType Type) {
874   Type = Type.getNonReferenceType();
875   RecordDecl *RD = Type->castAs<RecordType>()->getDecl();
876   llvm::Type *ValTy = CGM.getTypes().ConvertType(Type);
877   return Builder.build(ValTy, RD->hasFlexibleArrayMember());
878 }
879 
880 llvm::Constant *ConstStructBuilder::BuildStruct(ConstantEmitter &Emitter,
881                                                 InitListExpr *ILE,
882                                                 QualType ValTy) {
883   ConstantAggregateBuilder Const(Emitter.CGM);
884   ConstStructBuilder Builder(Emitter, Const, CharUnits::Zero());
885 
886   if (!Builder.Build(ILE, /*AllowOverwrite*/false))
887     return nullptr;
888 
889   return Builder.Finalize(ValTy);
890 }
891 
892 llvm::Constant *ConstStructBuilder::BuildStruct(ConstantEmitter &Emitter,
893                                                 const APValue &Val,
894                                                 QualType ValTy) {
895   ConstantAggregateBuilder Const(Emitter.CGM);
896   ConstStructBuilder Builder(Emitter, Const, CharUnits::Zero());
897 
898   const RecordDecl *RD = ValTy->castAs<RecordType>()->getDecl();
899   const CXXRecordDecl *CD = dyn_cast<CXXRecordDecl>(RD);
900   if (!Builder.Build(Val, RD, false, CD, CharUnits::Zero()))
901     return nullptr;
902 
903   return Builder.Finalize(ValTy);
904 }
905 
906 bool ConstStructBuilder::UpdateStruct(ConstantEmitter &Emitter,
907                                       ConstantAggregateBuilder &Const,
908                                       CharUnits Offset, InitListExpr *Updater) {
909   return ConstStructBuilder(Emitter, Const, Offset)
910       .Build(Updater, /*AllowOverwrite*/ true);
911 }
912 
913 //===----------------------------------------------------------------------===//
914 //                             ConstExprEmitter
915 //===----------------------------------------------------------------------===//
916 
917 static ConstantAddress
918 tryEmitGlobalCompoundLiteral(ConstantEmitter &emitter,
919                              const CompoundLiteralExpr *E) {
920   CodeGenModule &CGM = emitter.CGM;
921   CharUnits Align = CGM.getContext().getTypeAlignInChars(E->getType());
922   if (llvm::GlobalVariable *Addr =
923           CGM.getAddrOfConstantCompoundLiteralIfEmitted(E))
924     return ConstantAddress(Addr, Addr->getValueType(), Align);
925 
926   LangAS addressSpace = E->getType().getAddressSpace();
927   llvm::Constant *C = emitter.tryEmitForInitializer(E->getInitializer(),
928                                                     addressSpace, E->getType());
929   if (!C) {
930     assert(!E->isFileScope() &&
931            "file-scope compound literal did not have constant initializer!");
932     return ConstantAddress::invalid();
933   }
934 
935   auto GV = new llvm::GlobalVariable(
936       CGM.getModule(), C->getType(),
937       CGM.isTypeConstant(E->getType(), true, false),
938       llvm::GlobalValue::InternalLinkage, C, ".compoundliteral", nullptr,
939       llvm::GlobalVariable::NotThreadLocal,
940       CGM.getContext().getTargetAddressSpace(addressSpace));
941   emitter.finalize(GV);
942   GV->setAlignment(Align.getAsAlign());
943   CGM.setAddrOfConstantCompoundLiteral(E, GV);
944   return ConstantAddress(GV, GV->getValueType(), Align);
945 }
946 
947 static llvm::Constant *
948 EmitArrayConstant(CodeGenModule &CGM, llvm::ArrayType *DesiredType,
949                   llvm::Type *CommonElementType, unsigned ArrayBound,
950                   SmallVectorImpl<llvm::Constant *> &Elements,
951                   llvm::Constant *Filler) {
952   // Figure out how long the initial prefix of non-zero elements is.
953   unsigned NonzeroLength = ArrayBound;
954   if (Elements.size() < NonzeroLength && Filler->isNullValue())
955     NonzeroLength = Elements.size();
956   if (NonzeroLength == Elements.size()) {
957     while (NonzeroLength > 0 && Elements[NonzeroLength - 1]->isNullValue())
958       --NonzeroLength;
959   }
960 
961   if (NonzeroLength == 0)
962     return llvm::ConstantAggregateZero::get(DesiredType);
963 
964   // Add a zeroinitializer array filler if we have lots of trailing zeroes.
965   unsigned TrailingZeroes = ArrayBound - NonzeroLength;
966   if (TrailingZeroes >= 8) {
967     assert(Elements.size() >= NonzeroLength &&
968            "missing initializer for non-zero element");
969 
970     // If all the elements had the same type up to the trailing zeroes, emit a
971     // struct of two arrays (the nonzero data and the zeroinitializer).
972     if (CommonElementType && NonzeroLength >= 8) {
973       llvm::Constant *Initial = llvm::ConstantArray::get(
974           llvm::ArrayType::get(CommonElementType, NonzeroLength),
975           ArrayRef(Elements).take_front(NonzeroLength));
976       Elements.resize(2);
977       Elements[0] = Initial;
978     } else {
979       Elements.resize(NonzeroLength + 1);
980     }
981 
982     auto *FillerType =
983         CommonElementType ? CommonElementType : DesiredType->getElementType();
984     FillerType = llvm::ArrayType::get(FillerType, TrailingZeroes);
985     Elements.back() = llvm::ConstantAggregateZero::get(FillerType);
986     CommonElementType = nullptr;
987   } else if (Elements.size() != ArrayBound) {
988     // Otherwise pad to the right size with the filler if necessary.
989     Elements.resize(ArrayBound, Filler);
990     if (Filler->getType() != CommonElementType)
991       CommonElementType = nullptr;
992   }
993 
994   // If all elements have the same type, just emit an array constant.
995   if (CommonElementType)
996     return llvm::ConstantArray::get(
997         llvm::ArrayType::get(CommonElementType, ArrayBound), Elements);
998 
999   // We have mixed types. Use a packed struct.
1000   llvm::SmallVector<llvm::Type *, 16> Types;
1001   Types.reserve(Elements.size());
1002   for (llvm::Constant *Elt : Elements)
1003     Types.push_back(Elt->getType());
1004   llvm::StructType *SType =
1005       llvm::StructType::get(CGM.getLLVMContext(), Types, true);
1006   return llvm::ConstantStruct::get(SType, Elements);
1007 }
1008 
1009 // This class only needs to handle arrays, structs and unions. Outside C++11
1010 // mode, we don't currently constant fold those types.  All other types are
1011 // handled by constant folding.
1012 //
1013 // Constant folding is currently missing support for a few features supported
1014 // here: CK_ToUnion, CK_ReinterpretMemberPointer, and DesignatedInitUpdateExpr.
1015 class ConstExprEmitter :
1016   public StmtVisitor<ConstExprEmitter, llvm::Constant*, QualType> {
1017   CodeGenModule &CGM;
1018   ConstantEmitter &Emitter;
1019   llvm::LLVMContext &VMContext;
1020 public:
1021   ConstExprEmitter(ConstantEmitter &emitter)
1022     : CGM(emitter.CGM), Emitter(emitter), VMContext(CGM.getLLVMContext()) {
1023   }
1024 
1025   //===--------------------------------------------------------------------===//
1026   //                            Visitor Methods
1027   //===--------------------------------------------------------------------===//
1028 
1029   llvm::Constant *VisitStmt(Stmt *S, QualType T) {
1030     return nullptr;
1031   }
1032 
1033   llvm::Constant *VisitConstantExpr(ConstantExpr *CE, QualType T) {
1034     if (llvm::Constant *Result = Emitter.tryEmitConstantExpr(CE))
1035       return Result;
1036     return Visit(CE->getSubExpr(), T);
1037   }
1038 
1039   llvm::Constant *VisitParenExpr(ParenExpr *PE, QualType T) {
1040     return Visit(PE->getSubExpr(), T);
1041   }
1042 
1043   llvm::Constant *
1044   VisitSubstNonTypeTemplateParmExpr(SubstNonTypeTemplateParmExpr *PE,
1045                                     QualType T) {
1046     return Visit(PE->getReplacement(), T);
1047   }
1048 
1049   llvm::Constant *VisitGenericSelectionExpr(GenericSelectionExpr *GE,
1050                                             QualType T) {
1051     return Visit(GE->getResultExpr(), T);
1052   }
1053 
1054   llvm::Constant *VisitChooseExpr(ChooseExpr *CE, QualType T) {
1055     return Visit(CE->getChosenSubExpr(), T);
1056   }
1057 
1058   llvm::Constant *VisitCompoundLiteralExpr(CompoundLiteralExpr *E, QualType T) {
1059     return Visit(E->getInitializer(), T);
1060   }
1061 
1062   llvm::Constant *VisitCastExpr(CastExpr *E, QualType destType) {
1063     if (const auto *ECE = dyn_cast<ExplicitCastExpr>(E))
1064       CGM.EmitExplicitCastExprType(ECE, Emitter.CGF);
1065     Expr *subExpr = E->getSubExpr();
1066 
1067     switch (E->getCastKind()) {
1068     case CK_ToUnion: {
1069       // GCC cast to union extension
1070       assert(E->getType()->isUnionType() &&
1071              "Destination type is not union type!");
1072 
1073       auto field = E->getTargetUnionField();
1074 
1075       auto C = Emitter.tryEmitPrivateForMemory(subExpr, field->getType());
1076       if (!C) return nullptr;
1077 
1078       auto destTy = ConvertType(destType);
1079       if (C->getType() == destTy) return C;
1080 
1081       // Build a struct with the union sub-element as the first member,
1082       // and padded to the appropriate size.
1083       SmallVector<llvm::Constant*, 2> Elts;
1084       SmallVector<llvm::Type*, 2> Types;
1085       Elts.push_back(C);
1086       Types.push_back(C->getType());
1087       unsigned CurSize = CGM.getDataLayout().getTypeAllocSize(C->getType());
1088       unsigned TotalSize = CGM.getDataLayout().getTypeAllocSize(destTy);
1089 
1090       assert(CurSize <= TotalSize && "Union size mismatch!");
1091       if (unsigned NumPadBytes = TotalSize - CurSize) {
1092         llvm::Type *Ty = CGM.CharTy;
1093         if (NumPadBytes > 1)
1094           Ty = llvm::ArrayType::get(Ty, NumPadBytes);
1095 
1096         Elts.push_back(llvm::UndefValue::get(Ty));
1097         Types.push_back(Ty);
1098       }
1099 
1100       llvm::StructType *STy = llvm::StructType::get(VMContext, Types, false);
1101       return llvm::ConstantStruct::get(STy, Elts);
1102     }
1103 
1104     case CK_AddressSpaceConversion: {
1105       auto C = Emitter.tryEmitPrivate(subExpr, subExpr->getType());
1106       if (!C) return nullptr;
1107       LangAS destAS = E->getType()->getPointeeType().getAddressSpace();
1108       LangAS srcAS = subExpr->getType()->getPointeeType().getAddressSpace();
1109       llvm::Type *destTy = ConvertType(E->getType());
1110       return CGM.getTargetCodeGenInfo().performAddrSpaceCast(CGM, C, srcAS,
1111                                                              destAS, destTy);
1112     }
1113 
1114     case CK_LValueToRValue: {
1115       // We don't really support doing lvalue-to-rvalue conversions here; any
1116       // interesting conversions should be done in Evaluate().  But as a
1117       // special case, allow compound literals to support the gcc extension
1118       // allowing "struct x {int x;} x = (struct x) {};".
1119       if (auto *E = dyn_cast<CompoundLiteralExpr>(subExpr->IgnoreParens()))
1120         return Visit(E->getInitializer(), destType);
1121       return nullptr;
1122     }
1123 
1124     case CK_AtomicToNonAtomic:
1125     case CK_NonAtomicToAtomic:
1126     case CK_NoOp:
1127     case CK_ConstructorConversion:
1128       return Visit(subExpr, destType);
1129 
1130     case CK_IntToOCLSampler:
1131       llvm_unreachable("global sampler variables are not generated");
1132 
1133     case CK_Dependent: llvm_unreachable("saw dependent cast!");
1134 
1135     case CK_BuiltinFnToFnPtr:
1136       llvm_unreachable("builtin functions are handled elsewhere");
1137 
1138     case CK_ReinterpretMemberPointer:
1139     case CK_DerivedToBaseMemberPointer:
1140     case CK_BaseToDerivedMemberPointer: {
1141       auto C = Emitter.tryEmitPrivate(subExpr, subExpr->getType());
1142       if (!C) return nullptr;
1143       return CGM.getCXXABI().EmitMemberPointerConversion(E, C);
1144     }
1145 
1146     // These will never be supported.
1147     case CK_ObjCObjectLValueCast:
1148     case CK_ARCProduceObject:
1149     case CK_ARCConsumeObject:
1150     case CK_ARCReclaimReturnedObject:
1151     case CK_ARCExtendBlockObject:
1152     case CK_CopyAndAutoreleaseBlockObject:
1153       return nullptr;
1154 
1155     // These don't need to be handled here because Evaluate knows how to
1156     // evaluate them in the cases where they can be folded.
1157     case CK_BitCast:
1158     case CK_ToVoid:
1159     case CK_Dynamic:
1160     case CK_LValueBitCast:
1161     case CK_LValueToRValueBitCast:
1162     case CK_NullToMemberPointer:
1163     case CK_UserDefinedConversion:
1164     case CK_CPointerToObjCPointerCast:
1165     case CK_BlockPointerToObjCPointerCast:
1166     case CK_AnyPointerToBlockPointerCast:
1167     case CK_ArrayToPointerDecay:
1168     case CK_FunctionToPointerDecay:
1169     case CK_BaseToDerived:
1170     case CK_DerivedToBase:
1171     case CK_UncheckedDerivedToBase:
1172     case CK_MemberPointerToBoolean:
1173     case CK_VectorSplat:
1174     case CK_FloatingRealToComplex:
1175     case CK_FloatingComplexToReal:
1176     case CK_FloatingComplexToBoolean:
1177     case CK_FloatingComplexCast:
1178     case CK_FloatingComplexToIntegralComplex:
1179     case CK_IntegralRealToComplex:
1180     case CK_IntegralComplexToReal:
1181     case CK_IntegralComplexToBoolean:
1182     case CK_IntegralComplexCast:
1183     case CK_IntegralComplexToFloatingComplex:
1184     case CK_PointerToIntegral:
1185     case CK_PointerToBoolean:
1186     case CK_NullToPointer:
1187     case CK_IntegralCast:
1188     case CK_BooleanToSignedIntegral:
1189     case CK_IntegralToPointer:
1190     case CK_IntegralToBoolean:
1191     case CK_IntegralToFloating:
1192     case CK_FloatingToIntegral:
1193     case CK_FloatingToBoolean:
1194     case CK_FloatingCast:
1195     case CK_FloatingToFixedPoint:
1196     case CK_FixedPointToFloating:
1197     case CK_FixedPointCast:
1198     case CK_FixedPointToBoolean:
1199     case CK_FixedPointToIntegral:
1200     case CK_IntegralToFixedPoint:
1201     case CK_ZeroToOCLOpaqueType:
1202     case CK_MatrixCast:
1203       return nullptr;
1204     }
1205     llvm_unreachable("Invalid CastKind");
1206   }
1207 
1208   llvm::Constant *VisitCXXDefaultInitExpr(CXXDefaultInitExpr *DIE, QualType T) {
1209     // No need for a DefaultInitExprScope: we don't handle 'this' in a
1210     // constant expression.
1211     return Visit(DIE->getExpr(), T);
1212   }
1213 
1214   llvm::Constant *VisitExprWithCleanups(ExprWithCleanups *E, QualType T) {
1215     return Visit(E->getSubExpr(), T);
1216   }
1217 
1218   llvm::Constant *EmitArrayInitialization(InitListExpr *ILE, QualType T) {
1219     auto *CAT = CGM.getContext().getAsConstantArrayType(ILE->getType());
1220     assert(CAT && "can't emit array init for non-constant-bound array");
1221     unsigned NumInitElements = ILE->getNumInits();
1222     unsigned NumElements = CAT->getSize().getZExtValue();
1223 
1224     // Initialising an array requires us to automatically
1225     // initialise any elements that have not been initialised explicitly
1226     unsigned NumInitableElts = std::min(NumInitElements, NumElements);
1227 
1228     QualType EltType = CAT->getElementType();
1229 
1230     // Initialize remaining array elements.
1231     llvm::Constant *fillC = nullptr;
1232     if (Expr *filler = ILE->getArrayFiller()) {
1233       fillC = Emitter.tryEmitAbstractForMemory(filler, EltType);
1234       if (!fillC)
1235         return nullptr;
1236     }
1237 
1238     // Copy initializer elements.
1239     SmallVector<llvm::Constant*, 16> Elts;
1240     if (fillC && fillC->isNullValue())
1241       Elts.reserve(NumInitableElts + 1);
1242     else
1243       Elts.reserve(NumElements);
1244 
1245     llvm::Type *CommonElementType = nullptr;
1246     for (unsigned i = 0; i < NumInitableElts; ++i) {
1247       Expr *Init = ILE->getInit(i);
1248       llvm::Constant *C = Emitter.tryEmitPrivateForMemory(Init, EltType);
1249       if (!C)
1250         return nullptr;
1251       if (i == 0)
1252         CommonElementType = C->getType();
1253       else if (C->getType() != CommonElementType)
1254         CommonElementType = nullptr;
1255       Elts.push_back(C);
1256     }
1257 
1258     llvm::ArrayType *Desired =
1259         cast<llvm::ArrayType>(CGM.getTypes().ConvertType(ILE->getType()));
1260     return EmitArrayConstant(CGM, Desired, CommonElementType, NumElements, Elts,
1261                              fillC);
1262   }
1263 
1264   llvm::Constant *EmitRecordInitialization(InitListExpr *ILE, QualType T) {
1265     return ConstStructBuilder::BuildStruct(Emitter, ILE, T);
1266   }
1267 
1268   llvm::Constant *VisitImplicitValueInitExpr(ImplicitValueInitExpr* E,
1269                                              QualType T) {
1270     return CGM.EmitNullConstant(T);
1271   }
1272 
1273   llvm::Constant *VisitInitListExpr(InitListExpr *ILE, QualType T) {
1274     if (ILE->isTransparent())
1275       return Visit(ILE->getInit(0), T);
1276 
1277     if (ILE->getType()->isArrayType())
1278       return EmitArrayInitialization(ILE, T);
1279 
1280     if (ILE->getType()->isRecordType())
1281       return EmitRecordInitialization(ILE, T);
1282 
1283     return nullptr;
1284   }
1285 
1286   llvm::Constant *VisitDesignatedInitUpdateExpr(DesignatedInitUpdateExpr *E,
1287                                                 QualType destType) {
1288     auto C = Visit(E->getBase(), destType);
1289     if (!C)
1290       return nullptr;
1291 
1292     ConstantAggregateBuilder Const(CGM);
1293     Const.add(C, CharUnits::Zero(), false);
1294 
1295     if (!EmitDesignatedInitUpdater(Emitter, Const, CharUnits::Zero(), destType,
1296                                    E->getUpdater()))
1297       return nullptr;
1298 
1299     llvm::Type *ValTy = CGM.getTypes().ConvertType(destType);
1300     bool HasFlexibleArray = false;
1301     if (auto *RT = destType->getAs<RecordType>())
1302       HasFlexibleArray = RT->getDecl()->hasFlexibleArrayMember();
1303     return Const.build(ValTy, HasFlexibleArray);
1304   }
1305 
1306   llvm::Constant *VisitCXXConstructExpr(CXXConstructExpr *E, QualType Ty) {
1307     if (!E->getConstructor()->isTrivial())
1308       return nullptr;
1309 
1310     // Only default and copy/move constructors can be trivial.
1311     if (E->getNumArgs()) {
1312       assert(E->getNumArgs() == 1 && "trivial ctor with > 1 argument");
1313       assert(E->getConstructor()->isCopyOrMoveConstructor() &&
1314              "trivial ctor has argument but isn't a copy/move ctor");
1315 
1316       Expr *Arg = E->getArg(0);
1317       assert(CGM.getContext().hasSameUnqualifiedType(Ty, Arg->getType()) &&
1318              "argument to copy ctor is of wrong type");
1319 
1320       // Look through the temporary; it's just converting the value to an
1321       // lvalue to pass it to the constructor.
1322       if (auto *MTE = dyn_cast<MaterializeTemporaryExpr>(Arg))
1323         return Visit(MTE->getSubExpr(), Ty);
1324       // Don't try to support arbitrary lvalue-to-rvalue conversions for now.
1325       return nullptr;
1326     }
1327 
1328     return CGM.EmitNullConstant(Ty);
1329   }
1330 
1331   llvm::Constant *VisitStringLiteral(StringLiteral *E, QualType T) {
1332     // This is a string literal initializing an array in an initializer.
1333     return CGM.GetConstantArrayFromStringLiteral(E);
1334   }
1335 
1336   llvm::Constant *VisitObjCEncodeExpr(ObjCEncodeExpr *E, QualType T) {
1337     // This must be an @encode initializing an array in a static initializer.
1338     // Don't emit it as the address of the string, emit the string data itself
1339     // as an inline array.
1340     std::string Str;
1341     CGM.getContext().getObjCEncodingForType(E->getEncodedType(), Str);
1342     const ConstantArrayType *CAT = CGM.getContext().getAsConstantArrayType(T);
1343     assert(CAT && "String data not of constant array type!");
1344 
1345     // Resize the string to the right size, adding zeros at the end, or
1346     // truncating as needed.
1347     Str.resize(CAT->getSize().getZExtValue(), '\0');
1348     return llvm::ConstantDataArray::getString(VMContext, Str, false);
1349   }
1350 
1351   llvm::Constant *VisitUnaryExtension(const UnaryOperator *E, QualType T) {
1352     return Visit(E->getSubExpr(), T);
1353   }
1354 
1355   // Utility methods
1356   llvm::Type *ConvertType(QualType T) {
1357     return CGM.getTypes().ConvertType(T);
1358   }
1359 };
1360 
1361 }  // end anonymous namespace.
1362 
1363 llvm::Constant *ConstantEmitter::validateAndPopAbstract(llvm::Constant *C,
1364                                                         AbstractState saved) {
1365   Abstract = saved.OldValue;
1366 
1367   assert(saved.OldPlaceholdersSize == PlaceholderAddresses.size() &&
1368          "created a placeholder while doing an abstract emission?");
1369 
1370   // No validation necessary for now.
1371   // No cleanup to do for now.
1372   return C;
1373 }
1374 
1375 llvm::Constant *
1376 ConstantEmitter::tryEmitAbstractForInitializer(const VarDecl &D) {
1377   auto state = pushAbstract();
1378   auto C = tryEmitPrivateForVarInit(D);
1379   return validateAndPopAbstract(C, state);
1380 }
1381 
1382 llvm::Constant *
1383 ConstantEmitter::tryEmitAbstract(const Expr *E, QualType destType) {
1384   auto state = pushAbstract();
1385   auto C = tryEmitPrivate(E, destType);
1386   return validateAndPopAbstract(C, state);
1387 }
1388 
1389 llvm::Constant *
1390 ConstantEmitter::tryEmitAbstract(const APValue &value, QualType destType) {
1391   auto state = pushAbstract();
1392   auto C = tryEmitPrivate(value, destType);
1393   return validateAndPopAbstract(C, state);
1394 }
1395 
1396 llvm::Constant *ConstantEmitter::tryEmitConstantExpr(const ConstantExpr *CE) {
1397   if (!CE->hasAPValueResult())
1398     return nullptr;
1399 
1400   QualType RetType = CE->getType();
1401   if (CE->isGLValue())
1402     RetType = CGM.getContext().getLValueReferenceType(RetType);
1403 
1404   return emitAbstract(CE->getBeginLoc(), CE->getAPValueResult(), RetType);
1405 }
1406 
1407 llvm::Constant *
1408 ConstantEmitter::emitAbstract(const Expr *E, QualType destType) {
1409   auto state = pushAbstract();
1410   auto C = tryEmitPrivate(E, destType);
1411   C = validateAndPopAbstract(C, state);
1412   if (!C) {
1413     CGM.Error(E->getExprLoc(),
1414               "internal error: could not emit constant value \"abstractly\"");
1415     C = CGM.EmitNullConstant(destType);
1416   }
1417   return C;
1418 }
1419 
1420 llvm::Constant *
1421 ConstantEmitter::emitAbstract(SourceLocation loc, const APValue &value,
1422                               QualType destType) {
1423   auto state = pushAbstract();
1424   auto C = tryEmitPrivate(value, destType);
1425   C = validateAndPopAbstract(C, state);
1426   if (!C) {
1427     CGM.Error(loc,
1428               "internal error: could not emit constant value \"abstractly\"");
1429     C = CGM.EmitNullConstant(destType);
1430   }
1431   return C;
1432 }
1433 
1434 llvm::Constant *ConstantEmitter::tryEmitForInitializer(const VarDecl &D) {
1435   initializeNonAbstract(D.getType().getAddressSpace());
1436   return markIfFailed(tryEmitPrivateForVarInit(D));
1437 }
1438 
1439 llvm::Constant *ConstantEmitter::tryEmitForInitializer(const Expr *E,
1440                                                        LangAS destAddrSpace,
1441                                                        QualType destType) {
1442   initializeNonAbstract(destAddrSpace);
1443   return markIfFailed(tryEmitPrivateForMemory(E, destType));
1444 }
1445 
1446 llvm::Constant *ConstantEmitter::emitForInitializer(const APValue &value,
1447                                                     LangAS destAddrSpace,
1448                                                     QualType destType) {
1449   initializeNonAbstract(destAddrSpace);
1450   auto C = tryEmitPrivateForMemory(value, destType);
1451   assert(C && "couldn't emit constant value non-abstractly?");
1452   return C;
1453 }
1454 
1455 llvm::GlobalValue *ConstantEmitter::getCurrentAddrPrivate() {
1456   assert(!Abstract && "cannot get current address for abstract constant");
1457 
1458 
1459 
1460   // Make an obviously ill-formed global that should blow up compilation
1461   // if it survives.
1462   auto global = new llvm::GlobalVariable(CGM.getModule(), CGM.Int8Ty, true,
1463                                          llvm::GlobalValue::PrivateLinkage,
1464                                          /*init*/ nullptr,
1465                                          /*name*/ "",
1466                                          /*before*/ nullptr,
1467                                          llvm::GlobalVariable::NotThreadLocal,
1468                                          CGM.getContext().getTargetAddressSpace(DestAddressSpace));
1469 
1470   PlaceholderAddresses.push_back(std::make_pair(nullptr, global));
1471 
1472   return global;
1473 }
1474 
1475 void ConstantEmitter::registerCurrentAddrPrivate(llvm::Constant *signal,
1476                                            llvm::GlobalValue *placeholder) {
1477   assert(!PlaceholderAddresses.empty());
1478   assert(PlaceholderAddresses.back().first == nullptr);
1479   assert(PlaceholderAddresses.back().second == placeholder);
1480   PlaceholderAddresses.back().first = signal;
1481 }
1482 
1483 namespace {
1484   struct ReplacePlaceholders {
1485     CodeGenModule &CGM;
1486 
1487     /// The base address of the global.
1488     llvm::Constant *Base;
1489     llvm::Type *BaseValueTy = nullptr;
1490 
1491     /// The placeholder addresses that were registered during emission.
1492     llvm::DenseMap<llvm::Constant*, llvm::GlobalVariable*> PlaceholderAddresses;
1493 
1494     /// The locations of the placeholder signals.
1495     llvm::DenseMap<llvm::GlobalVariable*, llvm::Constant*> Locations;
1496 
1497     /// The current index stack.  We use a simple unsigned stack because
1498     /// we assume that placeholders will be relatively sparse in the
1499     /// initializer, but we cache the index values we find just in case.
1500     llvm::SmallVector<unsigned, 8> Indices;
1501     llvm::SmallVector<llvm::Constant*, 8> IndexValues;
1502 
1503     ReplacePlaceholders(CodeGenModule &CGM, llvm::Constant *base,
1504                         ArrayRef<std::pair<llvm::Constant*,
1505                                            llvm::GlobalVariable*>> addresses)
1506         : CGM(CGM), Base(base),
1507           PlaceholderAddresses(addresses.begin(), addresses.end()) {
1508     }
1509 
1510     void replaceInInitializer(llvm::Constant *init) {
1511       // Remember the type of the top-most initializer.
1512       BaseValueTy = init->getType();
1513 
1514       // Initialize the stack.
1515       Indices.push_back(0);
1516       IndexValues.push_back(nullptr);
1517 
1518       // Recurse into the initializer.
1519       findLocations(init);
1520 
1521       // Check invariants.
1522       assert(IndexValues.size() == Indices.size() && "mismatch");
1523       assert(Indices.size() == 1 && "didn't pop all indices");
1524 
1525       // Do the replacement; this basically invalidates 'init'.
1526       assert(Locations.size() == PlaceholderAddresses.size() &&
1527              "missed a placeholder?");
1528 
1529       // We're iterating over a hashtable, so this would be a source of
1530       // non-determinism in compiler output *except* that we're just
1531       // messing around with llvm::Constant structures, which never itself
1532       // does anything that should be visible in compiler output.
1533       for (auto &entry : Locations) {
1534         assert(entry.first->getParent() == nullptr && "not a placeholder!");
1535         entry.first->replaceAllUsesWith(entry.second);
1536         entry.first->eraseFromParent();
1537       }
1538     }
1539 
1540   private:
1541     void findLocations(llvm::Constant *init) {
1542       // Recurse into aggregates.
1543       if (auto agg = dyn_cast<llvm::ConstantAggregate>(init)) {
1544         for (unsigned i = 0, e = agg->getNumOperands(); i != e; ++i) {
1545           Indices.push_back(i);
1546           IndexValues.push_back(nullptr);
1547 
1548           findLocations(agg->getOperand(i));
1549 
1550           IndexValues.pop_back();
1551           Indices.pop_back();
1552         }
1553         return;
1554       }
1555 
1556       // Otherwise, check for registered constants.
1557       while (true) {
1558         auto it = PlaceholderAddresses.find(init);
1559         if (it != PlaceholderAddresses.end()) {
1560           setLocation(it->second);
1561           break;
1562         }
1563 
1564         // Look through bitcasts or other expressions.
1565         if (auto expr = dyn_cast<llvm::ConstantExpr>(init)) {
1566           init = expr->getOperand(0);
1567         } else {
1568           break;
1569         }
1570       }
1571     }
1572 
1573     void setLocation(llvm::GlobalVariable *placeholder) {
1574       assert(!Locations.contains(placeholder) &&
1575              "already found location for placeholder!");
1576 
1577       // Lazily fill in IndexValues with the values from Indices.
1578       // We do this in reverse because we should always have a strict
1579       // prefix of indices from the start.
1580       assert(Indices.size() == IndexValues.size());
1581       for (size_t i = Indices.size() - 1; i != size_t(-1); --i) {
1582         if (IndexValues[i]) {
1583 #ifndef NDEBUG
1584           for (size_t j = 0; j != i + 1; ++j) {
1585             assert(IndexValues[j] &&
1586                    isa<llvm::ConstantInt>(IndexValues[j]) &&
1587                    cast<llvm::ConstantInt>(IndexValues[j])->getZExtValue()
1588                      == Indices[j]);
1589           }
1590 #endif
1591           break;
1592         }
1593 
1594         IndexValues[i] = llvm::ConstantInt::get(CGM.Int32Ty, Indices[i]);
1595       }
1596 
1597       // Form a GEP and then bitcast to the placeholder type so that the
1598       // replacement will succeed.
1599       llvm::Constant *location =
1600         llvm::ConstantExpr::getInBoundsGetElementPtr(BaseValueTy,
1601                                                      Base, IndexValues);
1602       location = llvm::ConstantExpr::getBitCast(location,
1603                                                 placeholder->getType());
1604 
1605       Locations.insert({placeholder, location});
1606     }
1607   };
1608 }
1609 
1610 void ConstantEmitter::finalize(llvm::GlobalVariable *global) {
1611   assert(InitializedNonAbstract &&
1612          "finalizing emitter that was used for abstract emission?");
1613   assert(!Finalized && "finalizing emitter multiple times");
1614   assert(global->getInitializer());
1615 
1616   // Note that we might also be Failed.
1617   Finalized = true;
1618 
1619   if (!PlaceholderAddresses.empty()) {
1620     ReplacePlaceholders(CGM, global, PlaceholderAddresses)
1621       .replaceInInitializer(global->getInitializer());
1622     PlaceholderAddresses.clear(); // satisfy
1623   }
1624 }
1625 
1626 ConstantEmitter::~ConstantEmitter() {
1627   assert((!InitializedNonAbstract || Finalized || Failed) &&
1628          "not finalized after being initialized for non-abstract emission");
1629   assert(PlaceholderAddresses.empty() && "unhandled placeholders");
1630 }
1631 
1632 static QualType getNonMemoryType(CodeGenModule &CGM, QualType type) {
1633   if (auto AT = type->getAs<AtomicType>()) {
1634     return CGM.getContext().getQualifiedType(AT->getValueType(),
1635                                              type.getQualifiers());
1636   }
1637   return type;
1638 }
1639 
1640 llvm::Constant *ConstantEmitter::tryEmitPrivateForVarInit(const VarDecl &D) {
1641   // Make a quick check if variable can be default NULL initialized
1642   // and avoid going through rest of code which may do, for c++11,
1643   // initialization of memory to all NULLs.
1644   if (!D.hasLocalStorage()) {
1645     QualType Ty = CGM.getContext().getBaseElementType(D.getType());
1646     if (Ty->isRecordType())
1647       if (const CXXConstructExpr *E =
1648           dyn_cast_or_null<CXXConstructExpr>(D.getInit())) {
1649         const CXXConstructorDecl *CD = E->getConstructor();
1650         if (CD->isTrivial() && CD->isDefaultConstructor())
1651           return CGM.EmitNullConstant(D.getType());
1652       }
1653   }
1654   InConstantContext = D.hasConstantInitialization();
1655 
1656   QualType destType = D.getType();
1657   const Expr *E = D.getInit();
1658   assert(E && "No initializer to emit");
1659 
1660   if (!destType->isReferenceType()) {
1661     QualType nonMemoryDestType = getNonMemoryType(CGM, destType);
1662     if (llvm::Constant *C = ConstExprEmitter(*this).Visit(const_cast<Expr *>(E),
1663                                                           nonMemoryDestType))
1664       return emitForMemory(C, destType);
1665   }
1666 
1667   // Try to emit the initializer.  Note that this can allow some things that
1668   // are not allowed by tryEmitPrivateForMemory alone.
1669   if (APValue *value = D.evaluateValue())
1670     return tryEmitPrivateForMemory(*value, destType);
1671 
1672   return nullptr;
1673 }
1674 
1675 llvm::Constant *
1676 ConstantEmitter::tryEmitAbstractForMemory(const Expr *E, QualType destType) {
1677   auto nonMemoryDestType = getNonMemoryType(CGM, destType);
1678   auto C = tryEmitAbstract(E, nonMemoryDestType);
1679   return (C ? emitForMemory(C, destType) : nullptr);
1680 }
1681 
1682 llvm::Constant *
1683 ConstantEmitter::tryEmitAbstractForMemory(const APValue &value,
1684                                           QualType destType) {
1685   auto nonMemoryDestType = getNonMemoryType(CGM, destType);
1686   auto C = tryEmitAbstract(value, nonMemoryDestType);
1687   return (C ? emitForMemory(C, destType) : nullptr);
1688 }
1689 
1690 llvm::Constant *ConstantEmitter::tryEmitPrivateForMemory(const Expr *E,
1691                                                          QualType destType) {
1692   auto nonMemoryDestType = getNonMemoryType(CGM, destType);
1693   llvm::Constant *C = tryEmitPrivate(E, nonMemoryDestType);
1694   return (C ? emitForMemory(C, destType) : nullptr);
1695 }
1696 
1697 llvm::Constant *ConstantEmitter::tryEmitPrivateForMemory(const APValue &value,
1698                                                          QualType destType) {
1699   auto nonMemoryDestType = getNonMemoryType(CGM, destType);
1700   auto C = tryEmitPrivate(value, nonMemoryDestType);
1701   return (C ? emitForMemory(C, destType) : nullptr);
1702 }
1703 
1704 llvm::Constant *ConstantEmitter::emitForMemory(CodeGenModule &CGM,
1705                                                llvm::Constant *C,
1706                                                QualType destType) {
1707   // For an _Atomic-qualified constant, we may need to add tail padding.
1708   if (auto AT = destType->getAs<AtomicType>()) {
1709     QualType destValueType = AT->getValueType();
1710     C = emitForMemory(CGM, C, destValueType);
1711 
1712     uint64_t innerSize = CGM.getContext().getTypeSize(destValueType);
1713     uint64_t outerSize = CGM.getContext().getTypeSize(destType);
1714     if (innerSize == outerSize)
1715       return C;
1716 
1717     assert(innerSize < outerSize && "emitted over-large constant for atomic");
1718     llvm::Constant *elts[] = {
1719       C,
1720       llvm::ConstantAggregateZero::get(
1721           llvm::ArrayType::get(CGM.Int8Ty, (outerSize - innerSize) / 8))
1722     };
1723     return llvm::ConstantStruct::getAnon(elts);
1724   }
1725 
1726   // Zero-extend bool.
1727   if (C->getType()->isIntegerTy(1) && !destType->isBitIntType()) {
1728     llvm::Type *boolTy = CGM.getTypes().ConvertTypeForMem(destType);
1729     return llvm::ConstantExpr::getZExt(C, boolTy);
1730   }
1731 
1732   return C;
1733 }
1734 
1735 llvm::Constant *ConstantEmitter::tryEmitPrivate(const Expr *E,
1736                                                 QualType destType) {
1737   assert(!destType->isVoidType() && "can't emit a void constant");
1738 
1739   if (!destType->isReferenceType())
1740     if (llvm::Constant *C =
1741             ConstExprEmitter(*this).Visit(const_cast<Expr *>(E), destType))
1742       return C;
1743 
1744   Expr::EvalResult Result;
1745 
1746   bool Success = false;
1747 
1748   if (destType->isReferenceType())
1749     Success = E->EvaluateAsLValue(Result, CGM.getContext());
1750   else
1751     Success = E->EvaluateAsRValue(Result, CGM.getContext(), InConstantContext);
1752 
1753   if (Success && !Result.HasSideEffects)
1754     return tryEmitPrivate(Result.Val, destType);
1755 
1756   return nullptr;
1757 }
1758 
1759 llvm::Constant *CodeGenModule::getNullPointer(llvm::PointerType *T, QualType QT) {
1760   return getTargetCodeGenInfo().getNullPointer(*this, T, QT);
1761 }
1762 
1763 namespace {
1764 /// A struct which can be used to peephole certain kinds of finalization
1765 /// that normally happen during l-value emission.
1766 struct ConstantLValue {
1767   llvm::Constant *Value;
1768   bool HasOffsetApplied;
1769 
1770   /*implicit*/ ConstantLValue(llvm::Constant *value,
1771                               bool hasOffsetApplied = false)
1772     : Value(value), HasOffsetApplied(hasOffsetApplied) {}
1773 
1774   /*implicit*/ ConstantLValue(ConstantAddress address)
1775     : ConstantLValue(address.getPointer()) {}
1776 };
1777 
1778 /// A helper class for emitting constant l-values.
1779 class ConstantLValueEmitter : public ConstStmtVisitor<ConstantLValueEmitter,
1780                                                       ConstantLValue> {
1781   CodeGenModule &CGM;
1782   ConstantEmitter &Emitter;
1783   const APValue &Value;
1784   QualType DestType;
1785 
1786   // Befriend StmtVisitorBase so that we don't have to expose Visit*.
1787   friend StmtVisitorBase;
1788 
1789 public:
1790   ConstantLValueEmitter(ConstantEmitter &emitter, const APValue &value,
1791                         QualType destType)
1792     : CGM(emitter.CGM), Emitter(emitter), Value(value), DestType(destType) {}
1793 
1794   llvm::Constant *tryEmit();
1795 
1796 private:
1797   llvm::Constant *tryEmitAbsolute(llvm::Type *destTy);
1798   ConstantLValue tryEmitBase(const APValue::LValueBase &base);
1799 
1800   ConstantLValue VisitStmt(const Stmt *S) { return nullptr; }
1801   ConstantLValue VisitConstantExpr(const ConstantExpr *E);
1802   ConstantLValue VisitCompoundLiteralExpr(const CompoundLiteralExpr *E);
1803   ConstantLValue VisitStringLiteral(const StringLiteral *E);
1804   ConstantLValue VisitObjCBoxedExpr(const ObjCBoxedExpr *E);
1805   ConstantLValue VisitObjCEncodeExpr(const ObjCEncodeExpr *E);
1806   ConstantLValue VisitObjCStringLiteral(const ObjCStringLiteral *E);
1807   ConstantLValue VisitPredefinedExpr(const PredefinedExpr *E);
1808   ConstantLValue VisitAddrLabelExpr(const AddrLabelExpr *E);
1809   ConstantLValue VisitCallExpr(const CallExpr *E);
1810   ConstantLValue VisitBlockExpr(const BlockExpr *E);
1811   ConstantLValue VisitCXXTypeidExpr(const CXXTypeidExpr *E);
1812   ConstantLValue VisitMaterializeTemporaryExpr(
1813                                          const MaterializeTemporaryExpr *E);
1814 
1815   bool hasNonZeroOffset() const {
1816     return !Value.getLValueOffset().isZero();
1817   }
1818 
1819   /// Return the value offset.
1820   llvm::Constant *getOffset() {
1821     return llvm::ConstantInt::get(CGM.Int64Ty,
1822                                   Value.getLValueOffset().getQuantity());
1823   }
1824 
1825   /// Apply the value offset to the given constant.
1826   llvm::Constant *applyOffset(llvm::Constant *C) {
1827     if (!hasNonZeroOffset())
1828       return C;
1829 
1830     llvm::Type *origPtrTy = C->getType();
1831     C = llvm::ConstantExpr::getGetElementPtr(CGM.Int8Ty, C, getOffset());
1832     C = llvm::ConstantExpr::getPointerCast(C, origPtrTy);
1833     return C;
1834   }
1835 };
1836 
1837 }
1838 
1839 llvm::Constant *ConstantLValueEmitter::tryEmit() {
1840   const APValue::LValueBase &base = Value.getLValueBase();
1841 
1842   // The destination type should be a pointer or reference
1843   // type, but it might also be a cast thereof.
1844   //
1845   // FIXME: the chain of casts required should be reflected in the APValue.
1846   // We need this in order to correctly handle things like a ptrtoint of a
1847   // non-zero null pointer and addrspace casts that aren't trivially
1848   // represented in LLVM IR.
1849   auto destTy = CGM.getTypes().ConvertTypeForMem(DestType);
1850   assert(isa<llvm::IntegerType>(destTy) || isa<llvm::PointerType>(destTy));
1851 
1852   // If there's no base at all, this is a null or absolute pointer,
1853   // possibly cast back to an integer type.
1854   if (!base) {
1855     return tryEmitAbsolute(destTy);
1856   }
1857 
1858   // Otherwise, try to emit the base.
1859   ConstantLValue result = tryEmitBase(base);
1860 
1861   // If that failed, we're done.
1862   llvm::Constant *value = result.Value;
1863   if (!value) return nullptr;
1864 
1865   // Apply the offset if necessary and not already done.
1866   if (!result.HasOffsetApplied) {
1867     value = applyOffset(value);
1868   }
1869 
1870   // Convert to the appropriate type; this could be an lvalue for
1871   // an integer.  FIXME: performAddrSpaceCast
1872   if (isa<llvm::PointerType>(destTy))
1873     return llvm::ConstantExpr::getPointerCast(value, destTy);
1874 
1875   return llvm::ConstantExpr::getPtrToInt(value, destTy);
1876 }
1877 
1878 /// Try to emit an absolute l-value, such as a null pointer or an integer
1879 /// bitcast to pointer type.
1880 llvm::Constant *
1881 ConstantLValueEmitter::tryEmitAbsolute(llvm::Type *destTy) {
1882   // If we're producing a pointer, this is easy.
1883   auto destPtrTy = cast<llvm::PointerType>(destTy);
1884   if (Value.isNullPointer()) {
1885     // FIXME: integer offsets from non-zero null pointers.
1886     return CGM.getNullPointer(destPtrTy, DestType);
1887   }
1888 
1889   // Convert the integer to a pointer-sized integer before converting it
1890   // to a pointer.
1891   // FIXME: signedness depends on the original integer type.
1892   auto intptrTy = CGM.getDataLayout().getIntPtrType(destPtrTy);
1893   llvm::Constant *C;
1894   C = llvm::ConstantExpr::getIntegerCast(getOffset(), intptrTy,
1895                                          /*isSigned*/ false);
1896   C = llvm::ConstantExpr::getIntToPtr(C, destPtrTy);
1897   return C;
1898 }
1899 
1900 ConstantLValue
1901 ConstantLValueEmitter::tryEmitBase(const APValue::LValueBase &base) {
1902   // Handle values.
1903   if (const ValueDecl *D = base.dyn_cast<const ValueDecl*>()) {
1904     // The constant always points to the canonical declaration. We want to look
1905     // at properties of the most recent declaration at the point of emission.
1906     D = cast<ValueDecl>(D->getMostRecentDecl());
1907 
1908     if (D->hasAttr<WeakRefAttr>())
1909       return CGM.GetWeakRefReference(D).getPointer();
1910 
1911     if (auto FD = dyn_cast<FunctionDecl>(D))
1912       return CGM.GetAddrOfFunction(FD);
1913 
1914     if (auto VD = dyn_cast<VarDecl>(D)) {
1915       // We can never refer to a variable with local storage.
1916       if (!VD->hasLocalStorage()) {
1917         if (VD->isFileVarDecl() || VD->hasExternalStorage())
1918           return CGM.GetAddrOfGlobalVar(VD);
1919 
1920         if (VD->isLocalVarDecl()) {
1921           return CGM.getOrCreateStaticVarDecl(
1922               *VD, CGM.getLLVMLinkageVarDefinition(VD));
1923         }
1924       }
1925     }
1926 
1927     if (auto *GD = dyn_cast<MSGuidDecl>(D))
1928       return CGM.GetAddrOfMSGuidDecl(GD);
1929 
1930     if (auto *GCD = dyn_cast<UnnamedGlobalConstantDecl>(D))
1931       return CGM.GetAddrOfUnnamedGlobalConstantDecl(GCD);
1932 
1933     if (auto *TPO = dyn_cast<TemplateParamObjectDecl>(D))
1934       return CGM.GetAddrOfTemplateParamObject(TPO);
1935 
1936     return nullptr;
1937   }
1938 
1939   // Handle typeid(T).
1940   if (TypeInfoLValue TI = base.dyn_cast<TypeInfoLValue>())
1941     return CGM.GetAddrOfRTTIDescriptor(QualType(TI.getType(), 0));
1942 
1943   // Otherwise, it must be an expression.
1944   return Visit(base.get<const Expr*>());
1945 }
1946 
1947 ConstantLValue
1948 ConstantLValueEmitter::VisitConstantExpr(const ConstantExpr *E) {
1949   if (llvm::Constant *Result = Emitter.tryEmitConstantExpr(E))
1950     return Result;
1951   return Visit(E->getSubExpr());
1952 }
1953 
1954 ConstantLValue
1955 ConstantLValueEmitter::VisitCompoundLiteralExpr(const CompoundLiteralExpr *E) {
1956   ConstantEmitter CompoundLiteralEmitter(CGM, Emitter.CGF);
1957   CompoundLiteralEmitter.setInConstantContext(Emitter.isInConstantContext());
1958   return tryEmitGlobalCompoundLiteral(CompoundLiteralEmitter, E);
1959 }
1960 
1961 ConstantLValue
1962 ConstantLValueEmitter::VisitStringLiteral(const StringLiteral *E) {
1963   return CGM.GetAddrOfConstantStringFromLiteral(E);
1964 }
1965 
1966 ConstantLValue
1967 ConstantLValueEmitter::VisitObjCEncodeExpr(const ObjCEncodeExpr *E) {
1968   return CGM.GetAddrOfConstantStringFromObjCEncode(E);
1969 }
1970 
1971 static ConstantLValue emitConstantObjCStringLiteral(const StringLiteral *S,
1972                                                     QualType T,
1973                                                     CodeGenModule &CGM) {
1974   auto C = CGM.getObjCRuntime().GenerateConstantString(S);
1975   return C.withElementType(CGM.getTypes().ConvertTypeForMem(T));
1976 }
1977 
1978 ConstantLValue
1979 ConstantLValueEmitter::VisitObjCStringLiteral(const ObjCStringLiteral *E) {
1980   return emitConstantObjCStringLiteral(E->getString(), E->getType(), CGM);
1981 }
1982 
1983 ConstantLValue
1984 ConstantLValueEmitter::VisitObjCBoxedExpr(const ObjCBoxedExpr *E) {
1985   assert(E->isExpressibleAsConstantInitializer() &&
1986          "this boxed expression can't be emitted as a compile-time constant");
1987   auto *SL = cast<StringLiteral>(E->getSubExpr()->IgnoreParenCasts());
1988   return emitConstantObjCStringLiteral(SL, E->getType(), CGM);
1989 }
1990 
1991 ConstantLValue
1992 ConstantLValueEmitter::VisitPredefinedExpr(const PredefinedExpr *E) {
1993   return CGM.GetAddrOfConstantStringFromLiteral(E->getFunctionName());
1994 }
1995 
1996 ConstantLValue
1997 ConstantLValueEmitter::VisitAddrLabelExpr(const AddrLabelExpr *E) {
1998   assert(Emitter.CGF && "Invalid address of label expression outside function");
1999   llvm::Constant *Ptr = Emitter.CGF->GetAddrOfLabel(E->getLabel());
2000   Ptr = llvm::ConstantExpr::getBitCast(Ptr,
2001                                    CGM.getTypes().ConvertType(E->getType()));
2002   return Ptr;
2003 }
2004 
2005 ConstantLValue
2006 ConstantLValueEmitter::VisitCallExpr(const CallExpr *E) {
2007   unsigned builtin = E->getBuiltinCallee();
2008   if (builtin == Builtin::BI__builtin_function_start)
2009     return CGM.GetFunctionStart(
2010         E->getArg(0)->getAsBuiltinConstantDeclRef(CGM.getContext()));
2011   if (builtin != Builtin::BI__builtin___CFStringMakeConstantString &&
2012       builtin != Builtin::BI__builtin___NSStringMakeConstantString)
2013     return nullptr;
2014 
2015   auto literal = cast<StringLiteral>(E->getArg(0)->IgnoreParenCasts());
2016   if (builtin == Builtin::BI__builtin___NSStringMakeConstantString) {
2017     return CGM.getObjCRuntime().GenerateConstantString(literal);
2018   } else {
2019     // FIXME: need to deal with UCN conversion issues.
2020     return CGM.GetAddrOfConstantCFString(literal);
2021   }
2022 }
2023 
2024 ConstantLValue
2025 ConstantLValueEmitter::VisitBlockExpr(const BlockExpr *E) {
2026   StringRef functionName;
2027   if (auto CGF = Emitter.CGF)
2028     functionName = CGF->CurFn->getName();
2029   else
2030     functionName = "global";
2031 
2032   return CGM.GetAddrOfGlobalBlock(E, functionName);
2033 }
2034 
2035 ConstantLValue
2036 ConstantLValueEmitter::VisitCXXTypeidExpr(const CXXTypeidExpr *E) {
2037   QualType T;
2038   if (E->isTypeOperand())
2039     T = E->getTypeOperand(CGM.getContext());
2040   else
2041     T = E->getExprOperand()->getType();
2042   return CGM.GetAddrOfRTTIDescriptor(T);
2043 }
2044 
2045 ConstantLValue
2046 ConstantLValueEmitter::VisitMaterializeTemporaryExpr(
2047                                             const MaterializeTemporaryExpr *E) {
2048   assert(E->getStorageDuration() == SD_Static);
2049   SmallVector<const Expr *, 2> CommaLHSs;
2050   SmallVector<SubobjectAdjustment, 2> Adjustments;
2051   const Expr *Inner =
2052       E->getSubExpr()->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments);
2053   return CGM.GetAddrOfGlobalTemporary(E, Inner);
2054 }
2055 
2056 llvm::Constant *ConstantEmitter::tryEmitPrivate(const APValue &Value,
2057                                                 QualType DestType) {
2058   switch (Value.getKind()) {
2059   case APValue::None:
2060   case APValue::Indeterminate:
2061     // Out-of-lifetime and indeterminate values can be modeled as 'undef'.
2062     return llvm::UndefValue::get(CGM.getTypes().ConvertType(DestType));
2063   case APValue::LValue:
2064     return ConstantLValueEmitter(*this, Value, DestType).tryEmit();
2065   case APValue::Int:
2066     return llvm::ConstantInt::get(CGM.getLLVMContext(), Value.getInt());
2067   case APValue::FixedPoint:
2068     return llvm::ConstantInt::get(CGM.getLLVMContext(),
2069                                   Value.getFixedPoint().getValue());
2070   case APValue::ComplexInt: {
2071     llvm::Constant *Complex[2];
2072 
2073     Complex[0] = llvm::ConstantInt::get(CGM.getLLVMContext(),
2074                                         Value.getComplexIntReal());
2075     Complex[1] = llvm::ConstantInt::get(CGM.getLLVMContext(),
2076                                         Value.getComplexIntImag());
2077 
2078     // FIXME: the target may want to specify that this is packed.
2079     llvm::StructType *STy =
2080         llvm::StructType::get(Complex[0]->getType(), Complex[1]->getType());
2081     return llvm::ConstantStruct::get(STy, Complex);
2082   }
2083   case APValue::Float: {
2084     const llvm::APFloat &Init = Value.getFloat();
2085     if (&Init.getSemantics() == &llvm::APFloat::IEEEhalf() &&
2086         !CGM.getContext().getLangOpts().NativeHalfType &&
2087         CGM.getContext().getTargetInfo().useFP16ConversionIntrinsics())
2088       return llvm::ConstantInt::get(CGM.getLLVMContext(),
2089                                     Init.bitcastToAPInt());
2090     else
2091       return llvm::ConstantFP::get(CGM.getLLVMContext(), Init);
2092   }
2093   case APValue::ComplexFloat: {
2094     llvm::Constant *Complex[2];
2095 
2096     Complex[0] = llvm::ConstantFP::get(CGM.getLLVMContext(),
2097                                        Value.getComplexFloatReal());
2098     Complex[1] = llvm::ConstantFP::get(CGM.getLLVMContext(),
2099                                        Value.getComplexFloatImag());
2100 
2101     // FIXME: the target may want to specify that this is packed.
2102     llvm::StructType *STy =
2103         llvm::StructType::get(Complex[0]->getType(), Complex[1]->getType());
2104     return llvm::ConstantStruct::get(STy, Complex);
2105   }
2106   case APValue::Vector: {
2107     unsigned NumElts = Value.getVectorLength();
2108     SmallVector<llvm::Constant *, 4> Inits(NumElts);
2109 
2110     for (unsigned I = 0; I != NumElts; ++I) {
2111       const APValue &Elt = Value.getVectorElt(I);
2112       if (Elt.isInt())
2113         Inits[I] = llvm::ConstantInt::get(CGM.getLLVMContext(), Elt.getInt());
2114       else if (Elt.isFloat())
2115         Inits[I] = llvm::ConstantFP::get(CGM.getLLVMContext(), Elt.getFloat());
2116       else
2117         llvm_unreachable("unsupported vector element type");
2118     }
2119     return llvm::ConstantVector::get(Inits);
2120   }
2121   case APValue::AddrLabelDiff: {
2122     const AddrLabelExpr *LHSExpr = Value.getAddrLabelDiffLHS();
2123     const AddrLabelExpr *RHSExpr = Value.getAddrLabelDiffRHS();
2124     llvm::Constant *LHS = tryEmitPrivate(LHSExpr, LHSExpr->getType());
2125     llvm::Constant *RHS = tryEmitPrivate(RHSExpr, RHSExpr->getType());
2126     if (!LHS || !RHS) return nullptr;
2127 
2128     // Compute difference
2129     llvm::Type *ResultType = CGM.getTypes().ConvertType(DestType);
2130     LHS = llvm::ConstantExpr::getPtrToInt(LHS, CGM.IntPtrTy);
2131     RHS = llvm::ConstantExpr::getPtrToInt(RHS, CGM.IntPtrTy);
2132     llvm::Constant *AddrLabelDiff = llvm::ConstantExpr::getSub(LHS, RHS);
2133 
2134     // LLVM is a bit sensitive about the exact format of the
2135     // address-of-label difference; make sure to truncate after
2136     // the subtraction.
2137     return llvm::ConstantExpr::getTruncOrBitCast(AddrLabelDiff, ResultType);
2138   }
2139   case APValue::Struct:
2140   case APValue::Union:
2141     return ConstStructBuilder::BuildStruct(*this, Value, DestType);
2142   case APValue::Array: {
2143     const ArrayType *ArrayTy = CGM.getContext().getAsArrayType(DestType);
2144     unsigned NumElements = Value.getArraySize();
2145     unsigned NumInitElts = Value.getArrayInitializedElts();
2146 
2147     // Emit array filler, if there is one.
2148     llvm::Constant *Filler = nullptr;
2149     if (Value.hasArrayFiller()) {
2150       Filler = tryEmitAbstractForMemory(Value.getArrayFiller(),
2151                                         ArrayTy->getElementType());
2152       if (!Filler)
2153         return nullptr;
2154     }
2155 
2156     // Emit initializer elements.
2157     SmallVector<llvm::Constant*, 16> Elts;
2158     if (Filler && Filler->isNullValue())
2159       Elts.reserve(NumInitElts + 1);
2160     else
2161       Elts.reserve(NumElements);
2162 
2163     llvm::Type *CommonElementType = nullptr;
2164     for (unsigned I = 0; I < NumInitElts; ++I) {
2165       llvm::Constant *C = tryEmitPrivateForMemory(
2166           Value.getArrayInitializedElt(I), ArrayTy->getElementType());
2167       if (!C) return nullptr;
2168 
2169       if (I == 0)
2170         CommonElementType = C->getType();
2171       else if (C->getType() != CommonElementType)
2172         CommonElementType = nullptr;
2173       Elts.push_back(C);
2174     }
2175 
2176     llvm::ArrayType *Desired =
2177         cast<llvm::ArrayType>(CGM.getTypes().ConvertType(DestType));
2178 
2179     // Fix the type of incomplete arrays if the initializer isn't empty.
2180     if (DestType->isIncompleteArrayType() && !Elts.empty())
2181       Desired = llvm::ArrayType::get(Desired->getElementType(), Elts.size());
2182 
2183     return EmitArrayConstant(CGM, Desired, CommonElementType, NumElements, Elts,
2184                              Filler);
2185   }
2186   case APValue::MemberPointer:
2187     return CGM.getCXXABI().EmitMemberPointer(Value, DestType);
2188   }
2189   llvm_unreachable("Unknown APValue kind");
2190 }
2191 
2192 llvm::GlobalVariable *CodeGenModule::getAddrOfConstantCompoundLiteralIfEmitted(
2193     const CompoundLiteralExpr *E) {
2194   return EmittedCompoundLiterals.lookup(E);
2195 }
2196 
2197 void CodeGenModule::setAddrOfConstantCompoundLiteral(
2198     const CompoundLiteralExpr *CLE, llvm::GlobalVariable *GV) {
2199   bool Ok = EmittedCompoundLiterals.insert(std::make_pair(CLE, GV)).second;
2200   (void)Ok;
2201   assert(Ok && "CLE has already been emitted!");
2202 }
2203 
2204 ConstantAddress
2205 CodeGenModule::GetAddrOfConstantCompoundLiteral(const CompoundLiteralExpr *E) {
2206   assert(E->isFileScope() && "not a file-scope compound literal expr");
2207   ConstantEmitter emitter(*this);
2208   return tryEmitGlobalCompoundLiteral(emitter, E);
2209 }
2210 
2211 llvm::Constant *
2212 CodeGenModule::getMemberPointerConstant(const UnaryOperator *uo) {
2213   // Member pointer constants always have a very particular form.
2214   const MemberPointerType *type = cast<MemberPointerType>(uo->getType());
2215   const ValueDecl *decl = cast<DeclRefExpr>(uo->getSubExpr())->getDecl();
2216 
2217   // A member function pointer.
2218   if (const CXXMethodDecl *method = dyn_cast<CXXMethodDecl>(decl))
2219     return getCXXABI().EmitMemberFunctionPointer(method);
2220 
2221   // Otherwise, a member data pointer.
2222   uint64_t fieldOffset = getContext().getFieldOffset(decl);
2223   CharUnits chars = getContext().toCharUnitsFromBits((int64_t) fieldOffset);
2224   return getCXXABI().EmitMemberDataPointer(type, chars);
2225 }
2226 
2227 static llvm::Constant *EmitNullConstantForBase(CodeGenModule &CGM,
2228                                                llvm::Type *baseType,
2229                                                const CXXRecordDecl *base);
2230 
2231 static llvm::Constant *EmitNullConstant(CodeGenModule &CGM,
2232                                         const RecordDecl *record,
2233                                         bool asCompleteObject) {
2234   const CGRecordLayout &layout = CGM.getTypes().getCGRecordLayout(record);
2235   llvm::StructType *structure =
2236     (asCompleteObject ? layout.getLLVMType()
2237                       : layout.getBaseSubobjectLLVMType());
2238 
2239   unsigned numElements = structure->getNumElements();
2240   std::vector<llvm::Constant *> elements(numElements);
2241 
2242   auto CXXR = dyn_cast<CXXRecordDecl>(record);
2243   // Fill in all the bases.
2244   if (CXXR) {
2245     for (const auto &I : CXXR->bases()) {
2246       if (I.isVirtual()) {
2247         // Ignore virtual bases; if we're laying out for a complete
2248         // object, we'll lay these out later.
2249         continue;
2250       }
2251 
2252       const CXXRecordDecl *base =
2253         cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
2254 
2255       // Ignore empty bases.
2256       if (base->isEmpty() ||
2257           CGM.getContext().getASTRecordLayout(base).getNonVirtualSize()
2258               .isZero())
2259         continue;
2260 
2261       unsigned fieldIndex = layout.getNonVirtualBaseLLVMFieldNo(base);
2262       llvm::Type *baseType = structure->getElementType(fieldIndex);
2263       elements[fieldIndex] = EmitNullConstantForBase(CGM, baseType, base);
2264     }
2265   }
2266 
2267   // Fill in all the fields.
2268   for (const auto *Field : record->fields()) {
2269     // Fill in non-bitfields. (Bitfields always use a zero pattern, which we
2270     // will fill in later.)
2271     if (!Field->isBitField() && !Field->isZeroSize(CGM.getContext())) {
2272       unsigned fieldIndex = layout.getLLVMFieldNo(Field);
2273       elements[fieldIndex] = CGM.EmitNullConstant(Field->getType());
2274     }
2275 
2276     // For unions, stop after the first named field.
2277     if (record->isUnion()) {
2278       if (Field->getIdentifier())
2279         break;
2280       if (const auto *FieldRD = Field->getType()->getAsRecordDecl())
2281         if (FieldRD->findFirstNamedDataMember())
2282           break;
2283     }
2284   }
2285 
2286   // Fill in the virtual bases, if we're working with the complete object.
2287   if (CXXR && asCompleteObject) {
2288     for (const auto &I : CXXR->vbases()) {
2289       const CXXRecordDecl *base =
2290         cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
2291 
2292       // Ignore empty bases.
2293       if (base->isEmpty())
2294         continue;
2295 
2296       unsigned fieldIndex = layout.getVirtualBaseIndex(base);
2297 
2298       // We might have already laid this field out.
2299       if (elements[fieldIndex]) continue;
2300 
2301       llvm::Type *baseType = structure->getElementType(fieldIndex);
2302       elements[fieldIndex] = EmitNullConstantForBase(CGM, baseType, base);
2303     }
2304   }
2305 
2306   // Now go through all other fields and zero them out.
2307   for (unsigned i = 0; i != numElements; ++i) {
2308     if (!elements[i])
2309       elements[i] = llvm::Constant::getNullValue(structure->getElementType(i));
2310   }
2311 
2312   return llvm::ConstantStruct::get(structure, elements);
2313 }
2314 
2315 /// Emit the null constant for a base subobject.
2316 static llvm::Constant *EmitNullConstantForBase(CodeGenModule &CGM,
2317                                                llvm::Type *baseType,
2318                                                const CXXRecordDecl *base) {
2319   const CGRecordLayout &baseLayout = CGM.getTypes().getCGRecordLayout(base);
2320 
2321   // Just zero out bases that don't have any pointer to data members.
2322   if (baseLayout.isZeroInitializableAsBase())
2323     return llvm::Constant::getNullValue(baseType);
2324 
2325   // Otherwise, we can just use its null constant.
2326   return EmitNullConstant(CGM, base, /*asCompleteObject=*/false);
2327 }
2328 
2329 llvm::Constant *ConstantEmitter::emitNullForMemory(CodeGenModule &CGM,
2330                                                    QualType T) {
2331   return emitForMemory(CGM, CGM.EmitNullConstant(T), T);
2332 }
2333 
2334 llvm::Constant *CodeGenModule::EmitNullConstant(QualType T) {
2335   if (T->getAs<PointerType>())
2336     return getNullPointer(
2337         cast<llvm::PointerType>(getTypes().ConvertTypeForMem(T)), T);
2338 
2339   if (getTypes().isZeroInitializable(T))
2340     return llvm::Constant::getNullValue(getTypes().ConvertTypeForMem(T));
2341 
2342   if (const ConstantArrayType *CAT = Context.getAsConstantArrayType(T)) {
2343     llvm::ArrayType *ATy =
2344       cast<llvm::ArrayType>(getTypes().ConvertTypeForMem(T));
2345 
2346     QualType ElementTy = CAT->getElementType();
2347 
2348     llvm::Constant *Element =
2349       ConstantEmitter::emitNullForMemory(*this, ElementTy);
2350     unsigned NumElements = CAT->getSize().getZExtValue();
2351     SmallVector<llvm::Constant *, 8> Array(NumElements, Element);
2352     return llvm::ConstantArray::get(ATy, Array);
2353   }
2354 
2355   if (const RecordType *RT = T->getAs<RecordType>())
2356     return ::EmitNullConstant(*this, RT->getDecl(), /*complete object*/ true);
2357 
2358   assert(T->isMemberDataPointerType() &&
2359          "Should only see pointers to data members here!");
2360 
2361   return getCXXABI().EmitNullMemberPointer(T->castAs<MemberPointerType>());
2362 }
2363 
2364 llvm::Constant *
2365 CodeGenModule::EmitNullConstantForBase(const CXXRecordDecl *Record) {
2366   return ::EmitNullConstant(*this, Record, false);
2367 }
2368