contrib/llvm/tools/clang/lib/CodeGen/CGExprConstant.cpp

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