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 "CodeGenModule.h"
  16 #include "CGCXXABI.h"
  17 #include "CGObjCRuntime.h"
  18 #include "CGRecordLayout.h"
  19 #include "clang/AST/APValue.h"
  20 #include "clang/AST/ASTContext.h"
  21 #include "clang/AST/RecordLayout.h"
  22 #include "clang/AST/StmtVisitor.h"
  23 #include "clang/Basic/Builtins.h"
  24 #include "llvm/Constants.h"
  25 #include "llvm/Function.h"
  26 #include "llvm/GlobalVariable.h"
  27 #include "llvm/Target/TargetData.h"
  28 using namespace clang;
  29 using namespace CodeGen;
  30
  31 //===----------------------------------------------------------------------===//
  32 //                            ConstStructBuilder
  33 //===----------------------------------------------------------------------===//
  34
  35 namespace {
  36 class ConstStructBuilder {
  37   CodeGenModule &CGM;
  38   CodeGenFunction *CGF;
  39
  40   bool Packed;
  41   unsigned NextFieldOffsetInBytes;
  42   unsigned LLVMStructAlignment;
  43   std::vector<llvm::Constant *> Elements;
  44 public:
  45   static llvm::Constant *BuildStruct(CodeGenModule &CGM, CodeGenFunction *CGF,
  46                                      InitListExpr *ILE);
  47
  48 private:
  49   ConstStructBuilder(CodeGenModule &CGM, CodeGenFunction *CGF)
  50     : CGM(CGM), CGF(CGF), Packed(false), NextFieldOffsetInBytes(0),
  51     LLVMStructAlignment(1) { }
  52
  53   bool AppendField(const FieldDecl *Field, uint64_t FieldOffset,
  54                    llvm::Constant *InitExpr);
  55
  56   void AppendBitField(const FieldDecl *Field, uint64_t FieldOffset,
  57                       llvm::ConstantInt *InitExpr);
  58
  59   void AppendPadding(uint64_t NumBytes);
  60
  61   void AppendTailPadding(uint64_t RecordSize);
  62
  63   void ConvertStructToPacked();
  64
  65   bool Build(InitListExpr *ILE);
  66
  67   unsigned getAlignment(const llvm::Constant *C) const {
  68     if (Packed)  return 1;
  69     return CGM.getTargetData().getABITypeAlignment(C->getType());
  70   }
  71
  72   uint64_t getSizeInBytes(const llvm::Constant *C) const {
  73     return CGM.getTargetData().getTypeAllocSize(C->getType());
  74   }
  75 };
  76
  77 bool ConstStructBuilder::
  78 AppendField(const FieldDecl *Field, uint64_t FieldOffset,
  79             llvm::Constant *InitCst) {
  80   uint64_t FieldOffsetInBytes = FieldOffset / 8;
  81
  82   assert(NextFieldOffsetInBytes <= FieldOffsetInBytes
  83          && "Field offset mismatch!");
  84
  85   unsigned FieldAlignment = getAlignment(InitCst);
  86
  87   // Round up the field offset to the alignment of the field type.
  88   uint64_t AlignedNextFieldOffsetInBytes =
  89     llvm::RoundUpToAlignment(NextFieldOffsetInBytes, FieldAlignment);
  90
  91   if (AlignedNextFieldOffsetInBytes > FieldOffsetInBytes) {
  92     assert(!Packed && "Alignment is wrong even with a packed struct!");
  93
  94     // Convert the struct to a packed struct.
  95     ConvertStructToPacked();
  96
  97     AlignedNextFieldOffsetInBytes = NextFieldOffsetInBytes;
  98   }
  99
 100   if (AlignedNextFieldOffsetInBytes < FieldOffsetInBytes) {
 101     // We need to append padding.
 102     AppendPadding(FieldOffsetInBytes - NextFieldOffsetInBytes);
 103
 104     assert(NextFieldOffsetInBytes == FieldOffsetInBytes &&
 105            "Did not add enough padding!");
 106
 107     AlignedNextFieldOffsetInBytes = NextFieldOffsetInBytes;
 108   }
 109
 110   // Add the field.
 111   Elements.push_back(InitCst);
 112   NextFieldOffsetInBytes = AlignedNextFieldOffsetInBytes +
 113                              getSizeInBytes(InitCst);
 114
 115   if (Packed)
 116     assert(LLVMStructAlignment == 1 && "Packed struct not byte-aligned!");
 117   else
 118     LLVMStructAlignment = std::max(LLVMStructAlignment, FieldAlignment);
 119
 120   return true;
 121 }
 122
 123 void ConstStructBuilder::AppendBitField(const FieldDecl *Field,
 124                                         uint64_t FieldOffset,
 125                                         llvm::ConstantInt *CI) {
 126   if (FieldOffset > NextFieldOffsetInBytes * 8) {
 127     // We need to add padding.
 128     uint64_t NumBytes =
 129       llvm::RoundUpToAlignment(FieldOffset -
 130                                NextFieldOffsetInBytes * 8, 8) / 8;
 131
 132     AppendPadding(NumBytes);
 133   }
 134
 135   uint64_t FieldSize =
 136     Field->getBitWidth()->EvaluateAsInt(CGM.getContext()).getZExtValue();
 137
 138   llvm::APInt FieldValue = CI->getValue();
 139
 140   // Promote the size of FieldValue if necessary
 141   // FIXME: This should never occur, but currently it can because initializer
 142   // constants are cast to bool, and because clang is not enforcing bitfield
 143   // width limits.
 144   if (FieldSize > FieldValue.getBitWidth())
 145     FieldValue = FieldValue.zext(FieldSize);
 146
 147   // Truncate the size of FieldValue to the bit field size.
 148   if (FieldSize < FieldValue.getBitWidth())
 149     FieldValue = FieldValue.trunc(FieldSize);
 150
 151   if (FieldOffset < NextFieldOffsetInBytes * 8) {
 152     // Either part of the field or the entire field can go into the previous
 153     // byte.
 154     assert(!Elements.empty() && "Elements can't be empty!");
 155
 156     unsigned BitsInPreviousByte =
 157       NextFieldOffsetInBytes * 8 - FieldOffset;
 158
 159     bool FitsCompletelyInPreviousByte =
 160       BitsInPreviousByte >= FieldValue.getBitWidth();
 161
 162     llvm::APInt Tmp = FieldValue;
 163
 164     if (!FitsCompletelyInPreviousByte) {
 165       unsigned NewFieldWidth = FieldSize - BitsInPreviousByte;
 166
 167       if (CGM.getTargetData().isBigEndian()) {
 168         Tmp = Tmp.lshr(NewFieldWidth);
 169         Tmp = Tmp.trunc(BitsInPreviousByte);
 170
 171         // We want the remaining high bits.
 172         FieldValue = FieldValue.trunc(NewFieldWidth);
 173       } else {
 174         Tmp = Tmp.trunc(BitsInPreviousByte);
 175
 176         // We want the remaining low bits.
 177         FieldValue = FieldValue.lshr(BitsInPreviousByte);
 178         FieldValue = FieldValue.trunc(NewFieldWidth);
 179       }
 180     }
 181
 182     Tmp = Tmp.zext(8);
 183     if (CGM.getTargetData().isBigEndian()) {
 184       if (FitsCompletelyInPreviousByte)
 185         Tmp = Tmp.shl(BitsInPreviousByte - FieldValue.getBitWidth());
 186     } else {
 187       Tmp = Tmp.shl(8 - BitsInPreviousByte);
 188     }
 189
 190     // 'or' in the bits that go into the previous byte.
 191     llvm::Value *LastElt = Elements.back();
 192     if (llvm::ConstantInt *Val = dyn_cast<llvm::ConstantInt>(LastElt))
 193       Tmp |= Val->getValue();
 194     else {
 195       assert(isa<llvm::UndefValue>(LastElt));
 196       // If there is an undef field that we're adding to, it can either be a
 197       // scalar undef (in which case, we just replace it with our field) or it
 198       // is an array.  If it is an array, we have to pull one byte off the
 199       // array so that the other undef bytes stay around.
 200       if (!isa<llvm::IntegerType>(LastElt->getType())) {
 201         // The undef padding will be a multibyte array, create a new smaller
 202         // padding and then an hole for our i8 to get plopped into.
 203         assert(isa<llvm::ArrayType>(LastElt->getType()) &&
 204                "Expected array padding of undefs");
 205         const llvm::ArrayType *AT = cast<llvm::ArrayType>(LastElt->getType());
 206         assert(AT->getElementType()->isIntegerTy(8) &&
 207                AT->getNumElements() != 0 &&
 208                "Expected non-empty array padding of undefs");
 209
 210         // Remove the padding array.
 211         NextFieldOffsetInBytes -= AT->getNumElements();
 212         Elements.pop_back();
 213
 214         // Add the padding back in two chunks.
 215         AppendPadding(AT->getNumElements()-1);
 216         AppendPadding(1);
 217         assert(isa<llvm::UndefValue>(Elements.back()) &&
 218                Elements.back()->getType()->isIntegerTy(8) &&
 219                "Padding addition didn't work right");
 220       }
 221     }
 222
 223     Elements.back() = llvm::ConstantInt::get(CGM.getLLVMContext(), Tmp);
 224
 225     if (FitsCompletelyInPreviousByte)
 226       return;
 227   }
 228
 229   while (FieldValue.getBitWidth() > 8) {
 230     llvm::APInt Tmp;
 231
 232     if (CGM.getTargetData().isBigEndian()) {
 233       // We want the high bits.
 234       Tmp = FieldValue.lshr(Tmp.getBitWidth() - 8).trunc(8);
 235     } else {
 236       // We want the low bits.
 237       Tmp = FieldValue.trunc(8);
 238
 239       FieldValue = FieldValue.lshr(8);
 240     }
 241
 242     Elements.push_back(llvm::ConstantInt::get(CGM.getLLVMContext(), Tmp));
 243     NextFieldOffsetInBytes++;
 244
 245     FieldValue = FieldValue.trunc(FieldValue.getBitWidth() - 8);
 246   }
 247
 248   assert(FieldValue.getBitWidth() > 0 &&
 249          "Should have at least one bit left!");
 250   assert(FieldValue.getBitWidth() <= 8 &&
 251          "Should not have more than a byte left!");
 252
 253   if (FieldValue.getBitWidth() < 8) {
 254     if (CGM.getTargetData().isBigEndian()) {
 255       unsigned BitWidth = FieldValue.getBitWidth();
 256
 257       FieldValue = FieldValue.zext(8) << (8 - BitWidth);
 258     } else
 259       FieldValue = FieldValue.zext(8);
 260   }
 261
 262   // Append the last element.
 263   Elements.push_back(llvm::ConstantInt::get(CGM.getLLVMContext(),
 264                                             FieldValue));
 265   NextFieldOffsetInBytes++;
 266 }
 267
 268 void ConstStructBuilder::AppendPadding(uint64_t NumBytes) {
 269   if (!NumBytes)
 270     return;
 271
 272   const llvm::Type *Ty = llvm::Type::getInt8Ty(CGM.getLLVMContext());
 273   if (NumBytes > 1)
 274     Ty = llvm::ArrayType::get(Ty, NumBytes);
 275
 276   llvm::Constant *C = llvm::UndefValue::get(Ty);
 277   Elements.push_back(C);
 278   assert(getAlignment(C) == 1 && "Padding must have 1 byte alignment!");
 279
 280   NextFieldOffsetInBytes += getSizeInBytes(C);
 281 }
 282
 283 void ConstStructBuilder::AppendTailPadding(uint64_t RecordSize) {
 284   assert(RecordSize % 8 == 0 && "Invalid record size!");
 285
 286   uint64_t RecordSizeInBytes = RecordSize / 8;
 287   assert(NextFieldOffsetInBytes <= RecordSizeInBytes && "Size mismatch!");
 288
 289   unsigned NumPadBytes = RecordSizeInBytes - NextFieldOffsetInBytes;
 290   AppendPadding(NumPadBytes);
 291 }
 292
 293 void ConstStructBuilder::ConvertStructToPacked() {
 294   std::vector<llvm::Constant *> PackedElements;
 295   uint64_t ElementOffsetInBytes = 0;
 296
 297   for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
 298     llvm::Constant *C = Elements[i];
 299
 300     unsigned ElementAlign =
 301       CGM.getTargetData().getABITypeAlignment(C->getType());
 302     uint64_t AlignedElementOffsetInBytes =
 303       llvm::RoundUpToAlignment(ElementOffsetInBytes, ElementAlign);
 304
 305     if (AlignedElementOffsetInBytes > ElementOffsetInBytes) {
 306       // We need some padding.
 307       uint64_t NumBytes =
 308         AlignedElementOffsetInBytes - ElementOffsetInBytes;
 309
 310       const llvm::Type *Ty = llvm::Type::getInt8Ty(CGM.getLLVMContext());
 311       if (NumBytes > 1)
 312         Ty = llvm::ArrayType::get(Ty, NumBytes);
 313
 314       llvm::Constant *Padding = llvm::UndefValue::get(Ty);
 315       PackedElements.push_back(Padding);
 316       ElementOffsetInBytes += getSizeInBytes(Padding);
 317     }
 318
 319     PackedElements.push_back(C);
 320     ElementOffsetInBytes += getSizeInBytes(C);
 321   }
 322
 323   assert(ElementOffsetInBytes == NextFieldOffsetInBytes &&
 324          "Packing the struct changed its size!");
 325
 326   Elements = PackedElements;
 327   LLVMStructAlignment = 1;
 328   Packed = true;
 329 }
 330
 331 bool ConstStructBuilder::Build(InitListExpr *ILE) {
 332   RecordDecl *RD = ILE->getType()->getAs<RecordType>()->getDecl();
 333   const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(RD);
 334
 335   unsigned FieldNo = 0;
 336   unsigned ElementNo = 0;
 337   for (RecordDecl::field_iterator Field = RD->field_begin(),
 338        FieldEnd = RD->field_end(); Field != FieldEnd; ++Field, ++FieldNo) {
 339
 340     // If this is a union, skip all the fields that aren't being initialized.
 341     if (RD->isUnion() && ILE->getInitializedFieldInUnion() != *Field)
 342       continue;
 343
 344     // Don't emit anonymous bitfields, they just affect layout.
 345     if (Field->isBitField() && !Field->getIdentifier())
 346       continue;
 347
 348     // Get the initializer.  A struct can include fields without initializers,
 349     // we just use explicit null values for them.
 350     llvm::Constant *EltInit;
 351     if (ElementNo < ILE->getNumInits())
 352       EltInit = CGM.EmitConstantExpr(ILE->getInit(ElementNo++),
 353                                      Field->getType(), CGF);
 354     else
 355       EltInit = CGM.EmitNullConstant(Field->getType());
 356
 357     if (!EltInit)
 358       return false;
 359
 360     if (!Field->isBitField()) {
 361       // Handle non-bitfield members.
 362       if (!AppendField(*Field, Layout.getFieldOffset(FieldNo), EltInit))
 363         return false;
 364     } else {
 365       // Otherwise we have a bitfield.
 366       AppendBitField(*Field, Layout.getFieldOffset(FieldNo),
 367                      cast<llvm::ConstantInt>(EltInit));
 368     }
 369   }
 370
 371   uint64_t LayoutSizeInBytes = Layout.getSize() / 8;
 372
 373   if (NextFieldOffsetInBytes > LayoutSizeInBytes) {
 374     // If the struct is bigger than the size of the record type,
 375     // we must have a flexible array member at the end.
 376     assert(RD->hasFlexibleArrayMember() &&
 377            "Must have flexible array member if struct is bigger than type!");
 378
 379     // No tail padding is necessary.
 380     return true;
 381   }
 382
 383   uint64_t LLVMSizeInBytes = llvm::RoundUpToAlignment(NextFieldOffsetInBytes,
 384                                                       LLVMStructAlignment);
 385
 386   // Check if we need to convert the struct to a packed struct.
 387   if (NextFieldOffsetInBytes <= LayoutSizeInBytes &&
 388       LLVMSizeInBytes > LayoutSizeInBytes) {
 389     assert(!Packed && "Size mismatch!");
 390
 391     ConvertStructToPacked();
 392     assert(NextFieldOffsetInBytes <= LayoutSizeInBytes &&
 393            "Converting to packed did not help!");
 394   }
 395
 396   // Append tail padding if necessary.
 397   AppendTailPadding(Layout.getSize());
 398
 399   assert(Layout.getSize() / 8 == NextFieldOffsetInBytes &&
 400          "Tail padding mismatch!");
 401
 402   return true;
 403 }
 404
 405 llvm::Constant *ConstStructBuilder::
 406   BuildStruct(CodeGenModule &CGM, CodeGenFunction *CGF, InitListExpr *ILE) {
 407   ConstStructBuilder Builder(CGM, CGF);
 408
 409   if (!Builder.Build(ILE))
 410     return 0;
 411
 412   llvm::Constant *Result =
 413   llvm::ConstantStruct::get(CGM.getLLVMContext(),
 414                             Builder.Elements, Builder.Packed);
 415
 416   assert(llvm::RoundUpToAlignment(Builder.NextFieldOffsetInBytes,
 417                                   Builder.getAlignment(Result)) ==
 418          Builder.getSizeInBytes(Result) && "Size mismatch!");
 419
 420   return Result;
 421 }
 422
 423
 424 //===----------------------------------------------------------------------===//
 425 //                             ConstExprEmitter
 426 //===----------------------------------------------------------------------===//
 427
 428 class ConstExprEmitter :
 429   public StmtVisitor<ConstExprEmitter, llvm::Constant*> {
 430   CodeGenModule &CGM;
 431   CodeGenFunction *CGF;
 432   llvm::LLVMContext &VMContext;
 433 public:
 434   ConstExprEmitter(CodeGenModule &cgm, CodeGenFunction *cgf)
 435     : CGM(cgm), CGF(cgf), VMContext(cgm.getLLVMContext()) {
 436   }
 437
 438   //===--------------------------------------------------------------------===//
 439   //                            Visitor Methods
 440   //===--------------------------------------------------------------------===//
 441
 442   llvm::Constant *VisitStmt(Stmt *S) {
 443     return 0;
 444   }
 445
 446   llvm::Constant *VisitParenExpr(ParenExpr *PE) {
 447     return Visit(PE->getSubExpr());
 448   }
 449
 450   llvm::Constant *VisitCompoundLiteralExpr(CompoundLiteralExpr *E) {
 451     return Visit(E->getInitializer());
 452   }
 453
 454   llvm::Constant *VisitUnaryAddrOf(UnaryOperator *E) {
 455     if (const MemberPointerType *MPT =
 456           E->getType()->getAs<MemberPointerType>()) {
 457       DeclRefExpr *DRE = cast<DeclRefExpr>(E->getSubExpr());
 458       NamedDecl *ND = DRE->getDecl();
 459       if (MPT->isMemberFunctionPointer())
 460         return CGM.getCXXABI().EmitMemberPointer(cast<CXXMethodDecl>(ND));
 461       else
 462         return CGM.getCXXABI().EmitMemberPointer(cast<FieldDecl>(ND));
 463     }
 464
 465     return 0;
 466   }
 467
 468   llvm::Constant *VisitBinSub(BinaryOperator *E) {
 469     // This must be a pointer/pointer subtraction.  This only happens for
 470     // address of label.
 471     if (!isa<AddrLabelExpr>(E->getLHS()->IgnoreParenNoopCasts(CGM.getContext())) ||
 472        !isa<AddrLabelExpr>(E->getRHS()->IgnoreParenNoopCasts(CGM.getContext())))
 473       return 0;
 474
 475     llvm::Constant *LHS = CGM.EmitConstantExpr(E->getLHS(),
 476                                                E->getLHS()->getType(), CGF);
 477     llvm::Constant *RHS = CGM.EmitConstantExpr(E->getRHS(),
 478                                                E->getRHS()->getType(), CGF);
 479
 480     const llvm::Type *ResultType = ConvertType(E->getType());
 481     LHS = llvm::ConstantExpr::getPtrToInt(LHS, ResultType);
 482     RHS = llvm::ConstantExpr::getPtrToInt(RHS, ResultType);
 483
 484     // No need to divide by element size, since addr of label is always void*,
 485     // which has size 1 in GNUish.
 486     return llvm::ConstantExpr::getSub(LHS, RHS);
 487   }
 488
 489   llvm::Constant *VisitCastExpr(CastExpr* E) {
 490     switch (E->getCastKind()) {
 491     case CK_ToUnion: {
 492       // GCC cast to union extension
 493       assert(E->getType()->isUnionType() &&
 494              "Destination type is not union type!");
 495       const llvm::Type *Ty = ConvertType(E->getType());
 496       Expr *SubExpr = E->getSubExpr();
 497
 498       llvm::Constant *C =
 499         CGM.EmitConstantExpr(SubExpr, SubExpr->getType(), CGF);
 500       if (!C)
 501         return 0;
 502
 503       // Build a struct with the union sub-element as the first member,
 504       // and padded to the appropriate size
 505       std::vector<llvm::Constant*> Elts;
 506       std::vector<const llvm::Type*> Types;
 507       Elts.push_back(C);
 508       Types.push_back(C->getType());
 509       unsigned CurSize = CGM.getTargetData().getTypeAllocSize(C->getType());
 510       unsigned TotalSize = CGM.getTargetData().getTypeAllocSize(Ty);
 511
 512       assert(CurSize <= TotalSize && "Union size mismatch!");
 513       if (unsigned NumPadBytes = TotalSize - CurSize) {
 514         const llvm::Type *Ty = llvm::Type::getInt8Ty(VMContext);
 515         if (NumPadBytes > 1)
 516           Ty = llvm::ArrayType::get(Ty, NumPadBytes);
 517
 518         Elts.push_back(llvm::UndefValue::get(Ty));
 519         Types.push_back(Ty);
 520       }
 521
 522       llvm::StructType* STy =
 523         llvm::StructType::get(C->getType()->getContext(), Types, false);
 524       return llvm::ConstantStruct::get(STy, Elts);
 525     }
 526     case CK_NullToMemberPointer: {
 527       const MemberPointerType *MPT = E->getType()->getAs<MemberPointerType>();
 528       return CGM.getCXXABI().EmitNullMemberPointer(MPT);
 529     }
 530
 531     case CK_BaseToDerivedMemberPointer: {
 532       Expr *SubExpr = E->getSubExpr();
 533       llvm::Constant *C =
 534         CGM.EmitConstantExpr(SubExpr, SubExpr->getType(), CGF);
 535       if (!C) return 0;
 536
 537       return CGM.getCXXABI().EmitMemberPointerConversion(C, E);
 538     }
 539
 540     case CK_BitCast:
 541       // This must be a member function pointer cast.
 542       return Visit(E->getSubExpr());
 543
 544     default: {
 545       // FIXME: This should be handled by the CK_NoOp cast kind.
 546       // Explicit and implicit no-op casts
 547       QualType Ty = E->getType(), SubTy = E->getSubExpr()->getType();
 548       if (CGM.getContext().hasSameUnqualifiedType(Ty, SubTy))
 549         return Visit(E->getSubExpr());
 550
 551       // Handle integer->integer casts for address-of-label differences.
 552       if (Ty->isIntegerType() && SubTy->isIntegerType() &&
 553           CGF) {
 554         llvm::Value *Src = Visit(E->getSubExpr());
 555         if (Src == 0) return 0;
 556
 557         // Use EmitScalarConversion to perform the conversion.
 558         return cast<llvm::Constant>(CGF->EmitScalarConversion(Src, SubTy, Ty));
 559       }
 560
 561       return 0;
 562     }
 563     }
 564   }
 565
 566   llvm::Constant *VisitCXXDefaultArgExpr(CXXDefaultArgExpr *DAE) {
 567     return Visit(DAE->getExpr());
 568   }
 569
 570   llvm::Constant *EmitArrayInitialization(InitListExpr *ILE) {
 571     unsigned NumInitElements = ILE->getNumInits();
 572     if (NumInitElements == 1 &&
 573         (isa<StringLiteral>(ILE->getInit(0)) ||
 574          isa<ObjCEncodeExpr>(ILE->getInit(0))))
 575       return Visit(ILE->getInit(0));
 576
 577     std::vector<llvm::Constant*> Elts;
 578     const llvm::ArrayType *AType =
 579         cast<llvm::ArrayType>(ConvertType(ILE->getType()));
 580     const llvm::Type *ElemTy = AType->getElementType();
 581     unsigned NumElements = AType->getNumElements();
 582
 583     // Initialising an array requires us to automatically
 584     // initialise any elements that have not been initialised explicitly
 585     unsigned NumInitableElts = std::min(NumInitElements, NumElements);
 586
 587     // Copy initializer elements.
 588     unsigned i = 0;
 589     bool RewriteType = false;
 590     for (; i < NumInitableElts; ++i) {
 591       Expr *Init = ILE->getInit(i);
 592       llvm::Constant *C = CGM.EmitConstantExpr(Init, Init->getType(), CGF);
 593       if (!C)
 594         return 0;
 595       RewriteType |= (C->getType() != ElemTy);
 596       Elts.push_back(C);
 597     }
 598
 599     // Initialize remaining array elements.
 600     // FIXME: This doesn't handle member pointers correctly!
 601     for (; i < NumElements; ++i)
 602       Elts.push_back(llvm::Constant::getNullValue(ElemTy));
 603
 604     if (RewriteType) {
 605       // FIXME: Try to avoid packing the array
 606       std::vector<const llvm::Type*> Types;
 607       for (unsigned i = 0; i < Elts.size(); ++i)
 608         Types.push_back(Elts[i]->getType());
 609       const llvm::StructType *SType = llvm::StructType::get(AType->getContext(),
 610                                                             Types, true);
 611       return llvm::ConstantStruct::get(SType, Elts);
 612     }
 613
 614     return llvm::ConstantArray::get(AType, Elts);
 615   }
 616
 617   llvm::Constant *EmitStructInitialization(InitListExpr *ILE) {
 618     return ConstStructBuilder::BuildStruct(CGM, CGF, ILE);
 619   }
 620
 621   llvm::Constant *EmitUnionInitialization(InitListExpr *ILE) {
 622     return ConstStructBuilder::BuildStruct(CGM, CGF, ILE);
 623   }
 624
 625   llvm::Constant *VisitImplicitValueInitExpr(ImplicitValueInitExpr* E) {
 626     return CGM.EmitNullConstant(E->getType());
 627   }
 628
 629   llvm::Constant *VisitInitListExpr(InitListExpr *ILE) {
 630     if (ILE->getType()->isScalarType()) {
 631       // We have a scalar in braces. Just use the first element.
 632       if (ILE->getNumInits() > 0) {
 633         Expr *Init = ILE->getInit(0);
 634         return CGM.EmitConstantExpr(Init, Init->getType(), CGF);
 635       }
 636       return CGM.EmitNullConstant(ILE->getType());
 637     }
 638
 639     if (ILE->getType()->isArrayType())
 640       return EmitArrayInitialization(ILE);
 641
 642     if (ILE->getType()->isRecordType())
 643       return EmitStructInitialization(ILE);
 644
 645     if (ILE->getType()->isUnionType())
 646       return EmitUnionInitialization(ILE);
 647
 648     // If ILE was a constant vector, we would have handled it already.
 649     if (ILE->getType()->isVectorType())
 650       return 0;
 651
 652     assert(0 && "Unable to handle InitListExpr");
 653     // Get rid of control reaches end of void function warning.
 654     // Not reached.
 655     return 0;
 656   }
 657
 658   llvm::Constant *VisitCXXConstructExpr(CXXConstructExpr *E) {
 659     if (!E->getConstructor()->isTrivial())
 660       return 0;
 661
 662     QualType Ty = E->getType();
 663
 664     // FIXME: We should not have to call getBaseElementType here.
 665     const RecordType *RT =
 666       CGM.getContext().getBaseElementType(Ty)->getAs<RecordType>();
 667     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
 668
 669     // If the class doesn't have a trivial destructor, we can't emit it as a
 670     // constant expr.
 671     if (!RD->hasTrivialDestructor())
 672       return 0;
 673
 674     // Only copy and default constructors can be trivial.
 675
 676
 677     if (E->getNumArgs()) {
 678       assert(E->getNumArgs() == 1 && "trivial ctor with > 1 argument");
 679       assert(E->getConstructor()->isCopyConstructor() &&
 680              "trivial ctor has argument but isn't a copy ctor");
 681
 682       Expr *Arg = E->getArg(0);
 683       assert(CGM.getContext().hasSameUnqualifiedType(Ty, Arg->getType()) &&
 684              "argument to copy ctor is of wrong type");
 685
 686       return Visit(Arg);
 687     }
 688
 689     return CGM.EmitNullConstant(Ty);
 690   }
 691
 692   llvm::Constant *VisitStringLiteral(StringLiteral *E) {
 693     assert(!E->getType()->isPointerType() && "Strings are always arrays");
 694
 695     // This must be a string initializing an array in a static initializer.
 696     // Don't emit it as the address of the string, emit the string data itself
 697     // as an inline array.
 698     return llvm::ConstantArray::get(VMContext,
 699                                     CGM.GetStringForStringLiteral(E), false);
 700   }
 701
 702   llvm::Constant *VisitObjCEncodeExpr(ObjCEncodeExpr *E) {
 703     // This must be an @encode initializing an array in a static initializer.
 704     // Don't emit it as the address of the string, emit the string data itself
 705     // as an inline array.
 706     std::string Str;
 707     CGM.getContext().getObjCEncodingForType(E->getEncodedType(), Str);
 708     const ConstantArrayType *CAT = cast<ConstantArrayType>(E->getType());
 709
 710     // Resize the string to the right size, adding zeros at the end, or
 711     // truncating as needed.
 712     Str.resize(CAT->getSize().getZExtValue(), '\0');
 713     return llvm::ConstantArray::get(VMContext, Str, false);
 714   }
 715
 716   llvm::Constant *VisitUnaryExtension(const UnaryOperator *E) {
 717     return Visit(E->getSubExpr());
 718   }
 719
 720   // Utility methods
 721   const llvm::Type *ConvertType(QualType T) {
 722     return CGM.getTypes().ConvertType(T);
 723   }
 724
 725 public:
 726   llvm::Constant *EmitLValue(Expr *E) {
 727     switch (E->getStmtClass()) {
 728     default: break;
 729     case Expr::CompoundLiteralExprClass: {
 730       // Note that due to the nature of compound literals, this is guaranteed
 731       // to be the only use of the variable, so we just generate it here.
 732       CompoundLiteralExpr *CLE = cast<CompoundLiteralExpr>(E);
 733       llvm::Constant* C = Visit(CLE->getInitializer());
 734       // FIXME: "Leaked" on failure.
 735       if (C)
 736         C = new llvm::GlobalVariable(CGM.getModule(), C->getType(),
 737                                      E->getType().isConstant(CGM.getContext()),
 738                                      llvm::GlobalValue::InternalLinkage,
 739                                      C, ".compoundliteral", 0, false,
 740                                      E->getType().getAddressSpace());
 741       return C;
 742     }
 743     case Expr::DeclRefExprClass: {
 744       ValueDecl *Decl = cast<DeclRefExpr>(E)->getDecl();
 745       if (Decl->hasAttr<WeakRefAttr>())
 746         return CGM.GetWeakRefReference(Decl);
 747       if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(Decl))
 748         return CGM.GetAddrOfFunction(FD);
 749       if (const VarDecl* VD = dyn_cast<VarDecl>(Decl)) {
 750         // We can never refer to a variable with local storage.
 751         if (!VD->hasLocalStorage()) {
 752           if (VD->isFileVarDecl() || VD->hasExternalStorage())
 753             return CGM.GetAddrOfGlobalVar(VD);
 754           else if (VD->isLocalVarDecl()) {
 755             assert(CGF && "Can't access static local vars without CGF");
 756             return CGF->GetAddrOfStaticLocalVar(VD);
 757           }
 758         }
 759       }
 760       break;
 761     }
 762     case Expr::StringLiteralClass:
 763       return CGM.GetAddrOfConstantStringFromLiteral(cast<StringLiteral>(E));
 764     case Expr::ObjCEncodeExprClass:
 765       return CGM.GetAddrOfConstantStringFromObjCEncode(cast<ObjCEncodeExpr>(E));
 766     case Expr::ObjCStringLiteralClass: {
 767       ObjCStringLiteral* SL = cast<ObjCStringLiteral>(E);
 768       llvm::Constant *C =
 769           CGM.getObjCRuntime().GenerateConstantString(SL->getString());
 770       return llvm::ConstantExpr::getBitCast(C, ConvertType(E->getType()));
 771     }
 772     case Expr::PredefinedExprClass: {
 773       unsigned Type = cast<PredefinedExpr>(E)->getIdentType();
 774       if (CGF) {
 775         LValue Res = CGF->EmitPredefinedLValue(cast<PredefinedExpr>(E));
 776         return cast<llvm::Constant>(Res.getAddress());
 777       } else if (Type == PredefinedExpr::PrettyFunction) {
 778         return CGM.GetAddrOfConstantCString("top level", ".tmp");
 779       }
 780
 781       return CGM.GetAddrOfConstantCString("", ".tmp");
 782     }
 783     case Expr::AddrLabelExprClass: {
 784       assert(CGF && "Invalid address of label expression outside function.");
 785       llvm::Constant *Ptr =
 786         CGF->GetAddrOfLabel(cast<AddrLabelExpr>(E)->getLabel());
 787       return llvm::ConstantExpr::getBitCast(Ptr, ConvertType(E->getType()));
 788     }
 789     case Expr::CallExprClass: {
 790       CallExpr* CE = cast<CallExpr>(E);
 791       unsigned builtin = CE->isBuiltinCall(CGM.getContext());
 792       if (builtin !=
 793             Builtin::BI__builtin___CFStringMakeConstantString &&
 794           builtin !=
 795             Builtin::BI__builtin___NSStringMakeConstantString)
 796         break;
 797       const Expr *Arg = CE->getArg(0)->IgnoreParenCasts();
 798       const StringLiteral *Literal = cast<StringLiteral>(Arg);
 799       if (builtin ==
 800             Builtin::BI__builtin___NSStringMakeConstantString) {
 801         return CGM.getObjCRuntime().GenerateConstantString(Literal);
 802       }
 803       // FIXME: need to deal with UCN conversion issues.
 804       return CGM.GetAddrOfConstantCFString(Literal);
 805     }
 806     case Expr::BlockExprClass: {
 807       std::string FunctionName;
 808       if (CGF)
 809         FunctionName = CGF->CurFn->getName();
 810       else
 811         FunctionName = "global";
 812
 813       return CGM.GetAddrOfGlobalBlock(cast<BlockExpr>(E), FunctionName.c_str());
 814     }
 815     }
 816
 817     return 0;
 818   }
 819 };
 820
 821 }  // end anonymous namespace.
 822
 823 llvm::Constant *CodeGenModule::EmitConstantExpr(const Expr *E,
 824                                                 QualType DestType,
 825                                                 CodeGenFunction *CGF) {
 826   Expr::EvalResult Result;
 827
 828   bool Success = false;
 829
 830   if (DestType->isReferenceType())
 831     Success = E->EvaluateAsLValue(Result, Context);
 832   else
 833     Success = E->Evaluate(Result, Context);
 834
 835   if (Success && !Result.HasSideEffects) {
 836     switch (Result.Val.getKind()) {
 837     case APValue::Uninitialized:
 838       assert(0 && "Constant expressions should be initialized.");
 839       return 0;
 840     case APValue::LValue: {
 841       const llvm::Type *DestTy = getTypes().ConvertTypeForMem(DestType);
 842       llvm::Constant *Offset =
 843         llvm::ConstantInt::get(llvm::Type::getInt64Ty(VMContext),
 844                                Result.Val.getLValueOffset().getQuantity());
 845
 846       llvm::Constant *C;
 847       if (const Expr *LVBase = Result.Val.getLValueBase()) {
 848         C = ConstExprEmitter(*this, CGF).EmitLValue(const_cast<Expr*>(LVBase));
 849
 850         // Apply offset if necessary.
 851         if (!Offset->isNullValue()) {
 852           const llvm::Type *Type = llvm::Type::getInt8PtrTy(VMContext);
 853           llvm::Constant *Casted = llvm::ConstantExpr::getBitCast(C, Type);
 854           Casted = llvm::ConstantExpr::getGetElementPtr(Casted, &Offset, 1);
 855           C = llvm::ConstantExpr::getBitCast(Casted, C->getType());
 856         }
 857
 858         // Convert to the appropriate type; this could be an lvalue for
 859         // an integer.
 860         if (isa<llvm::PointerType>(DestTy))
 861           return llvm::ConstantExpr::getBitCast(C, DestTy);
 862
 863         return llvm::ConstantExpr::getPtrToInt(C, DestTy);
 864       } else {
 865         C = Offset;
 866
 867         // Convert to the appropriate type; this could be an lvalue for
 868         // an integer.
 869         if (isa<llvm::PointerType>(DestTy))
 870           return llvm::ConstantExpr::getIntToPtr(C, DestTy);
 871
 872         // If the types don't match this should only be a truncate.
 873         if (C->getType() != DestTy)
 874           return llvm::ConstantExpr::getTrunc(C, DestTy);
 875
 876         return C;
 877       }
 878     }
 879     case APValue::Int: {
 880       llvm::Constant *C = llvm::ConstantInt::get(VMContext,
 881                                                  Result.Val.getInt());
 882
 883       if (C->getType()->isIntegerTy(1)) {
 884         const llvm::Type *BoolTy = getTypes().ConvertTypeForMem(E->getType());
 885         C = llvm::ConstantExpr::getZExt(C, BoolTy);
 886       }
 887       return C;
 888     }
 889     case APValue::ComplexInt: {
 890       llvm::Constant *Complex[2];
 891
 892       Complex[0] = llvm::ConstantInt::get(VMContext,
 893                                           Result.Val.getComplexIntReal());
 894       Complex[1] = llvm::ConstantInt::get(VMContext,
 895                                           Result.Val.getComplexIntImag());
 896
 897       // FIXME: the target may want to specify that this is packed.
 898       return llvm::ConstantStruct::get(VMContext, Complex, 2, false);
 899     }
 900     case APValue::Float:
 901       return llvm::ConstantFP::get(VMContext, Result.Val.getFloat());
 902     case APValue::ComplexFloat: {
 903       llvm::Constant *Complex[2];
 904
 905       Complex[0] = llvm::ConstantFP::get(VMContext,
 906                                          Result.Val.getComplexFloatReal());
 907       Complex[1] = llvm::ConstantFP::get(VMContext,
 908                                          Result.Val.getComplexFloatImag());
 909
 910       // FIXME: the target may want to specify that this is packed.
 911       return llvm::ConstantStruct::get(VMContext, Complex, 2, false);
 912     }
 913     case APValue::Vector: {
 914       llvm::SmallVector<llvm::Constant *, 4> Inits;
 915       unsigned NumElts = Result.Val.getVectorLength();
 916
 917       for (unsigned i = 0; i != NumElts; ++i) {
 918         APValue &Elt = Result.Val.getVectorElt(i);
 919         if (Elt.isInt())
 920           Inits.push_back(llvm::ConstantInt::get(VMContext, Elt.getInt()));
 921         else
 922           Inits.push_back(llvm::ConstantFP::get(VMContext, Elt.getFloat()));
 923       }
 924       return llvm::ConstantVector::get(&Inits[0], Inits.size());
 925     }
 926     }
 927   }
 928
 929   llvm::Constant* C = ConstExprEmitter(*this, CGF).Visit(const_cast<Expr*>(E));
 930   if (C && C->getType()->isIntegerTy(1)) {
 931     const llvm::Type *BoolTy = getTypes().ConvertTypeForMem(E->getType());
 932     C = llvm::ConstantExpr::getZExt(C, BoolTy);
 933   }
 934   return C;
 935 }
 936
 937 static void
 938 FillInNullDataMemberPointers(CodeGenModule &CGM, QualType T,
 939                              std::vector<llvm::Constant *> &Elements,
 940                              uint64_t StartOffset) {
 941   assert(StartOffset % 8 == 0 && "StartOffset not byte aligned!");
 942
 943   if (CGM.getTypes().isZeroInitializable(T))
 944     return;
 945
 946   if (const ConstantArrayType *CAT =
 947         CGM.getContext().getAsConstantArrayType(T)) {
 948     QualType ElementTy = CAT->getElementType();
 949     uint64_t ElementSize = CGM.getContext().getTypeSize(ElementTy);
 950
 951     for (uint64_t I = 0, E = CAT->getSize().getZExtValue(); I != E; ++I) {
 952       FillInNullDataMemberPointers(CGM, ElementTy, Elements,
 953                                    StartOffset + I * ElementSize);
 954     }
 955   } else if (const RecordType *RT = T->getAs<RecordType>()) {
 956     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
 957     const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(RD);
 958
 959     // Go through all bases and fill in any null pointer to data members.
 960     for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 961          E = RD->bases_end(); I != E; ++I) {
 962       if (I->isVirtual()) {
 963         // Ignore virtual bases.
 964         continue;
 965       }
 966
 967       const CXXRecordDecl *BaseDecl =
 968       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 969
 970       // Ignore empty bases.
 971       if (BaseDecl->isEmpty())
 972         continue;
 973
 974       // Ignore bases that don't have any pointer to data members.
 975       if (CGM.getTypes().isZeroInitializable(BaseDecl))
 976         continue;
 977
 978       uint64_t BaseOffset = Layout.getBaseClassOffsetInBits(BaseDecl);
 979       FillInNullDataMemberPointers(CGM, I->getType(),
 980                                    Elements, StartOffset + BaseOffset);
 981     }
 982
 983     // Visit all fields.
 984     unsigned FieldNo = 0;
 985     for (RecordDecl::field_iterator I = RD->field_begin(),
 986          E = RD->field_end(); I != E; ++I, ++FieldNo) {
 987       QualType FieldType = I->getType();
 988
 989       if (CGM.getTypes().isZeroInitializable(FieldType))
 990         continue;
 991
 992       uint64_t FieldOffset = StartOffset + Layout.getFieldOffset(FieldNo);
 993       FillInNullDataMemberPointers(CGM, FieldType, Elements, FieldOffset);
 994     }
 995   } else {
 996     assert(T->isMemberPointerType() && "Should only see member pointers here!");
 997     assert(!T->getAs<MemberPointerType>()->getPointeeType()->isFunctionType() &&
 998            "Should only see pointers to data members here!");
 999
1000     uint64_t StartIndex = StartOffset / 8;
1001     uint64_t EndIndex = StartIndex + CGM.getContext().getTypeSize(T) / 8;
1002
1003     llvm::Constant *NegativeOne =
1004       llvm::ConstantInt::get(llvm::Type::getInt8Ty(CGM.getLLVMContext()),
1005                              -1ULL, /*isSigned=*/true);
1006
1007     // Fill in the null data member pointer.
1008     for (uint64_t I = StartIndex; I != EndIndex; ++I)
1009       Elements[I] = NegativeOne;
1010   }
1011 }
1012
1013 static llvm::Constant *EmitNullConstant(CodeGenModule &CGM,
1014                                         const CXXRecordDecl *RD) {
1015   QualType T = CGM.getContext().getTagDeclType(RD);
1016
1017   const llvm::StructType *STy =
1018     cast<llvm::StructType>(CGM.getTypes().ConvertTypeForMem(T));
1019   unsigned NumElements = STy->getNumElements();
1020   std::vector<llvm::Constant *> Elements(NumElements);
1021
1022   const CGRecordLayout &Layout = CGM.getTypes().getCGRecordLayout(RD);
1023
1024   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
1025        E = RD->bases_end(); I != E; ++I) {
1026     if (I->isVirtual()) {
1027       // Ignore virtual bases.
1028       continue;
1029     }
1030
1031     const CXXRecordDecl *BaseDecl =
1032       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
1033
1034     // Ignore empty bases.
1035     if (BaseDecl->isEmpty())
1036       continue;
1037
1038     // Ignore bases that don't have any pointer to data members.
1039     if (CGM.getTypes().isZeroInitializable(BaseDecl))
1040       continue;
1041
1042     unsigned BaseFieldNo = Layout.getNonVirtualBaseLLVMFieldNo(BaseDecl);
1043     const llvm::Type *BaseTy = STy->getElementType(BaseFieldNo);
1044
1045     if (isa<llvm::StructType>(BaseTy)) {
1046       // We can just emit the base as a null constant.
1047       Elements[BaseFieldNo] = EmitNullConstant(CGM, BaseDecl);
1048       continue;
1049     }
1050
1051     // Some bases are represented as arrays of i8 if the size of the
1052     // base is smaller than its corresponding LLVM type.
1053     // Figure out how many elements this base array has.
1054     const llvm::ArrayType *BaseArrayTy =  cast<llvm::ArrayType>(BaseTy);
1055     unsigned NumBaseElements = BaseArrayTy->getNumElements();
1056
1057     // Fill in null data member pointers.
1058     std::vector<llvm::Constant *> BaseElements(NumBaseElements);
1059     FillInNullDataMemberPointers(CGM, I->getType(), BaseElements, 0);
1060
1061     // Now go through all other elements and zero them out.
1062     if (NumBaseElements) {
1063       const llvm::Type* Int8Ty = llvm::Type::getInt8Ty(CGM.getLLVMContext());
1064       llvm::Constant *Zero = llvm::Constant::getNullValue(Int8Ty);
1065       for (unsigned I = 0; I != NumBaseElements; ++I) {
1066         if (!BaseElements[I])
1067           BaseElements[I] = Zero;
1068       }
1069     }
1070
1071     Elements[BaseFieldNo] = llvm::ConstantArray::get(BaseArrayTy, BaseElements);
1072   }
1073
1074   // Visit all fields.
1075   for (RecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
1076        I != E; ++I) {
1077     const FieldDecl *FD = *I;
1078
1079     // Ignore bit fields.
1080     if (FD->isBitField())
1081       continue;
1082
1083     unsigned FieldNo = Layout.getLLVMFieldNo(FD);
1084     Elements[FieldNo] = CGM.EmitNullConstant(FD->getType());
1085   }
1086
1087   // Now go through all other fields and zero them out.
1088   for (unsigned i = 0; i != NumElements; ++i) {
1089     if (!Elements[i])
1090       Elements[i] = llvm::Constant::getNullValue(STy->getElementType(i));
1091   }
1092
1093   return llvm::ConstantStruct::get(STy, Elements);
1094 }
1095
1096 llvm::Constant *CodeGenModule::EmitNullConstant(QualType T) {
1097   if (getTypes().isZeroInitializable(T))
1098     return llvm::Constant::getNullValue(getTypes().ConvertTypeForMem(T));
1099
1100   if (const ConstantArrayType *CAT = Context.getAsConstantArrayType(T)) {
1101
1102     QualType ElementTy = CAT->getElementType();
1103
1104     llvm::Constant *Element = EmitNullConstant(ElementTy);
1105     unsigned NumElements = CAT->getSize().getZExtValue();
1106     std::vector<llvm::Constant *> Array(NumElements);
1107     for (unsigned i = 0; i != NumElements; ++i)
1108       Array[i] = Element;
1109
1110     const llvm::ArrayType *ATy =
1111       cast<llvm::ArrayType>(getTypes().ConvertTypeForMem(T));
1112     return llvm::ConstantArray::get(ATy, Array);
1113   }
1114
1115   if (const RecordType *RT = T->getAs<RecordType>()) {
1116     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
1117     return ::EmitNullConstant(*this, RD);
1118   }
1119
1120   assert(T->isMemberPointerType() && "Should only see member pointers here!");
1121   assert(!T->getAs<MemberPointerType>()->getPointeeType()->isFunctionType() &&
1122          "Should only see pointers to data members here!");
1123
1124   // Itanium C++ ABI 2.3:
1125   //   A NULL pointer is represented as -1.
1126   return llvm::ConstantInt::get(getTypes().ConvertTypeForMem(T), -1ULL,
1127                                 /*isSigned=*/true);
1128 }