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

   1 //===--- CGExprCXX.cpp - Emit LLVM Code for C++ 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 dealing with code generation of C++ expressions
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "CodeGenFunction.h"
  15 #include "CGCUDARuntime.h"
  16 #include "CGCXXABI.h"
  17 #include "CGDebugInfo.h"
  18 #include "CGObjCRuntime.h"
  19 #include "clang/CodeGen/CGFunctionInfo.h"
  20 #include "clang/Frontend/CodeGenOptions.h"
  21 #include "llvm/IR/Intrinsics.h"
  22 #include "llvm/Support/CallSite.h"
  23
  24 using namespace clang;
  25 using namespace CodeGen;
  26
  27 RValue CodeGenFunction::EmitCXXMemberCall(const CXXMethodDecl *MD,
  28                                           SourceLocation CallLoc,
  29                                           llvm::Value *Callee,
  30                                           ReturnValueSlot ReturnValue,
  31                                           llvm::Value *This,
  32                                           llvm::Value *ImplicitParam,
  33                                           QualType ImplicitParamTy,
  34                                           CallExpr::const_arg_iterator ArgBeg,
  35                                           CallExpr::const_arg_iterator ArgEnd) {
  36   assert(MD->isInstance() &&
  37          "Trying to emit a member call expr on a static method!");
  38
  39   // C++11 [class.mfct.non-static]p2:
  40   //   If a non-static member function of a class X is called for an object that
  41   //   is not of type X, or of a type derived from X, the behavior is undefined.
  42   EmitTypeCheck(isa<CXXConstructorDecl>(MD) ? TCK_ConstructorCall
  43                                             : TCK_MemberCall,
  44                 CallLoc, This, getContext().getRecordType(MD->getParent()));
  45
  46   CallArgList Args;
  47
  48   // Push the this ptr.
  49   Args.add(RValue::get(This), MD->getThisType(getContext()));
  50
  51   // If there is an implicit parameter (e.g. VTT), emit it.
  52   if (ImplicitParam) {
  53     Args.add(RValue::get(ImplicitParam), ImplicitParamTy);
  54   }
  55
  56   const FunctionProtoType *FPT = MD->getType()->castAs<FunctionProtoType>();
  57   RequiredArgs required = RequiredArgs::forPrototypePlus(FPT, Args.size());
  58
  59   // And the rest of the call args.
  60   EmitCallArgs(Args, FPT, ArgBeg, ArgEnd);
  61
  62   return EmitCall(CGM.getTypes().arrangeCXXMethodCall(Args, FPT, required),
  63                   Callee, ReturnValue, Args, MD);
  64 }
  65
  66 static CXXRecordDecl *getCXXRecord(const Expr *E) {
  67   QualType T = E->getType();
  68   if (const PointerType *PTy = T->getAs<PointerType>())
  69     T = PTy->getPointeeType();
  70   const RecordType *Ty = T->castAs<RecordType>();
  71   return cast<CXXRecordDecl>(Ty->getDecl());
  72 }
  73
  74 // Note: This function also emit constructor calls to support a MSVC
  75 // extensions allowing explicit constructor function call.
  76 RValue CodeGenFunction::EmitCXXMemberCallExpr(const CXXMemberCallExpr *CE,
  77                                               ReturnValueSlot ReturnValue) {
  78   const Expr *callee = CE->getCallee()->IgnoreParens();
  79
  80   if (isa<BinaryOperator>(callee))
  81     return EmitCXXMemberPointerCallExpr(CE, ReturnValue);
  82
  83   const MemberExpr *ME = cast<MemberExpr>(callee);
  84   const CXXMethodDecl *MD = cast<CXXMethodDecl>(ME->getMemberDecl());
  85
  86   if (MD->isStatic()) {
  87     // The method is static, emit it as we would a regular call.
  88     llvm::Value *Callee = CGM.GetAddrOfFunction(MD);
  89     return EmitCall(getContext().getPointerType(MD->getType()), Callee,
  90                     CE->getLocStart(), ReturnValue, CE->arg_begin(),
  91                     CE->arg_end());
  92   }
  93
  94   // Compute the object pointer.
  95   const Expr *Base = ME->getBase();
  96   bool CanUseVirtualCall = MD->isVirtual() && !ME->hasQualifier();
  97
  98   const CXXMethodDecl *DevirtualizedMethod = NULL;
  99   if (CanUseVirtualCall && CanDevirtualizeMemberFunctionCall(Base, MD)) {
 100     const CXXRecordDecl *BestDynamicDecl = Base->getBestDynamicClassType();
 101     DevirtualizedMethod = MD->getCorrespondingMethodInClass(BestDynamicDecl);
 102     assert(DevirtualizedMethod);
 103     const CXXRecordDecl *DevirtualizedClass = DevirtualizedMethod->getParent();
 104     const Expr *Inner = Base->ignoreParenBaseCasts();
 105     if (getCXXRecord(Inner) == DevirtualizedClass)
 106       // If the class of the Inner expression is where the dynamic method
 107       // is defined, build the this pointer from it.
 108       Base = Inner;
 109     else if (getCXXRecord(Base) != DevirtualizedClass) {
 110       // If the method is defined in a class that is not the best dynamic
 111       // one or the one of the full expression, we would have to build
 112       // a derived-to-base cast to compute the correct this pointer, but
 113       // we don't have support for that yet, so do a virtual call.
 114       DevirtualizedMethod = NULL;
 115     }
 116     // If the return types are not the same, this might be a case where more
 117     // code needs to run to compensate for it. For example, the derived
 118     // method might return a type that inherits form from the return
 119     // type of MD and has a prefix.
 120     // For now we just avoid devirtualizing these covariant cases.
 121     if (DevirtualizedMethod &&
 122         DevirtualizedMethod->getResultType().getCanonicalType() !=
 123         MD->getResultType().getCanonicalType())
 124       DevirtualizedMethod = NULL;
 125   }
 126
 127   llvm::Value *This;
 128   if (ME->isArrow())
 129     This = EmitScalarExpr(Base);
 130   else
 131     This = EmitLValue(Base).getAddress();
 132
 133
 134   if (MD->isTrivial()) {
 135     if (isa<CXXDestructorDecl>(MD)) return RValue::get(0);
 136     if (isa<CXXConstructorDecl>(MD) &&
 137         cast<CXXConstructorDecl>(MD)->isDefaultConstructor())
 138       return RValue::get(0);
 139
 140     if (MD->isCopyAssignmentOperator() || MD->isMoveAssignmentOperator()) {
 141       // We don't like to generate the trivial copy/move assignment operator
 142       // when it isn't necessary; just produce the proper effect here.
 143       llvm::Value *RHS = EmitLValue(*CE->arg_begin()).getAddress();
 144       EmitAggregateAssign(This, RHS, CE->getType());
 145       return RValue::get(This);
 146     }
 147
 148     if (isa<CXXConstructorDecl>(MD) &&
 149         cast<CXXConstructorDecl>(MD)->isCopyOrMoveConstructor()) {
 150       // Trivial move and copy ctor are the same.
 151       llvm::Value *RHS = EmitLValue(*CE->arg_begin()).getAddress();
 152       EmitSynthesizedCXXCopyCtorCall(cast<CXXConstructorDecl>(MD), This, RHS,
 153                                      CE->arg_begin(), CE->arg_end());
 154       return RValue::get(This);
 155     }
 156     llvm_unreachable("unknown trivial member function");
 157   }
 158
 159   // Compute the function type we're calling.
 160   const CXXMethodDecl *CalleeDecl = DevirtualizedMethod ? DevirtualizedMethod : MD;
 161   const CGFunctionInfo *FInfo = 0;
 162   if (const CXXDestructorDecl *Dtor = dyn_cast<CXXDestructorDecl>(CalleeDecl))
 163     FInfo = &CGM.getTypes().arrangeCXXDestructor(Dtor,
 164                                                  Dtor_Complete);
 165   else if (const CXXConstructorDecl *Ctor = dyn_cast<CXXConstructorDecl>(CalleeDecl))
 166     FInfo = &CGM.getTypes().arrangeCXXConstructorDeclaration(Ctor,
 167                                                              Ctor_Complete);
 168   else
 169     FInfo = &CGM.getTypes().arrangeCXXMethodDeclaration(CalleeDecl);
 170
 171   llvm::FunctionType *Ty = CGM.getTypes().GetFunctionType(*FInfo);
 172
 173   // C++ [class.virtual]p12:
 174   //   Explicit qualification with the scope operator (5.1) suppresses the
 175   //   virtual call mechanism.
 176   //
 177   // We also don't emit a virtual call if the base expression has a record type
 178   // because then we know what the type is.
 179   bool UseVirtualCall = CanUseVirtualCall && !DevirtualizedMethod;
 180   llvm::Value *Callee;
 181
 182   if (const CXXDestructorDecl *Dtor = dyn_cast<CXXDestructorDecl>(MD)) {
 183     assert(CE->arg_begin() == CE->arg_end() &&
 184            "Destructor shouldn't have explicit parameters");
 185     assert(ReturnValue.isNull() && "Destructor shouldn't have return value");
 186     if (UseVirtualCall) {
 187       CGM.getCXXABI().EmitVirtualDestructorCall(*this, Dtor, Dtor_Complete,
 188                                                 CE->getExprLoc(), This);
 189     } else {
 190       if (getLangOpts().AppleKext &&
 191           MD->isVirtual() &&
 192           ME->hasQualifier())
 193         Callee = BuildAppleKextVirtualCall(MD, ME->getQualifier(), Ty);
 194       else if (!DevirtualizedMethod)
 195         Callee = CGM.GetAddrOfCXXDestructor(Dtor, Dtor_Complete, FInfo, Ty);
 196       else {
 197         const CXXDestructorDecl *DDtor =
 198           cast<CXXDestructorDecl>(DevirtualizedMethod);
 199         Callee = CGM.GetAddrOfFunction(GlobalDecl(DDtor, Dtor_Complete), Ty);
 200       }
 201       EmitCXXMemberCall(MD, CE->getExprLoc(), Callee, ReturnValue, This,
 202                         /*ImplicitParam=*/0, QualType(), 0, 0);
 203     }
 204     return RValue::get(0);
 205   }
 206
 207   if (const CXXConstructorDecl *Ctor = dyn_cast<CXXConstructorDecl>(MD)) {
 208     Callee = CGM.GetAddrOfFunction(GlobalDecl(Ctor, Ctor_Complete), Ty);
 209   } else if (UseVirtualCall) {
 210     Callee = CGM.getCXXABI().getVirtualFunctionPointer(*this, MD, This, Ty);
 211   } else {
 212     if (getLangOpts().AppleKext &&
 213         MD->isVirtual() &&
 214         ME->hasQualifier())
 215       Callee = BuildAppleKextVirtualCall(MD, ME->getQualifier(), Ty);
 216     else if (!DevirtualizedMethod)
 217       Callee = CGM.GetAddrOfFunction(MD, Ty);
 218     else {
 219       Callee = CGM.GetAddrOfFunction(DevirtualizedMethod, Ty);
 220     }
 221   }
 222
 223   if (MD->isVirtual())
 224     This = CGM.getCXXABI().adjustThisArgumentForVirtualCall(*this, MD, This);
 225
 226   return EmitCXXMemberCall(MD, CE->getExprLoc(), Callee, ReturnValue, This,
 227                            /*ImplicitParam=*/0, QualType(),
 228                            CE->arg_begin(), CE->arg_end());
 229 }
 230
 231 RValue
 232 CodeGenFunction::EmitCXXMemberPointerCallExpr(const CXXMemberCallExpr *E,
 233                                               ReturnValueSlot ReturnValue) {
 234   const BinaryOperator *BO =
 235       cast<BinaryOperator>(E->getCallee()->IgnoreParens());
 236   const Expr *BaseExpr = BO->getLHS();
 237   const Expr *MemFnExpr = BO->getRHS();
 238
 239   const MemberPointerType *MPT =
 240     MemFnExpr->getType()->castAs<MemberPointerType>();
 241
 242   const FunctionProtoType *FPT =
 243     MPT->getPointeeType()->castAs<FunctionProtoType>();
 244   const CXXRecordDecl *RD =
 245     cast<CXXRecordDecl>(MPT->getClass()->getAs<RecordType>()->getDecl());
 246
 247   // Get the member function pointer.
 248   llvm::Value *MemFnPtr = EmitScalarExpr(MemFnExpr);
 249
 250   // Emit the 'this' pointer.
 251   llvm::Value *This;
 252
 253   if (BO->getOpcode() == BO_PtrMemI)
 254     This = EmitScalarExpr(BaseExpr);
 255   else
 256     This = EmitLValue(BaseExpr).getAddress();
 257
 258   EmitTypeCheck(TCK_MemberCall, E->getExprLoc(), This,
 259                 QualType(MPT->getClass(), 0));
 260
 261   // Ask the ABI to load the callee.  Note that This is modified.
 262   llvm::Value *Callee =
 263     CGM.getCXXABI().EmitLoadOfMemberFunctionPointer(*this, This, MemFnPtr, MPT);
 264
 265   CallArgList Args;
 266
 267   QualType ThisType =
 268     getContext().getPointerType(getContext().getTagDeclType(RD));
 269
 270   // Push the this ptr.
 271   Args.add(RValue::get(This), ThisType);
 272
 273   RequiredArgs required = RequiredArgs::forPrototypePlus(FPT, 1);
 274
 275   // And the rest of the call args
 276   EmitCallArgs(Args, FPT, E->arg_begin(), E->arg_end());
 277   return EmitCall(CGM.getTypes().arrangeCXXMethodCall(Args, FPT, required),
 278                   Callee, ReturnValue, Args);
 279 }
 280
 281 RValue
 282 CodeGenFunction::EmitCXXOperatorMemberCallExpr(const CXXOperatorCallExpr *E,
 283                                                const CXXMethodDecl *MD,
 284                                                ReturnValueSlot ReturnValue) {
 285   assert(MD->isInstance() &&
 286          "Trying to emit a member call expr on a static method!");
 287   LValue LV = EmitLValue(E->getArg(0));
 288   llvm::Value *This = LV.getAddress();
 289
 290   if ((MD->isCopyAssignmentOperator() || MD->isMoveAssignmentOperator()) &&
 291       MD->isTrivial()) {
 292     llvm::Value *Src = EmitLValue(E->getArg(1)).getAddress();
 293     QualType Ty = E->getType();
 294     EmitAggregateAssign(This, Src, Ty);
 295     return RValue::get(This);
 296   }
 297
 298   llvm::Value *Callee = EmitCXXOperatorMemberCallee(E, MD, This);
 299   return EmitCXXMemberCall(MD, E->getExprLoc(), Callee, ReturnValue, This,
 300                            /*ImplicitParam=*/0, QualType(),
 301                            E->arg_begin() + 1, E->arg_end());
 302 }
 303
 304 RValue CodeGenFunction::EmitCUDAKernelCallExpr(const CUDAKernelCallExpr *E,
 305                                                ReturnValueSlot ReturnValue) {
 306   return CGM.getCUDARuntime().EmitCUDAKernelCallExpr(*this, E, ReturnValue);
 307 }
 308
 309 static void EmitNullBaseClassInitialization(CodeGenFunction &CGF,
 310                                             llvm::Value *DestPtr,
 311                                             const CXXRecordDecl *Base) {
 312   if (Base->isEmpty())
 313     return;
 314
 315   DestPtr = CGF.EmitCastToVoidPtr(DestPtr);
 316
 317   const ASTRecordLayout &Layout = CGF.getContext().getASTRecordLayout(Base);
 318   CharUnits Size = Layout.getNonVirtualSize();
 319   CharUnits Align = Layout.getNonVirtualAlign();
 320
 321   llvm::Value *SizeVal = CGF.CGM.getSize(Size);
 322
 323   // If the type contains a pointer to data member we can't memset it to zero.
 324   // Instead, create a null constant and copy it to the destination.
 325   // TODO: there are other patterns besides zero that we can usefully memset,
 326   // like -1, which happens to be the pattern used by member-pointers.
 327   // TODO: isZeroInitializable can be over-conservative in the case where a
 328   // virtual base contains a member pointer.
 329   if (!CGF.CGM.getTypes().isZeroInitializable(Base)) {
 330     llvm::Constant *NullConstant = CGF.CGM.EmitNullConstantForBase(Base);
 331
 332     llvm::GlobalVariable *NullVariable =
 333       new llvm::GlobalVariable(CGF.CGM.getModule(), NullConstant->getType(),
 334                                /*isConstant=*/true,
 335                                llvm::GlobalVariable::PrivateLinkage,
 336                                NullConstant, Twine());
 337     NullVariable->setAlignment(Align.getQuantity());
 338     llvm::Value *SrcPtr = CGF.EmitCastToVoidPtr(NullVariable);
 339
 340     // Get and call the appropriate llvm.memcpy overload.
 341     CGF.Builder.CreateMemCpy(DestPtr, SrcPtr, SizeVal, Align.getQuantity());
 342     return;
 343   }
 344
 345   // Otherwise, just memset the whole thing to zero.  This is legal
 346   // because in LLVM, all default initializers (other than the ones we just
 347   // handled above) are guaranteed to have a bit pattern of all zeros.
 348   CGF.Builder.CreateMemSet(DestPtr, CGF.Builder.getInt8(0), SizeVal,
 349                            Align.getQuantity());
 350 }
 351
 352 void
 353 CodeGenFunction::EmitCXXConstructExpr(const CXXConstructExpr *E,
 354                                       AggValueSlot Dest) {
 355   assert(!Dest.isIgnored() && "Must have a destination!");
 356   const CXXConstructorDecl *CD = E->getConstructor();
 357
 358   // If we require zero initialization before (or instead of) calling the
 359   // constructor, as can be the case with a non-user-provided default
 360   // constructor, emit the zero initialization now, unless destination is
 361   // already zeroed.
 362   if (E->requiresZeroInitialization() && !Dest.isZeroed()) {
 363     switch (E->getConstructionKind()) {
 364     case CXXConstructExpr::CK_Delegating:
 365     case CXXConstructExpr::CK_Complete:
 366       EmitNullInitialization(Dest.getAddr(), E->getType());
 367       break;
 368     case CXXConstructExpr::CK_VirtualBase:
 369     case CXXConstructExpr::CK_NonVirtualBase:
 370       EmitNullBaseClassInitialization(*this, Dest.getAddr(), CD->getParent());
 371       break;
 372     }
 373   }
 374
 375   // If this is a call to a trivial default constructor, do nothing.
 376   if (CD->isTrivial() && CD->isDefaultConstructor())
 377     return;
 378
 379   // Elide the constructor if we're constructing from a temporary.
 380   // The temporary check is required because Sema sets this on NRVO
 381   // returns.
 382   if (getLangOpts().ElideConstructors && E->isElidable()) {
 383     assert(getContext().hasSameUnqualifiedType(E->getType(),
 384                                                E->getArg(0)->getType()));
 385     if (E->getArg(0)->isTemporaryObject(getContext(), CD->getParent())) {
 386       EmitAggExpr(E->getArg(0), Dest);
 387       return;
 388     }
 389   }
 390
 391   if (const ConstantArrayType *arrayType
 392         = getContext().getAsConstantArrayType(E->getType())) {
 393     EmitCXXAggrConstructorCall(CD, arrayType, Dest.getAddr(),
 394                                E->arg_begin(), E->arg_end());
 395   } else {
 396     CXXCtorType Type = Ctor_Complete;
 397     bool ForVirtualBase = false;
 398     bool Delegating = false;
 399
 400     switch (E->getConstructionKind()) {
 401      case CXXConstructExpr::CK_Delegating:
 402       // We should be emitting a constructor; GlobalDecl will assert this
 403       Type = CurGD.getCtorType();
 404       Delegating = true;
 405       break;
 406
 407      case CXXConstructExpr::CK_Complete:
 408       Type = Ctor_Complete;
 409       break;
 410
 411      case CXXConstructExpr::CK_VirtualBase:
 412       ForVirtualBase = true;
 413       // fall-through
 414
 415      case CXXConstructExpr::CK_NonVirtualBase:
 416       Type = Ctor_Base;
 417     }
 418
 419     // Call the constructor.
 420     EmitCXXConstructorCall(CD, Type, ForVirtualBase, Delegating, Dest.getAddr(),
 421                            E->arg_begin(), E->arg_end());
 422   }
 423 }
 424
 425 void
 426 CodeGenFunction::EmitSynthesizedCXXCopyCtor(llvm::Value *Dest,
 427                                             llvm::Value *Src,
 428                                             const Expr *Exp) {
 429   if (const ExprWithCleanups *E = dyn_cast<ExprWithCleanups>(Exp))
 430     Exp = E->getSubExpr();
 431   assert(isa<CXXConstructExpr>(Exp) &&
 432          "EmitSynthesizedCXXCopyCtor - unknown copy ctor expr");
 433   const CXXConstructExpr* E = cast<CXXConstructExpr>(Exp);
 434   const CXXConstructorDecl *CD = E->getConstructor();
 435   RunCleanupsScope Scope(*this);
 436
 437   // If we require zero initialization before (or instead of) calling the
 438   // constructor, as can be the case with a non-user-provided default
 439   // constructor, emit the zero initialization now.
 440   // FIXME. Do I still need this for a copy ctor synthesis?
 441   if (E->requiresZeroInitialization())
 442     EmitNullInitialization(Dest, E->getType());
 443
 444   assert(!getContext().getAsConstantArrayType(E->getType())
 445          && "EmitSynthesizedCXXCopyCtor - Copied-in Array");
 446   EmitSynthesizedCXXCopyCtorCall(CD, Dest, Src, E->arg_begin(), E->arg_end());
 447 }
 448
 449 static CharUnits CalculateCookiePadding(CodeGenFunction &CGF,
 450                                         const CXXNewExpr *E) {
 451   if (!E->isArray())
 452     return CharUnits::Zero();
 453
 454   // No cookie is required if the operator new[] being used is the
 455   // reserved placement operator new[].
 456   if (E->getOperatorNew()->isReservedGlobalPlacementOperator())
 457     return CharUnits::Zero();
 458
 459   return CGF.CGM.getCXXABI().GetArrayCookieSize(E);
 460 }
 461
 462 static llvm::Value *EmitCXXNewAllocSize(CodeGenFunction &CGF,
 463                                         const CXXNewExpr *e,
 464                                         unsigned minElements,
 465                                         llvm::Value *&numElements,
 466                                         llvm::Value *&sizeWithoutCookie) {
 467   QualType type = e->getAllocatedType();
 468
 469   if (!e->isArray()) {
 470     CharUnits typeSize = CGF.getContext().getTypeSizeInChars(type);
 471     sizeWithoutCookie
 472       = llvm::ConstantInt::get(CGF.SizeTy, typeSize.getQuantity());
 473     return sizeWithoutCookie;
 474   }
 475
 476   // The width of size_t.
 477   unsigned sizeWidth = CGF.SizeTy->getBitWidth();
 478
 479   // Figure out the cookie size.
 480   llvm::APInt cookieSize(sizeWidth,
 481                          CalculateCookiePadding(CGF, e).getQuantity());
 482
 483   // Emit the array size expression.
 484   // We multiply the size of all dimensions for NumElements.
 485   // e.g for 'int[2][3]', ElemType is 'int' and NumElements is 6.
 486   numElements = CGF.EmitScalarExpr(e->getArraySize());
 487   assert(isa<llvm::IntegerType>(numElements->getType()));
 488
 489   // The number of elements can be have an arbitrary integer type;
 490   // essentially, we need to multiply it by a constant factor, add a
 491   // cookie size, and verify that the result is representable as a
 492   // size_t.  That's just a gloss, though, and it's wrong in one
 493   // important way: if the count is negative, it's an error even if
 494   // the cookie size would bring the total size >= 0.
 495   bool isSigned
 496     = e->getArraySize()->getType()->isSignedIntegerOrEnumerationType();
 497   llvm::IntegerType *numElementsType
 498     = cast<llvm::IntegerType>(numElements->getType());
 499   unsigned numElementsWidth = numElementsType->getBitWidth();
 500
 501   // Compute the constant factor.
 502   llvm::APInt arraySizeMultiplier(sizeWidth, 1);
 503   while (const ConstantArrayType *CAT
 504              = CGF.getContext().getAsConstantArrayType(type)) {
 505     type = CAT->getElementType();
 506     arraySizeMultiplier *= CAT->getSize();
 507   }
 508
 509   CharUnits typeSize = CGF.getContext().getTypeSizeInChars(type);
 510   llvm::APInt typeSizeMultiplier(sizeWidth, typeSize.getQuantity());
 511   typeSizeMultiplier *= arraySizeMultiplier;
 512
 513   // This will be a size_t.
 514   llvm::Value *size;
 515
 516   // If someone is doing 'new int[42]' there is no need to do a dynamic check.
 517   // Don't bloat the -O0 code.
 518   if (llvm::ConstantInt *numElementsC =
 519         dyn_cast<llvm::ConstantInt>(numElements)) {
 520     const llvm::APInt &count = numElementsC->getValue();
 521
 522     bool hasAnyOverflow = false;
 523
 524     // If 'count' was a negative number, it's an overflow.
 525     if (isSigned && count.isNegative())
 526       hasAnyOverflow = true;
 527
 528     // We want to do all this arithmetic in size_t.  If numElements is
 529     // wider than that, check whether it's already too big, and if so,
 530     // overflow.
 531     else if (numElementsWidth > sizeWidth &&
 532              numElementsWidth - sizeWidth > count.countLeadingZeros())
 533       hasAnyOverflow = true;
 534
 535     // Okay, compute a count at the right width.
 536     llvm::APInt adjustedCount = count.zextOrTrunc(sizeWidth);
 537
 538     // If there is a brace-initializer, we cannot allocate fewer elements than
 539     // there are initializers. If we do, that's treated like an overflow.
 540     if (adjustedCount.ult(minElements))
 541       hasAnyOverflow = true;
 542
 543     // Scale numElements by that.  This might overflow, but we don't
 544     // care because it only overflows if allocationSize does, too, and
 545     // if that overflows then we shouldn't use this.
 546     numElements = llvm::ConstantInt::get(CGF.SizeTy,
 547                                          adjustedCount * arraySizeMultiplier);
 548
 549     // Compute the size before cookie, and track whether it overflowed.
 550     bool overflow;
 551     llvm::APInt allocationSize
 552       = adjustedCount.umul_ov(typeSizeMultiplier, overflow);
 553     hasAnyOverflow |= overflow;
 554
 555     // Add in the cookie, and check whether it's overflowed.
 556     if (cookieSize != 0) {
 557       // Save the current size without a cookie.  This shouldn't be
 558       // used if there was overflow.
 559       sizeWithoutCookie = llvm::ConstantInt::get(CGF.SizeTy, allocationSize);
 560
 561       allocationSize = allocationSize.uadd_ov(cookieSize, overflow);
 562       hasAnyOverflow |= overflow;
 563     }
 564
 565     // On overflow, produce a -1 so operator new will fail.
 566     if (hasAnyOverflow) {
 567       size = llvm::Constant::getAllOnesValue(CGF.SizeTy);
 568     } else {
 569       size = llvm::ConstantInt::get(CGF.SizeTy, allocationSize);
 570     }
 571
 572   // Otherwise, we might need to use the overflow intrinsics.
 573   } else {
 574     // There are up to five conditions we need to test for:
 575     // 1) if isSigned, we need to check whether numElements is negative;
 576     // 2) if numElementsWidth > sizeWidth, we need to check whether
 577     //   numElements is larger than something representable in size_t;
 578     // 3) if minElements > 0, we need to check whether numElements is smaller
 579     //    than that.
 580     // 4) we need to compute
 581     //      sizeWithoutCookie := numElements * typeSizeMultiplier
 582     //    and check whether it overflows; and
 583     // 5) if we need a cookie, we need to compute
 584     //      size := sizeWithoutCookie + cookieSize
 585     //    and check whether it overflows.
 586
 587     llvm::Value *hasOverflow = 0;
 588
 589     // If numElementsWidth > sizeWidth, then one way or another, we're
 590     // going to have to do a comparison for (2), and this happens to
 591     // take care of (1), too.
 592     if (numElementsWidth > sizeWidth) {
 593       llvm::APInt threshold(numElementsWidth, 1);
 594       threshold <<= sizeWidth;
 595
 596       llvm::Value *thresholdV
 597         = llvm::ConstantInt::get(numElementsType, threshold);
 598
 599       hasOverflow = CGF.Builder.CreateICmpUGE(numElements, thresholdV);
 600       numElements = CGF.Builder.CreateTrunc(numElements, CGF.SizeTy);
 601
 602     // Otherwise, if we're signed, we want to sext up to size_t.
 603     } else if (isSigned) {
 604       if (numElementsWidth < sizeWidth)
 605         numElements = CGF.Builder.CreateSExt(numElements, CGF.SizeTy);
 606
 607       // If there's a non-1 type size multiplier, then we can do the
 608       // signedness check at the same time as we do the multiply
 609       // because a negative number times anything will cause an
 610       // unsigned overflow.  Otherwise, we have to do it here. But at least
 611       // in this case, we can subsume the >= minElements check.
 612       if (typeSizeMultiplier == 1)
 613         hasOverflow = CGF.Builder.CreateICmpSLT(numElements,
 614                               llvm::ConstantInt::get(CGF.SizeTy, minElements));
 615
 616     // Otherwise, zext up to size_t if necessary.
 617     } else if (numElementsWidth < sizeWidth) {
 618       numElements = CGF.Builder.CreateZExt(numElements, CGF.SizeTy);
 619     }
 620
 621     assert(numElements->getType() == CGF.SizeTy);
 622
 623     if (minElements) {
 624       // Don't allow allocation of fewer elements than we have initializers.
 625       if (!hasOverflow) {
 626         hasOverflow = CGF.Builder.CreateICmpULT(numElements,
 627                               llvm::ConstantInt::get(CGF.SizeTy, minElements));
 628       } else if (numElementsWidth > sizeWidth) {
 629         // The other existing overflow subsumes this check.
 630         // We do an unsigned comparison, since any signed value < -1 is
 631         // taken care of either above or below.
 632         hasOverflow = CGF.Builder.CreateOr(hasOverflow,
 633                           CGF.Builder.CreateICmpULT(numElements,
 634                               llvm::ConstantInt::get(CGF.SizeTy, minElements)));
 635       }
 636     }
 637
 638     size = numElements;
 639
 640     // Multiply by the type size if necessary.  This multiplier
 641     // includes all the factors for nested arrays.
 642     //
 643     // This step also causes numElements to be scaled up by the
 644     // nested-array factor if necessary.  Overflow on this computation
 645     // can be ignored because the result shouldn't be used if
 646     // allocation fails.
 647     if (typeSizeMultiplier != 1) {
 648       llvm::Value *umul_with_overflow
 649         = CGF.CGM.getIntrinsic(llvm::Intrinsic::umul_with_overflow, CGF.SizeTy);
 650
 651       llvm::Value *tsmV =
 652         llvm::ConstantInt::get(CGF.SizeTy, typeSizeMultiplier);
 653       llvm::Value *result =
 654         CGF.Builder.CreateCall2(umul_with_overflow, size, tsmV);
 655
 656       llvm::Value *overflowed = CGF.Builder.CreateExtractValue(result, 1);
 657       if (hasOverflow)
 658         hasOverflow = CGF.Builder.CreateOr(hasOverflow, overflowed);
 659       else
 660         hasOverflow = overflowed;
 661
 662       size = CGF.Builder.CreateExtractValue(result, 0);
 663
 664       // Also scale up numElements by the array size multiplier.
 665       if (arraySizeMultiplier != 1) {
 666         // If the base element type size is 1, then we can re-use the
 667         // multiply we just did.
 668         if (typeSize.isOne()) {
 669           assert(arraySizeMultiplier == typeSizeMultiplier);
 670           numElements = size;
 671
 672         // Otherwise we need a separate multiply.
 673         } else {
 674           llvm::Value *asmV =
 675             llvm::ConstantInt::get(CGF.SizeTy, arraySizeMultiplier);
 676           numElements = CGF.Builder.CreateMul(numElements, asmV);
 677         }
 678       }
 679     } else {
 680       // numElements doesn't need to be scaled.
 681       assert(arraySizeMultiplier == 1);
 682     }
 683
 684     // Add in the cookie size if necessary.
 685     if (cookieSize != 0) {
 686       sizeWithoutCookie = size;
 687
 688       llvm::Value *uadd_with_overflow
 689         = CGF.CGM.getIntrinsic(llvm::Intrinsic::uadd_with_overflow, CGF.SizeTy);
 690
 691       llvm::Value *cookieSizeV = llvm::ConstantInt::get(CGF.SizeTy, cookieSize);
 692       llvm::Value *result =
 693         CGF.Builder.CreateCall2(uadd_with_overflow, size, cookieSizeV);
 694
 695       llvm::Value *overflowed = CGF.Builder.CreateExtractValue(result, 1);
 696       if (hasOverflow)
 697         hasOverflow = CGF.Builder.CreateOr(hasOverflow, overflowed);
 698       else
 699         hasOverflow = overflowed;
 700
 701       size = CGF.Builder.CreateExtractValue(result, 0);
 702     }
 703
 704     // If we had any possibility of dynamic overflow, make a select to
 705     // overwrite 'size' with an all-ones value, which should cause
 706     // operator new to throw.
 707     if (hasOverflow)
 708       size = CGF.Builder.CreateSelect(hasOverflow,
 709                                  llvm::Constant::getAllOnesValue(CGF.SizeTy),
 710                                       size);
 711   }
 712
 713   if (cookieSize == 0)
 714     sizeWithoutCookie = size;
 715   else
 716     assert(sizeWithoutCookie && "didn't set sizeWithoutCookie?");
 717
 718   return size;
 719 }
 720
 721 static void StoreAnyExprIntoOneUnit(CodeGenFunction &CGF, const Expr *Init,
 722                                     QualType AllocType, llvm::Value *NewPtr) {
 723   // FIXME: Refactor with EmitExprAsInit.
 724   CharUnits Alignment = CGF.getContext().getTypeAlignInChars(AllocType);
 725   switch (CGF.getEvaluationKind(AllocType)) {
 726   case TEK_Scalar:
 727     CGF.EmitScalarInit(Init, 0, CGF.MakeAddrLValue(NewPtr, AllocType,
 728                                                    Alignment),
 729                        false);
 730     return;
 731   case TEK_Complex:
 732     CGF.EmitComplexExprIntoLValue(Init, CGF.MakeAddrLValue(NewPtr, AllocType,
 733                                                            Alignment),
 734                                   /*isInit*/ true);
 735     return;
 736   case TEK_Aggregate: {
 737     AggValueSlot Slot
 738       = AggValueSlot::forAddr(NewPtr, Alignment, AllocType.getQualifiers(),
 739                               AggValueSlot::IsDestructed,
 740                               AggValueSlot::DoesNotNeedGCBarriers,
 741                               AggValueSlot::IsNotAliased);
 742     CGF.EmitAggExpr(Init, Slot);
 743     return;
 744   }
 745   }
 746   llvm_unreachable("bad evaluation kind");
 747 }
 748
 749 void
 750 CodeGenFunction::EmitNewArrayInitializer(const CXXNewExpr *E,
 751                                          QualType elementType,
 752                                          llvm::Value *beginPtr,
 753                                          llvm::Value *numElements) {
 754   if (!E->hasInitializer())
 755     return; // We have a POD type.
 756
 757   llvm::Value *explicitPtr = beginPtr;
 758   // Find the end of the array, hoisted out of the loop.
 759   llvm::Value *endPtr =
 760     Builder.CreateInBoundsGEP(beginPtr, numElements, "array.end");
 761
 762   unsigned initializerElements = 0;
 763
 764   const Expr *Init = E->getInitializer();
 765   llvm::AllocaInst *endOfInit = 0;
 766   QualType::DestructionKind dtorKind = elementType.isDestructedType();
 767   EHScopeStack::stable_iterator cleanup;
 768   llvm::Instruction *cleanupDominator = 0;
 769
 770   // If the initializer is an initializer list, first do the explicit elements.
 771   if (const InitListExpr *ILE = dyn_cast<InitListExpr>(Init)) {
 772     initializerElements = ILE->getNumInits();
 773
 774     // If this is a multi-dimensional array new, we will initialize multiple
 775     // elements with each init list element.
 776     QualType AllocType = E->getAllocatedType();
 777     if (const ConstantArrayType *CAT = dyn_cast_or_null<ConstantArrayType>(
 778             AllocType->getAsArrayTypeUnsafe())) {
 779       unsigned AS = explicitPtr->getType()->getPointerAddressSpace();
 780       llvm::Type *AllocPtrTy = ConvertTypeForMem(AllocType)->getPointerTo(AS);
 781       explicitPtr = Builder.CreateBitCast(explicitPtr, AllocPtrTy);
 782       initializerElements *= getContext().getConstantArrayElementCount(CAT);
 783     }
 784
 785     // Enter a partial-destruction cleanup if necessary.
 786     if (needsEHCleanup(dtorKind)) {
 787       // In principle we could tell the cleanup where we are more
 788       // directly, but the control flow can get so varied here that it
 789       // would actually be quite complex.  Therefore we go through an
 790       // alloca.
 791       endOfInit = CreateTempAlloca(beginPtr->getType(), "array.endOfInit");
 792       cleanupDominator = Builder.CreateStore(beginPtr, endOfInit);
 793       pushIrregularPartialArrayCleanup(beginPtr, endOfInit, elementType,
 794                                        getDestroyer(dtorKind));
 795       cleanup = EHStack.stable_begin();
 796     }
 797
 798     for (unsigned i = 0, e = ILE->getNumInits(); i != e; ++i) {
 799       // Tell the cleanup that it needs to destroy up to this
 800       // element.  TODO: some of these stores can be trivially
 801       // observed to be unnecessary.
 802       if (endOfInit) Builder.CreateStore(explicitPtr, endOfInit);
 803       StoreAnyExprIntoOneUnit(*this, ILE->getInit(i),
 804                               ILE->getInit(i)->getType(), explicitPtr);
 805       explicitPtr = Builder.CreateConstGEP1_32(explicitPtr, 1,
 806                                                "array.exp.next");
 807     }
 808
 809     // The remaining elements are filled with the array filler expression.
 810     Init = ILE->getArrayFiller();
 811
 812     explicitPtr = Builder.CreateBitCast(explicitPtr, beginPtr->getType());
 813   }
 814
 815   // Create the continuation block.
 816   llvm::BasicBlock *contBB = createBasicBlock("new.loop.end");
 817
 818   // If the number of elements isn't constant, we have to now check if there is
 819   // anything left to initialize.
 820   if (llvm::ConstantInt *constNum = dyn_cast<llvm::ConstantInt>(numElements)) {
 821     // If all elements have already been initialized, skip the whole loop.
 822     if (constNum->getZExtValue() <= initializerElements) {
 823       // If there was a cleanup, deactivate it.
 824       if (cleanupDominator)
 825         DeactivateCleanupBlock(cleanup, cleanupDominator);
 826       return;
 827     }
 828   } else {
 829     llvm::BasicBlock *nonEmptyBB = createBasicBlock("new.loop.nonempty");
 830     llvm::Value *isEmpty = Builder.CreateICmpEQ(explicitPtr, endPtr,
 831                                                 "array.isempty");
 832     Builder.CreateCondBr(isEmpty, contBB, nonEmptyBB);
 833     EmitBlock(nonEmptyBB);
 834   }
 835
 836   // Enter the loop.
 837   llvm::BasicBlock *entryBB = Builder.GetInsertBlock();
 838   llvm::BasicBlock *loopBB = createBasicBlock("new.loop");
 839
 840   EmitBlock(loopBB);
 841
 842   // Set up the current-element phi.
 843   llvm::PHINode *curPtr =
 844     Builder.CreatePHI(explicitPtr->getType(), 2, "array.cur");
 845   curPtr->addIncoming(explicitPtr, entryBB);
 846
 847   // Store the new cleanup position for irregular cleanups.
 848   if (endOfInit) Builder.CreateStore(curPtr, endOfInit);
 849
 850   // Enter a partial-destruction cleanup if necessary.
 851   if (!cleanupDominator && needsEHCleanup(dtorKind)) {
 852     pushRegularPartialArrayCleanup(beginPtr, curPtr, elementType,
 853                                    getDestroyer(dtorKind));
 854     cleanup = EHStack.stable_begin();
 855     cleanupDominator = Builder.CreateUnreachable();
 856   }
 857
 858   // Emit the initializer into this element.
 859   StoreAnyExprIntoOneUnit(*this, Init, E->getAllocatedType(), curPtr);
 860
 861   // Leave the cleanup if we entered one.
 862   if (cleanupDominator) {
 863     DeactivateCleanupBlock(cleanup, cleanupDominator);
 864     cleanupDominator->eraseFromParent();
 865   }
 866
 867   // Advance to the next element.
 868   llvm::Value *nextPtr = Builder.CreateConstGEP1_32(curPtr, 1, "array.next");
 869
 870   // Check whether we've gotten to the end of the array and, if so,
 871   // exit the loop.
 872   llvm::Value *isEnd = Builder.CreateICmpEQ(nextPtr, endPtr, "array.atend");
 873   Builder.CreateCondBr(isEnd, contBB, loopBB);
 874   curPtr->addIncoming(nextPtr, Builder.GetInsertBlock());
 875
 876   EmitBlock(contBB);
 877 }
 878
 879 static void EmitZeroMemSet(CodeGenFunction &CGF, QualType T,
 880                            llvm::Value *NewPtr, llvm::Value *Size) {
 881   CGF.EmitCastToVoidPtr(NewPtr);
 882   CharUnits Alignment = CGF.getContext().getTypeAlignInChars(T);
 883   CGF.Builder.CreateMemSet(NewPtr, CGF.Builder.getInt8(0), Size,
 884                            Alignment.getQuantity(), false);
 885 }
 886
 887 static void EmitNewInitializer(CodeGenFunction &CGF, const CXXNewExpr *E,
 888                                QualType ElementType,
 889                                llvm::Value *NewPtr,
 890                                llvm::Value *NumElements,
 891                                llvm::Value *AllocSizeWithoutCookie) {
 892   const Expr *Init = E->getInitializer();
 893   if (E->isArray()) {
 894     if (const CXXConstructExpr *CCE = dyn_cast_or_null<CXXConstructExpr>(Init)){
 895       CXXConstructorDecl *Ctor = CCE->getConstructor();
 896       if (Ctor->isTrivial()) {
 897         // If new expression did not specify value-initialization, then there
 898         // is no initialization.
 899         if (!CCE->requiresZeroInitialization() || Ctor->getParent()->isEmpty())
 900           return;
 901
 902         if (CGF.CGM.getTypes().isZeroInitializable(ElementType)) {
 903           // Optimization: since zero initialization will just set the memory
 904           // to all zeroes, generate a single memset to do it in one shot.
 905           EmitZeroMemSet(CGF, ElementType, NewPtr, AllocSizeWithoutCookie);
 906           return;
 907         }
 908       }
 909
 910       CGF.EmitCXXAggrConstructorCall(Ctor, NumElements, NewPtr,
 911                                      CCE->arg_begin(),  CCE->arg_end(),
 912                                      CCE->requiresZeroInitialization());
 913       return;
 914     } else if (Init && isa<ImplicitValueInitExpr>(Init) &&
 915                CGF.CGM.getTypes().isZeroInitializable(ElementType)) {
 916       // Optimization: since zero initialization will just set the memory
 917       // to all zeroes, generate a single memset to do it in one shot.
 918       EmitZeroMemSet(CGF, ElementType, NewPtr, AllocSizeWithoutCookie);
 919       return;
 920     }
 921     CGF.EmitNewArrayInitializer(E, ElementType, NewPtr, NumElements);
 922     return;
 923   }
 924
 925   if (!Init)
 926     return;
 927
 928   StoreAnyExprIntoOneUnit(CGF, Init, E->getAllocatedType(), NewPtr);
 929 }
 930
 931 /// Emit a call to an operator new or operator delete function, as implicitly
 932 /// created by new-expressions and delete-expressions.
 933 static RValue EmitNewDeleteCall(CodeGenFunction &CGF,
 934                                 const FunctionDecl *Callee,
 935                                 const FunctionProtoType *CalleeType,
 936                                 const CallArgList &Args) {
 937   llvm::Instruction *CallOrInvoke;
 938   llvm::Value *CalleeAddr = CGF.CGM.GetAddrOfFunction(Callee);
 939   RValue RV =
 940       CGF.EmitCall(CGF.CGM.getTypes().arrangeFreeFunctionCall(Args, CalleeType),
 941                    CalleeAddr, ReturnValueSlot(), Args,
 942                    Callee, &CallOrInvoke);
 943
 944   /// C++1y [expr.new]p10:
 945   ///   [In a new-expression,] an implementation is allowed to omit a call
 946   ///   to a replaceable global allocation function.
 947   ///
 948   /// We model such elidable calls with the 'builtin' attribute.
 949   llvm::Function *Fn = dyn_cast<llvm::Function>(CalleeAddr);
 950   if (Callee->isReplaceableGlobalAllocationFunction() &&
 951       Fn && Fn->hasFnAttribute(llvm::Attribute::NoBuiltin)) {
 952     // FIXME: Add addAttribute to CallSite.
 953     if (llvm::CallInst *CI = dyn_cast<llvm::CallInst>(CallOrInvoke))
 954       CI->addAttribute(llvm::AttributeSet::FunctionIndex,
 955                        llvm::Attribute::Builtin);
 956     else if (llvm::InvokeInst *II = dyn_cast<llvm::InvokeInst>(CallOrInvoke))
 957       II->addAttribute(llvm::AttributeSet::FunctionIndex,
 958                        llvm::Attribute::Builtin);
 959     else
 960       llvm_unreachable("unexpected kind of call instruction");
 961   }
 962
 963   return RV;
 964 }
 965
 966 namespace {
 967   /// A cleanup to call the given 'operator delete' function upon
 968   /// abnormal exit from a new expression.
 969   class CallDeleteDuringNew : public EHScopeStack::Cleanup {
 970     size_t NumPlacementArgs;
 971     const FunctionDecl *OperatorDelete;
 972     llvm::Value *Ptr;
 973     llvm::Value *AllocSize;
 974
 975     RValue *getPlacementArgs() { return reinterpret_cast<RValue*>(this+1); }
 976
 977   public:
 978     static size_t getExtraSize(size_t NumPlacementArgs) {
 979       return NumPlacementArgs * sizeof(RValue);
 980     }
 981
 982     CallDeleteDuringNew(size_t NumPlacementArgs,
 983                         const FunctionDecl *OperatorDelete,
 984                         llvm::Value *Ptr,
 985                         llvm::Value *AllocSize)
 986       : NumPlacementArgs(NumPlacementArgs), OperatorDelete(OperatorDelete),
 987         Ptr(Ptr), AllocSize(AllocSize) {}
 988
 989     void setPlacementArg(unsigned I, RValue Arg) {
 990       assert(I < NumPlacementArgs && "index out of range");
 991       getPlacementArgs()[I] = Arg;
 992     }
 993
 994     void Emit(CodeGenFunction &CGF, Flags flags) {
 995       const FunctionProtoType *FPT
 996         = OperatorDelete->getType()->getAs<FunctionProtoType>();
 997       assert(FPT->getNumArgs() == NumPlacementArgs + 1 ||
 998              (FPT->getNumArgs() == 2 && NumPlacementArgs == 0));
 999
1000       CallArgList DeleteArgs;
1001
1002       // The first argument is always a void*.
1003       FunctionProtoType::arg_type_iterator AI = FPT->arg_type_begin();
1004       DeleteArgs.add(RValue::get(Ptr), *AI++);
1005
1006       // A member 'operator delete' can take an extra 'size_t' argument.
1007       if (FPT->getNumArgs() == NumPlacementArgs + 2)
1008         DeleteArgs.add(RValue::get(AllocSize), *AI++);
1009
1010       // Pass the rest of the arguments, which must match exactly.
1011       for (unsigned I = 0; I != NumPlacementArgs; ++I)
1012         DeleteArgs.add(getPlacementArgs()[I], *AI++);
1013
1014       // Call 'operator delete'.
1015       EmitNewDeleteCall(CGF, OperatorDelete, FPT, DeleteArgs);
1016     }
1017   };
1018
1019   /// A cleanup to call the given 'operator delete' function upon
1020   /// abnormal exit from a new expression when the new expression is
1021   /// conditional.
1022   class CallDeleteDuringConditionalNew : public EHScopeStack::Cleanup {
1023     size_t NumPlacementArgs;
1024     const FunctionDecl *OperatorDelete;
1025     DominatingValue<RValue>::saved_type Ptr;
1026     DominatingValue<RValue>::saved_type AllocSize;
1027
1028     DominatingValue<RValue>::saved_type *getPlacementArgs() {
1029       return reinterpret_cast<DominatingValue<RValue>::saved_type*>(this+1);
1030     }
1031
1032   public:
1033     static size_t getExtraSize(size_t NumPlacementArgs) {
1034       return NumPlacementArgs * sizeof(DominatingValue<RValue>::saved_type);
1035     }
1036
1037     CallDeleteDuringConditionalNew(size_t NumPlacementArgs,
1038                                    const FunctionDecl *OperatorDelete,
1039                                    DominatingValue<RValue>::saved_type Ptr,
1040                               DominatingValue<RValue>::saved_type AllocSize)
1041       : NumPlacementArgs(NumPlacementArgs), OperatorDelete(OperatorDelete),
1042         Ptr(Ptr), AllocSize(AllocSize) {}
1043
1044     void setPlacementArg(unsigned I, DominatingValue<RValue>::saved_type Arg) {
1045       assert(I < NumPlacementArgs && "index out of range");
1046       getPlacementArgs()[I] = Arg;
1047     }
1048
1049     void Emit(CodeGenFunction &CGF, Flags flags) {
1050       const FunctionProtoType *FPT
1051         = OperatorDelete->getType()->getAs<FunctionProtoType>();
1052       assert(FPT->getNumArgs() == NumPlacementArgs + 1 ||
1053              (FPT->getNumArgs() == 2 && NumPlacementArgs == 0));
1054
1055       CallArgList DeleteArgs;
1056
1057       // The first argument is always a void*.
1058       FunctionProtoType::arg_type_iterator AI = FPT->arg_type_begin();
1059       DeleteArgs.add(Ptr.restore(CGF), *AI++);
1060
1061       // A member 'operator delete' can take an extra 'size_t' argument.
1062       if (FPT->getNumArgs() == NumPlacementArgs + 2) {
1063         RValue RV = AllocSize.restore(CGF);
1064         DeleteArgs.add(RV, *AI++);
1065       }
1066
1067       // Pass the rest of the arguments, which must match exactly.
1068       for (unsigned I = 0; I != NumPlacementArgs; ++I) {
1069         RValue RV = getPlacementArgs()[I].restore(CGF);
1070         DeleteArgs.add(RV, *AI++);
1071       }
1072
1073       // Call 'operator delete'.
1074       EmitNewDeleteCall(CGF, OperatorDelete, FPT, DeleteArgs);
1075     }
1076   };
1077 }
1078
1079 /// Enter a cleanup to call 'operator delete' if the initializer in a
1080 /// new-expression throws.
1081 static void EnterNewDeleteCleanup(CodeGenFunction &CGF,
1082                                   const CXXNewExpr *E,
1083                                   llvm::Value *NewPtr,
1084                                   llvm::Value *AllocSize,
1085                                   const CallArgList &NewArgs) {
1086   // If we're not inside a conditional branch, then the cleanup will
1087   // dominate and we can do the easier (and more efficient) thing.
1088   if (!CGF.isInConditionalBranch()) {
1089     CallDeleteDuringNew *Cleanup = CGF.EHStack
1090       .pushCleanupWithExtra<CallDeleteDuringNew>(EHCleanup,
1091                                                  E->getNumPlacementArgs(),
1092                                                  E->getOperatorDelete(),
1093                                                  NewPtr, AllocSize);
1094     for (unsigned I = 0, N = E->getNumPlacementArgs(); I != N; ++I)
1095       Cleanup->setPlacementArg(I, NewArgs[I+1].RV);
1096
1097     return;
1098   }
1099
1100   // Otherwise, we need to save all this stuff.
1101   DominatingValue<RValue>::saved_type SavedNewPtr =
1102     DominatingValue<RValue>::save(CGF, RValue::get(NewPtr));
1103   DominatingValue<RValue>::saved_type SavedAllocSize =
1104     DominatingValue<RValue>::save(CGF, RValue::get(AllocSize));
1105
1106   CallDeleteDuringConditionalNew *Cleanup = CGF.EHStack
1107     .pushCleanupWithExtra<CallDeleteDuringConditionalNew>(EHCleanup,
1108                                                  E->getNumPlacementArgs(),
1109                                                  E->getOperatorDelete(),
1110                                                  SavedNewPtr,
1111                                                  SavedAllocSize);
1112   for (unsigned I = 0, N = E->getNumPlacementArgs(); I != N; ++I)
1113     Cleanup->setPlacementArg(I,
1114                      DominatingValue<RValue>::save(CGF, NewArgs[I+1].RV));
1115
1116   CGF.initFullExprCleanup();
1117 }
1118
1119 llvm::Value *CodeGenFunction::EmitCXXNewExpr(const CXXNewExpr *E) {
1120   // The element type being allocated.
1121   QualType allocType = getContext().getBaseElementType(E->getAllocatedType());
1122
1123   // 1. Build a call to the allocation function.
1124   FunctionDecl *allocator = E->getOperatorNew();
1125   const FunctionProtoType *allocatorType =
1126     allocator->getType()->castAs<FunctionProtoType>();
1127
1128   CallArgList allocatorArgs;
1129
1130   // The allocation size is the first argument.
1131   QualType sizeType = getContext().getSizeType();
1132
1133   // If there is a brace-initializer, cannot allocate fewer elements than inits.
1134   unsigned minElements = 0;
1135   if (E->isArray() && E->hasInitializer()) {
1136     if (const InitListExpr *ILE = dyn_cast<InitListExpr>(E->getInitializer()))
1137       minElements = ILE->getNumInits();
1138   }
1139
1140   llvm::Value *numElements = 0;
1141   llvm::Value *allocSizeWithoutCookie = 0;
1142   llvm::Value *allocSize =
1143     EmitCXXNewAllocSize(*this, E, minElements, numElements,
1144                         allocSizeWithoutCookie);
1145
1146   allocatorArgs.add(RValue::get(allocSize), sizeType);
1147
1148   // Emit the rest of the arguments.
1149   // FIXME: Ideally, this should just use EmitCallArgs.
1150   CXXNewExpr::const_arg_iterator placementArg = E->placement_arg_begin();
1151
1152   // First, use the types from the function type.
1153   // We start at 1 here because the first argument (the allocation size)
1154   // has already been emitted.
1155   for (unsigned i = 1, e = allocatorType->getNumArgs(); i != e;
1156        ++i, ++placementArg) {
1157     QualType argType = allocatorType->getArgType(i);
1158
1159     assert(getContext().hasSameUnqualifiedType(argType.getNonReferenceType(),
1160                                                placementArg->getType()) &&
1161            "type mismatch in call argument!");
1162
1163     EmitCallArg(allocatorArgs, *placementArg, argType);
1164   }
1165
1166   // Either we've emitted all the call args, or we have a call to a
1167   // variadic function.
1168   assert((placementArg == E->placement_arg_end() ||
1169           allocatorType->isVariadic()) &&
1170          "Extra arguments to non-variadic function!");
1171
1172   // If we still have any arguments, emit them using the type of the argument.
1173   for (CXXNewExpr::const_arg_iterator placementArgsEnd = E->placement_arg_end();
1174        placementArg != placementArgsEnd; ++placementArg) {
1175     EmitCallArg(allocatorArgs, *placementArg, placementArg->getType());
1176   }
1177
1178   // Emit the allocation call.  If the allocator is a global placement
1179   // operator, just "inline" it directly.
1180   RValue RV;
1181   if (allocator->isReservedGlobalPlacementOperator()) {
1182     assert(allocatorArgs.size() == 2);
1183     RV = allocatorArgs[1].RV;
1184     // TODO: kill any unnecessary computations done for the size
1185     // argument.
1186   } else {
1187     RV = EmitNewDeleteCall(*this, allocator, allocatorType, allocatorArgs);
1188   }
1189
1190   // Emit a null check on the allocation result if the allocation
1191   // function is allowed to return null (because it has a non-throwing
1192   // exception spec; for this part, we inline
1193   // CXXNewExpr::shouldNullCheckAllocation()) and we have an
1194   // interesting initializer.
1195   bool nullCheck = allocatorType->isNothrow(getContext()) &&
1196     (!allocType.isPODType(getContext()) || E->hasInitializer());
1197
1198   llvm::BasicBlock *nullCheckBB = 0;
1199   llvm::BasicBlock *contBB = 0;
1200
1201   llvm::Value *allocation = RV.getScalarVal();
1202   unsigned AS = allocation->getType()->getPointerAddressSpace();
1203
1204   // The null-check means that the initializer is conditionally
1205   // evaluated.
1206   ConditionalEvaluation conditional(*this);
1207
1208   if (nullCheck) {
1209     conditional.begin(*this);
1210
1211     nullCheckBB = Builder.GetInsertBlock();
1212     llvm::BasicBlock *notNullBB = createBasicBlock("new.notnull");
1213     contBB = createBasicBlock("new.cont");
1214
1215     llvm::Value *isNull = Builder.CreateIsNull(allocation, "new.isnull");
1216     Builder.CreateCondBr(isNull, contBB, notNullBB);
1217     EmitBlock(notNullBB);
1218   }
1219
1220   // If there's an operator delete, enter a cleanup to call it if an
1221   // exception is thrown.
1222   EHScopeStack::stable_iterator operatorDeleteCleanup;
1223   llvm::Instruction *cleanupDominator = 0;
1224   if (E->getOperatorDelete() &&
1225       !E->getOperatorDelete()->isReservedGlobalPlacementOperator()) {
1226     EnterNewDeleteCleanup(*this, E, allocation, allocSize, allocatorArgs);
1227     operatorDeleteCleanup = EHStack.stable_begin();
1228     cleanupDominator = Builder.CreateUnreachable();
1229   }
1230
1231   assert((allocSize == allocSizeWithoutCookie) ==
1232          CalculateCookiePadding(*this, E).isZero());
1233   if (allocSize != allocSizeWithoutCookie) {
1234     assert(E->isArray());
1235     allocation = CGM.getCXXABI().InitializeArrayCookie(*this, allocation,
1236                                                        numElements,
1237                                                        E, allocType);
1238   }
1239
1240   llvm::Type *elementPtrTy
1241     = ConvertTypeForMem(allocType)->getPointerTo(AS);
1242   llvm::Value *result = Builder.CreateBitCast(allocation, elementPtrTy);
1243
1244   EmitNewInitializer(*this, E, allocType, result, numElements,
1245                      allocSizeWithoutCookie);
1246   if (E->isArray()) {
1247     // NewPtr is a pointer to the base element type.  If we're
1248     // allocating an array of arrays, we'll need to cast back to the
1249     // array pointer type.
1250     llvm::Type *resultType = ConvertTypeForMem(E->getType());
1251     if (result->getType() != resultType)
1252       result = Builder.CreateBitCast(result, resultType);
1253   }
1254
1255   // Deactivate the 'operator delete' cleanup if we finished
1256   // initialization.
1257   if (operatorDeleteCleanup.isValid()) {
1258     DeactivateCleanupBlock(operatorDeleteCleanup, cleanupDominator);
1259     cleanupDominator->eraseFromParent();
1260   }
1261
1262   if (nullCheck) {
1263     conditional.end(*this);
1264
1265     llvm::BasicBlock *notNullBB = Builder.GetInsertBlock();
1266     EmitBlock(contBB);
1267
1268     llvm::PHINode *PHI = Builder.CreatePHI(result->getType(), 2);
1269     PHI->addIncoming(result, notNullBB);
1270     PHI->addIncoming(llvm::Constant::getNullValue(result->getType()),
1271                      nullCheckBB);
1272
1273     result = PHI;
1274   }
1275
1276   return result;
1277 }
1278
1279 void CodeGenFunction::EmitDeleteCall(const FunctionDecl *DeleteFD,
1280                                      llvm::Value *Ptr,
1281                                      QualType DeleteTy) {
1282   assert(DeleteFD->getOverloadedOperator() == OO_Delete);
1283
1284   const FunctionProtoType *DeleteFTy =
1285     DeleteFD->getType()->getAs<FunctionProtoType>();
1286
1287   CallArgList DeleteArgs;
1288
1289   // Check if we need to pass the size to the delete operator.
1290   llvm::Value *Size = 0;
1291   QualType SizeTy;
1292   if (DeleteFTy->getNumArgs() == 2) {
1293     SizeTy = DeleteFTy->getArgType(1);
1294     CharUnits DeleteTypeSize = getContext().getTypeSizeInChars(DeleteTy);
1295     Size = llvm::ConstantInt::get(ConvertType(SizeTy),
1296                                   DeleteTypeSize.getQuantity());
1297   }
1298
1299   QualType ArgTy = DeleteFTy->getArgType(0);
1300   llvm::Value *DeletePtr = Builder.CreateBitCast(Ptr, ConvertType(ArgTy));
1301   DeleteArgs.add(RValue::get(DeletePtr), ArgTy);
1302
1303   if (Size)
1304     DeleteArgs.add(RValue::get(Size), SizeTy);
1305
1306   // Emit the call to delete.
1307   EmitNewDeleteCall(*this, DeleteFD, DeleteFTy, DeleteArgs);
1308 }
1309
1310 namespace {
1311   /// Calls the given 'operator delete' on a single object.
1312   struct CallObjectDelete : EHScopeStack::Cleanup {
1313     llvm::Value *Ptr;
1314     const FunctionDecl *OperatorDelete;
1315     QualType ElementType;
1316
1317     CallObjectDelete(llvm::Value *Ptr,
1318                      const FunctionDecl *OperatorDelete,
1319                      QualType ElementType)
1320       : Ptr(Ptr), OperatorDelete(OperatorDelete), ElementType(ElementType) {}
1321
1322     void Emit(CodeGenFunction &CGF, Flags flags) {
1323       CGF.EmitDeleteCall(OperatorDelete, Ptr, ElementType);
1324     }
1325   };
1326 }
1327
1328 /// Emit the code for deleting a single object.
1329 static void EmitObjectDelete(CodeGenFunction &CGF,
1330                              const FunctionDecl *OperatorDelete,
1331                              llvm::Value *Ptr,
1332                              QualType ElementType,
1333                              bool UseGlobalDelete) {
1334   // Find the destructor for the type, if applicable.  If the
1335   // destructor is virtual, we'll just emit the vcall and return.
1336   const CXXDestructorDecl *Dtor = 0;
1337   if (const RecordType *RT = ElementType->getAs<RecordType>()) {
1338     CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
1339     if (RD->hasDefinition() && !RD->hasTrivialDestructor()) {
1340       Dtor = RD->getDestructor();
1341
1342       if (Dtor->isVirtual()) {
1343         if (UseGlobalDelete) {
1344           // If we're supposed to call the global delete, make sure we do so
1345           // even if the destructor throws.
1346
1347           // Derive the complete-object pointer, which is what we need
1348           // to pass to the deallocation function.
1349           llvm::Value *completePtr =
1350             CGF.CGM.getCXXABI().adjustToCompleteObject(CGF, Ptr, ElementType);
1351
1352           CGF.EHStack.pushCleanup<CallObjectDelete>(NormalAndEHCleanup,
1353                                                     completePtr, OperatorDelete,
1354                                                     ElementType);
1355         }
1356
1357         // FIXME: Provide a source location here.
1358         CXXDtorType DtorType = UseGlobalDelete ? Dtor_Complete : Dtor_Deleting;
1359         CGF.CGM.getCXXABI().EmitVirtualDestructorCall(CGF, Dtor, DtorType,
1360                                                       SourceLocation(), Ptr);
1361
1362         if (UseGlobalDelete) {
1363           CGF.PopCleanupBlock();
1364         }
1365
1366         return;
1367       }
1368     }
1369   }
1370
1371   // Make sure that we call delete even if the dtor throws.
1372   // This doesn't have to a conditional cleanup because we're going
1373   // to pop it off in a second.
1374   CGF.EHStack.pushCleanup<CallObjectDelete>(NormalAndEHCleanup,
1375                                             Ptr, OperatorDelete, ElementType);
1376
1377   if (Dtor)
1378     CGF.EmitCXXDestructorCall(Dtor, Dtor_Complete,
1379                               /*ForVirtualBase=*/false,
1380                               /*Delegating=*/false,
1381                               Ptr);
1382   else if (CGF.getLangOpts().ObjCAutoRefCount &&
1383            ElementType->isObjCLifetimeType()) {
1384     switch (ElementType.getObjCLifetime()) {
1385     case Qualifiers::OCL_None:
1386     case Qualifiers::OCL_ExplicitNone:
1387     case Qualifiers::OCL_Autoreleasing:
1388       break;
1389
1390     case Qualifiers::OCL_Strong: {
1391       // Load the pointer value.
1392       llvm::Value *PtrValue = CGF.Builder.CreateLoad(Ptr,
1393                                              ElementType.isVolatileQualified());
1394
1395       CGF.EmitARCRelease(PtrValue, ARCPreciseLifetime);
1396       break;
1397     }
1398
1399     case Qualifiers::OCL_Weak:
1400       CGF.EmitARCDestroyWeak(Ptr);
1401       break;
1402     }
1403   }
1404
1405   CGF.PopCleanupBlock();
1406 }
1407
1408 namespace {
1409   /// Calls the given 'operator delete' on an array of objects.
1410   struct CallArrayDelete : EHScopeStack::Cleanup {
1411     llvm::Value *Ptr;
1412     const FunctionDecl *OperatorDelete;
1413     llvm::Value *NumElements;
1414     QualType ElementType;
1415     CharUnits CookieSize;
1416
1417     CallArrayDelete(llvm::Value *Ptr,
1418                     const FunctionDecl *OperatorDelete,
1419                     llvm::Value *NumElements,
1420                     QualType ElementType,
1421                     CharUnits CookieSize)
1422       : Ptr(Ptr), OperatorDelete(OperatorDelete), NumElements(NumElements),
1423         ElementType(ElementType), CookieSize(CookieSize) {}
1424
1425     void Emit(CodeGenFunction &CGF, Flags flags) {
1426       const FunctionProtoType *DeleteFTy =
1427         OperatorDelete->getType()->getAs<FunctionProtoType>();
1428       assert(DeleteFTy->getNumArgs() == 1 || DeleteFTy->getNumArgs() == 2);
1429
1430       CallArgList Args;
1431
1432       // Pass the pointer as the first argument.
1433       QualType VoidPtrTy = DeleteFTy->getArgType(0);
1434       llvm::Value *DeletePtr
1435         = CGF.Builder.CreateBitCast(Ptr, CGF.ConvertType(VoidPtrTy));
1436       Args.add(RValue::get(DeletePtr), VoidPtrTy);
1437
1438       // Pass the original requested size as the second argument.
1439       if (DeleteFTy->getNumArgs() == 2) {
1440         QualType size_t = DeleteFTy->getArgType(1);
1441         llvm::IntegerType *SizeTy
1442           = cast<llvm::IntegerType>(CGF.ConvertType(size_t));
1443
1444         CharUnits ElementTypeSize =
1445           CGF.CGM.getContext().getTypeSizeInChars(ElementType);
1446
1447         // The size of an element, multiplied by the number of elements.
1448         llvm::Value *Size
1449           = llvm::ConstantInt::get(SizeTy, ElementTypeSize.getQuantity());
1450         Size = CGF.Builder.CreateMul(Size, NumElements);
1451
1452         // Plus the size of the cookie if applicable.
1453         if (!CookieSize.isZero()) {
1454           llvm::Value *CookieSizeV
1455             = llvm::ConstantInt::get(SizeTy, CookieSize.getQuantity());
1456           Size = CGF.Builder.CreateAdd(Size, CookieSizeV);
1457         }
1458
1459         Args.add(RValue::get(Size), size_t);
1460       }
1461
1462       // Emit the call to delete.
1463       EmitNewDeleteCall(CGF, OperatorDelete, DeleteFTy, Args);
1464     }
1465   };
1466 }
1467
1468 /// Emit the code for deleting an array of objects.
1469 static void EmitArrayDelete(CodeGenFunction &CGF,
1470                             const CXXDeleteExpr *E,
1471                             llvm::Value *deletedPtr,
1472                             QualType elementType) {
1473   llvm::Value *numElements = 0;
1474   llvm::Value *allocatedPtr = 0;
1475   CharUnits cookieSize;
1476   CGF.CGM.getCXXABI().ReadArrayCookie(CGF, deletedPtr, E, elementType,
1477                                       numElements, allocatedPtr, cookieSize);
1478
1479   assert(allocatedPtr && "ReadArrayCookie didn't set allocated pointer");
1480
1481   // Make sure that we call delete even if one of the dtors throws.
1482   const FunctionDecl *operatorDelete = E->getOperatorDelete();
1483   CGF.EHStack.pushCleanup<CallArrayDelete>(NormalAndEHCleanup,
1484                                            allocatedPtr, operatorDelete,
1485                                            numElements, elementType,
1486                                            cookieSize);
1487
1488   // Destroy the elements.
1489   if (QualType::DestructionKind dtorKind = elementType.isDestructedType()) {
1490     assert(numElements && "no element count for a type with a destructor!");
1491
1492     llvm::Value *arrayEnd =
1493       CGF.Builder.CreateInBoundsGEP(deletedPtr, numElements, "delete.end");
1494
1495     // Note that it is legal to allocate a zero-length array, and we
1496     // can never fold the check away because the length should always
1497     // come from a cookie.
1498     CGF.emitArrayDestroy(deletedPtr, arrayEnd, elementType,
1499                          CGF.getDestroyer(dtorKind),
1500                          /*checkZeroLength*/ true,
1501                          CGF.needsEHCleanup(dtorKind));
1502   }
1503
1504   // Pop the cleanup block.
1505   CGF.PopCleanupBlock();
1506 }
1507
1508 void CodeGenFunction::EmitCXXDeleteExpr(const CXXDeleteExpr *E) {
1509   const Expr *Arg = E->getArgument();
1510   llvm::Value *Ptr = EmitScalarExpr(Arg);
1511
1512   // Null check the pointer.
1513   llvm::BasicBlock *DeleteNotNull = createBasicBlock("delete.notnull");
1514   llvm::BasicBlock *DeleteEnd = createBasicBlock("delete.end");
1515
1516   llvm::Value *IsNull = Builder.CreateIsNull(Ptr, "isnull");
1517
1518   Builder.CreateCondBr(IsNull, DeleteEnd, DeleteNotNull);
1519   EmitBlock(DeleteNotNull);
1520
1521   // We might be deleting a pointer to array.  If so, GEP down to the
1522   // first non-array element.
1523   // (this assumes that A(*)[3][7] is converted to [3 x [7 x %A]]*)
1524   QualType DeleteTy = Arg->getType()->getAs<PointerType>()->getPointeeType();
1525   if (DeleteTy->isConstantArrayType()) {
1526     llvm::Value *Zero = Builder.getInt32(0);
1527     SmallVector<llvm::Value*,8> GEP;
1528
1529     GEP.push_back(Zero); // point at the outermost array
1530
1531     // For each layer of array type we're pointing at:
1532     while (const ConstantArrayType *Arr
1533              = getContext().getAsConstantArrayType(DeleteTy)) {
1534       // 1. Unpeel the array type.
1535       DeleteTy = Arr->getElementType();
1536
1537       // 2. GEP to the first element of the array.
1538       GEP.push_back(Zero);
1539     }
1540
1541     Ptr = Builder.CreateInBoundsGEP(Ptr, GEP, "del.first");
1542   }
1543
1544   assert(ConvertTypeForMem(DeleteTy) ==
1545          cast<llvm::PointerType>(Ptr->getType())->getElementType());
1546
1547   if (E->isArrayForm()) {
1548     EmitArrayDelete(*this, E, Ptr, DeleteTy);
1549   } else {
1550     EmitObjectDelete(*this, E->getOperatorDelete(), Ptr, DeleteTy,
1551                      E->isGlobalDelete());
1552   }
1553
1554   EmitBlock(DeleteEnd);
1555 }
1556
1557 static llvm::Constant *getBadTypeidFn(CodeGenFunction &CGF) {
1558   // void __cxa_bad_typeid();
1559   llvm::FunctionType *FTy = llvm::FunctionType::get(CGF.VoidTy, false);
1560
1561   return CGF.CGM.CreateRuntimeFunction(FTy, "__cxa_bad_typeid");
1562 }
1563
1564 static void EmitBadTypeidCall(CodeGenFunction &CGF) {
1565   llvm::Value *Fn = getBadTypeidFn(CGF);
1566   CGF.EmitRuntimeCallOrInvoke(Fn).setDoesNotReturn();
1567   CGF.Builder.CreateUnreachable();
1568 }
1569
1570 static llvm::Value *EmitTypeidFromVTable(CodeGenFunction &CGF,
1571                                          const Expr *E,
1572                                          llvm::Type *StdTypeInfoPtrTy) {
1573   // Get the vtable pointer.
1574   llvm::Value *ThisPtr = CGF.EmitLValue(E).getAddress();
1575
1576   // C++ [expr.typeid]p2:
1577   //   If the glvalue expression is obtained by applying the unary * operator to
1578   //   a pointer and the pointer is a null pointer value, the typeid expression
1579   //   throws the std::bad_typeid exception.
1580   if (const UnaryOperator *UO = dyn_cast<UnaryOperator>(E->IgnoreParens())) {
1581     if (UO->getOpcode() == UO_Deref) {
1582       llvm::BasicBlock *BadTypeidBlock =
1583         CGF.createBasicBlock("typeid.bad_typeid");
1584       llvm::BasicBlock *EndBlock =
1585         CGF.createBasicBlock("typeid.end");
1586
1587       llvm::Value *IsNull = CGF.Builder.CreateIsNull(ThisPtr);
1588       CGF.Builder.CreateCondBr(IsNull, BadTypeidBlock, EndBlock);
1589
1590       CGF.EmitBlock(BadTypeidBlock);
1591       EmitBadTypeidCall(CGF);
1592       CGF.EmitBlock(EndBlock);
1593     }
1594   }
1595
1596   llvm::Value *Value = CGF.GetVTablePtr(ThisPtr,
1597                                         StdTypeInfoPtrTy->getPointerTo());
1598
1599   // Load the type info.
1600   Value = CGF.Builder.CreateConstInBoundsGEP1_64(Value, -1ULL);
1601   return CGF.Builder.CreateLoad(Value);
1602 }
1603
1604 llvm::Value *CodeGenFunction::EmitCXXTypeidExpr(const CXXTypeidExpr *E) {
1605   llvm::Type *StdTypeInfoPtrTy =
1606     ConvertType(E->getType())->getPointerTo();
1607
1608   if (E->isTypeOperand()) {
1609     llvm::Constant *TypeInfo =
1610         CGM.GetAddrOfRTTIDescriptor(E->getTypeOperand(getContext()));
1611     return Builder.CreateBitCast(TypeInfo, StdTypeInfoPtrTy);
1612   }
1613
1614   // C++ [expr.typeid]p2:
1615   //   When typeid is applied to a glvalue expression whose type is a
1616   //   polymorphic class type, the result refers to a std::type_info object
1617   //   representing the type of the most derived object (that is, the dynamic
1618   //   type) to which the glvalue refers.
1619   if (E->isPotentiallyEvaluated())
1620     return EmitTypeidFromVTable(*this, E->getExprOperand(),
1621                                 StdTypeInfoPtrTy);
1622
1623   QualType OperandTy = E->getExprOperand()->getType();
1624   return Builder.CreateBitCast(CGM.GetAddrOfRTTIDescriptor(OperandTy),
1625                                StdTypeInfoPtrTy);
1626 }
1627
1628 static llvm::Constant *getDynamicCastFn(CodeGenFunction &CGF) {
1629   // void *__dynamic_cast(const void *sub,
1630   //                      const abi::__class_type_info *src,
1631   //                      const abi::__class_type_info *dst,
1632   //                      std::ptrdiff_t src2dst_offset);
1633
1634   llvm::Type *Int8PtrTy = CGF.Int8PtrTy;
1635   llvm::Type *PtrDiffTy =
1636     CGF.ConvertType(CGF.getContext().getPointerDiffType());
1637
1638   llvm::Type *Args[4] = { Int8PtrTy, Int8PtrTy, Int8PtrTy, PtrDiffTy };
1639
1640   llvm::FunctionType *FTy = llvm::FunctionType::get(Int8PtrTy, Args, false);
1641
1642   // Mark the function as nounwind readonly.
1643   llvm::Attribute::AttrKind FuncAttrs[] = { llvm::Attribute::NoUnwind,
1644                                             llvm::Attribute::ReadOnly };
1645   llvm::AttributeSet Attrs = llvm::AttributeSet::get(
1646       CGF.getLLVMContext(), llvm::AttributeSet::FunctionIndex, FuncAttrs);
1647
1648   return CGF.CGM.CreateRuntimeFunction(FTy, "__dynamic_cast", Attrs);
1649 }
1650
1651 static llvm::Constant *getBadCastFn(CodeGenFunction &CGF) {
1652   // void __cxa_bad_cast();
1653   llvm::FunctionType *FTy = llvm::FunctionType::get(CGF.VoidTy, false);
1654   return CGF.CGM.CreateRuntimeFunction(FTy, "__cxa_bad_cast");
1655 }
1656
1657 static void EmitBadCastCall(CodeGenFunction &CGF) {
1658   llvm::Value *Fn = getBadCastFn(CGF);
1659   CGF.EmitRuntimeCallOrInvoke(Fn).setDoesNotReturn();
1660   CGF.Builder.CreateUnreachable();
1661 }
1662
1663 /// \brief Compute the src2dst_offset hint as described in the
1664 /// Itanium C++ ABI [2.9.7]
1665 static CharUnits computeOffsetHint(ASTContext &Context,
1666                                    const CXXRecordDecl *Src,
1667                                    const CXXRecordDecl *Dst) {
1668   CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
1669                      /*DetectVirtual=*/false);
1670
1671   // If Dst is not derived from Src we can skip the whole computation below and
1672   // return that Src is not a public base of Dst.  Record all inheritance paths.
1673   if (!Dst->isDerivedFrom(Src, Paths))
1674     return CharUnits::fromQuantity(-2ULL);
1675
1676   unsigned NumPublicPaths = 0;
1677   CharUnits Offset;
1678
1679   // Now walk all possible inheritance paths.
1680   for (CXXBasePaths::paths_iterator I = Paths.begin(), E = Paths.end();
1681        I != E; ++I) {
1682     if (I->Access != AS_public) // Ignore non-public inheritance.
1683       continue;
1684
1685     ++NumPublicPaths;
1686
1687     for (CXXBasePath::iterator J = I->begin(), JE = I->end(); J != JE; ++J) {
1688       // If the path contains a virtual base class we can't give any hint.
1689       // -1: no hint.
1690       if (J->Base->isVirtual())
1691         return CharUnits::fromQuantity(-1ULL);
1692
1693       if (NumPublicPaths > 1) // Won't use offsets, skip computation.
1694         continue;
1695
1696       // Accumulate the base class offsets.
1697       const ASTRecordLayout &L = Context.getASTRecordLayout(J->Class);
1698       Offset += L.getBaseClassOffset(J->Base->getType()->getAsCXXRecordDecl());
1699     }
1700   }
1701
1702   // -2: Src is not a public base of Dst.
1703   if (NumPublicPaths == 0)
1704     return CharUnits::fromQuantity(-2ULL);
1705
1706   // -3: Src is a multiple public base type but never a virtual base type.
1707   if (NumPublicPaths > 1)
1708     return CharUnits::fromQuantity(-3ULL);
1709
1710   // Otherwise, the Src type is a unique public nonvirtual base type of Dst.
1711   // Return the offset of Src from the origin of Dst.
1712   return Offset;
1713 }
1714
1715 static llvm::Value *
1716 EmitDynamicCastCall(CodeGenFunction &CGF, llvm::Value *Value,
1717                     QualType SrcTy, QualType DestTy,
1718                     llvm::BasicBlock *CastEnd) {
1719   llvm::Type *PtrDiffLTy =
1720     CGF.ConvertType(CGF.getContext().getPointerDiffType());
1721   llvm::Type *DestLTy = CGF.ConvertType(DestTy);
1722
1723   if (const PointerType *PTy = DestTy->getAs<PointerType>()) {
1724     if (PTy->getPointeeType()->isVoidType()) {
1725       // C++ [expr.dynamic.cast]p7:
1726       //   If T is "pointer to cv void," then the result is a pointer to the
1727       //   most derived object pointed to by v.
1728
1729       // Get the vtable pointer.
1730       llvm::Value *VTable = CGF.GetVTablePtr(Value, PtrDiffLTy->getPointerTo());
1731
1732       // Get the offset-to-top from the vtable.
1733       llvm::Value *OffsetToTop =
1734         CGF.Builder.CreateConstInBoundsGEP1_64(VTable, -2ULL);
1735       OffsetToTop = CGF.Builder.CreateLoad(OffsetToTop, "offset.to.top");
1736
1737       // Finally, add the offset to the pointer.
1738       Value = CGF.EmitCastToVoidPtr(Value);
1739       Value = CGF.Builder.CreateInBoundsGEP(Value, OffsetToTop);
1740
1741       return CGF.Builder.CreateBitCast(Value, DestLTy);
1742     }
1743   }
1744
1745   QualType SrcRecordTy;
1746   QualType DestRecordTy;
1747
1748   if (const PointerType *DestPTy = DestTy->getAs<PointerType>()) {
1749     SrcRecordTy = SrcTy->castAs<PointerType>()->getPointeeType();
1750     DestRecordTy = DestPTy->getPointeeType();
1751   } else {
1752     SrcRecordTy = SrcTy;
1753     DestRecordTy = DestTy->castAs<ReferenceType>()->getPointeeType();
1754   }
1755
1756   assert(SrcRecordTy->isRecordType() && "source type must be a record type!");
1757   assert(DestRecordTy->isRecordType() && "dest type must be a record type!");
1758
1759   llvm::Value *SrcRTTI =
1760     CGF.CGM.GetAddrOfRTTIDescriptor(SrcRecordTy.getUnqualifiedType());
1761   llvm::Value *DestRTTI =
1762     CGF.CGM.GetAddrOfRTTIDescriptor(DestRecordTy.getUnqualifiedType());
1763
1764   // Compute the offset hint.
1765   const CXXRecordDecl *SrcDecl = SrcRecordTy->getAsCXXRecordDecl();
1766   const CXXRecordDecl *DestDecl = DestRecordTy->getAsCXXRecordDecl();
1767   llvm::Value *OffsetHint =
1768     llvm::ConstantInt::get(PtrDiffLTy,
1769                            computeOffsetHint(CGF.getContext(), SrcDecl,
1770                                              DestDecl).getQuantity());
1771
1772   // Emit the call to __dynamic_cast.
1773   Value = CGF.EmitCastToVoidPtr(Value);
1774
1775   llvm::Value *args[] = { Value, SrcRTTI, DestRTTI, OffsetHint };
1776   Value = CGF.EmitNounwindRuntimeCall(getDynamicCastFn(CGF), args);
1777   Value = CGF.Builder.CreateBitCast(Value, DestLTy);
1778
1779   /// C++ [expr.dynamic.cast]p9:
1780   ///   A failed cast to reference type throws std::bad_cast
1781   if (DestTy->isReferenceType()) {
1782     llvm::BasicBlock *BadCastBlock =
1783       CGF.createBasicBlock("dynamic_cast.bad_cast");
1784
1785     llvm::Value *IsNull = CGF.Builder.CreateIsNull(Value);
1786     CGF.Builder.CreateCondBr(IsNull, BadCastBlock, CastEnd);
1787
1788     CGF.EmitBlock(BadCastBlock);
1789     EmitBadCastCall(CGF);
1790   }
1791
1792   return Value;
1793 }
1794
1795 static llvm::Value *EmitDynamicCastToNull(CodeGenFunction &CGF,
1796                                           QualType DestTy) {
1797   llvm::Type *DestLTy = CGF.ConvertType(DestTy);
1798   if (DestTy->isPointerType())
1799     return llvm::Constant::getNullValue(DestLTy);
1800
1801   /// C++ [expr.dynamic.cast]p9:
1802   ///   A failed cast to reference type throws std::bad_cast
1803   EmitBadCastCall(CGF);
1804
1805   CGF.EmitBlock(CGF.createBasicBlock("dynamic_cast.end"));
1806   return llvm::UndefValue::get(DestLTy);
1807 }
1808
1809 llvm::Value *CodeGenFunction::EmitDynamicCast(llvm::Value *Value,
1810                                               const CXXDynamicCastExpr *DCE) {
1811   QualType DestTy = DCE->getTypeAsWritten();
1812
1813   if (DCE->isAlwaysNull())
1814     return EmitDynamicCastToNull(*this, DestTy);
1815
1816   QualType SrcTy = DCE->getSubExpr()->getType();
1817
1818   // C++ [expr.dynamic.cast]p4:
1819   //   If the value of v is a null pointer value in the pointer case, the result
1820   //   is the null pointer value of type T.
1821   bool ShouldNullCheckSrcValue = SrcTy->isPointerType();
1822
1823   llvm::BasicBlock *CastNull = 0;
1824   llvm::BasicBlock *CastNotNull = 0;
1825   llvm::BasicBlock *CastEnd = createBasicBlock("dynamic_cast.end");
1826
1827   if (ShouldNullCheckSrcValue) {
1828     CastNull = createBasicBlock("dynamic_cast.null");
1829     CastNotNull = createBasicBlock("dynamic_cast.notnull");
1830
1831     llvm::Value *IsNull = Builder.CreateIsNull(Value);
1832     Builder.CreateCondBr(IsNull, CastNull, CastNotNull);
1833     EmitBlock(CastNotNull);
1834   }
1835
1836   Value = EmitDynamicCastCall(*this, Value, SrcTy, DestTy, CastEnd);
1837
1838   if (ShouldNullCheckSrcValue) {
1839     EmitBranch(CastEnd);
1840
1841     EmitBlock(CastNull);
1842     EmitBranch(CastEnd);
1843   }
1844
1845   EmitBlock(CastEnd);
1846
1847   if (ShouldNullCheckSrcValue) {
1848     llvm::PHINode *PHI = Builder.CreatePHI(Value->getType(), 2);
1849     PHI->addIncoming(Value, CastNotNull);
1850     PHI->addIncoming(llvm::Constant::getNullValue(Value->getType()), CastNull);
1851
1852     Value = PHI;
1853   }
1854
1855   return Value;
1856 }
1857
1858 void CodeGenFunction::EmitLambdaExpr(const LambdaExpr *E, AggValueSlot Slot) {
1859   RunCleanupsScope Scope(*this);
1860   LValue SlotLV = MakeAddrLValue(Slot.getAddr(), E->getType(),
1861                                  Slot.getAlignment());
1862
1863   CXXRecordDecl::field_iterator CurField = E->getLambdaClass()->field_begin();
1864   for (LambdaExpr::capture_init_iterator i = E->capture_init_begin(),
1865                                          e = E->capture_init_end();
1866        i != e; ++i, ++CurField) {
1867     // Emit initialization
1868
1869     LValue LV = EmitLValueForFieldInitialization(SlotLV, *CurField);
1870     ArrayRef<VarDecl *> ArrayIndexes;
1871     if (CurField->getType()->isArrayType())
1872       ArrayIndexes = E->getCaptureInitIndexVars(i);
1873     EmitInitializerForField(*CurField, LV, *i, ArrayIndexes);
1874   }
1875 }