contrib/llvm-project/clang/lib/CodeGen/CGExprConstant.cpp

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