CGExprCXX.cpp revision 0339d72d7f853d90088a4d8639fb50810533e791 
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 "CGCXXABI.h"
16#include "CGObjCRuntime.h"
17#include "llvm/Intrinsics.h"
18using namespace clang;
19using namespace CodeGen;
20
21RValue CodeGenFunction::EmitCXXMemberCall(const CXXMethodDecl *MD,
22                                          llvm::Value *Callee,
23                                          ReturnValueSlot ReturnValue,
24                                          llvm::Value *This,
25                                          llvm::Value *VTT,
26                                          CallExpr::const_arg_iterator ArgBeg,
27                                          CallExpr::const_arg_iterator ArgEnd) {
28  assert(MD->isInstance() &&
29         "Trying to emit a member call expr on a static method!");
30
31  const FunctionProtoType *FPT = MD->getType()->getAs<FunctionProtoType>();
32
33  CallArgList Args;
34
35  // Push the this ptr.
36  Args.push_back(std::make_pair(RValue::get(This),
37                                MD->getThisType(getContext())));
38
39  // If there is a VTT parameter, emit it.
40  if (VTT) {
41    QualType T = getContext().getPointerType(getContext().VoidPtrTy);
42    Args.push_back(std::make_pair(RValue::get(VTT), T));
43  }
44
45  // And the rest of the call args
46  EmitCallArgs(Args, FPT, ArgBeg, ArgEnd);
47
48  QualType ResultType = FPT->getResultType();
49  return EmitCall(CGM.getTypes().getFunctionInfo(ResultType, Args,
50                                                 FPT->getExtInfo()),
51                  Callee, ReturnValue, Args, MD);
52}
53
54/// canDevirtualizeMemberFunctionCalls - Checks whether virtual calls on given
55/// expr can be devirtualized.
56static bool canDevirtualizeMemberFunctionCalls(const Expr *Base) {
57  if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Base)) {
58    if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
59      // This is a record decl. We know the type and can devirtualize it.
60      return VD->getType()->isRecordType();
61    }
62
63    return false;
64  }
65
66  // We can always devirtualize calls on temporary object expressions.
67  if (isa<CXXConstructExpr>(Base))
68    return true;
69
70  // And calls on bound temporaries.
71  if (isa<CXXBindTemporaryExpr>(Base))
72    return true;
73
74  // Check if this is a call expr that returns a record type.
75  if (const CallExpr *CE = dyn_cast<CallExpr>(Base))
76    return CE->getCallReturnType()->isRecordType();
77
78  // We can't devirtualize the call.
79  return false;
80}
81
82RValue CodeGenFunction::EmitCXXMemberCallExpr(const CXXMemberCallExpr *CE,
83                                              ReturnValueSlot ReturnValue) {
84  if (isa<BinaryOperator>(CE->getCallee()->IgnoreParens()))
85    return EmitCXXMemberPointerCallExpr(CE, ReturnValue);
86
87  const MemberExpr *ME = cast<MemberExpr>(CE->getCallee()->IgnoreParens());
88  const CXXMethodDecl *MD = cast<CXXMethodDecl>(ME->getMemberDecl());
89
90  if (MD->isStatic()) {
91    // The method is static, emit it as we would a regular call.
92    llvm::Value *Callee = CGM.GetAddrOfFunction(MD);
93    return EmitCall(getContext().getPointerType(MD->getType()), Callee,
94                    ReturnValue, CE->arg_begin(), CE->arg_end());
95  }
96
97  // Compute the object pointer.
98  llvm::Value *This;
99  if (ME->isArrow())
100    This = EmitScalarExpr(ME->getBase());
101  else {
102    LValue BaseLV = EmitLValue(ME->getBase());
103    if (BaseLV.isPropertyRef() || BaseLV.isKVCRef()) {
104      QualType QT = ME->getBase()->getType();
105      RValue RV =
106        BaseLV.isPropertyRef() ? EmitLoadOfPropertyRefLValue(BaseLV, QT)
107          : EmitLoadOfKVCRefLValue(BaseLV, QT);
108      This = RV.isScalar() ? RV.getScalarVal() : RV.getAggregateAddr();
109    }
110    else
111      This = BaseLV.getAddress();
112  }
113
114  if (MD->isTrivial()) {
115    if (isa<CXXDestructorDecl>(MD)) return RValue::get(0);
116
117    assert(MD->isCopyAssignment() && "unknown trivial member function");
118    // We don't like to generate the trivial copy assignment operator when
119    // it isn't necessary; just produce the proper effect here.
120    llvm::Value *RHS = EmitLValue(*CE->arg_begin()).getAddress();
121    EmitAggregateCopy(This, RHS, CE->getType());
122    return RValue::get(This);
123  }
124
125  // Compute the function type we're calling.
126  const CGFunctionInfo &FInfo =
127    (isa<CXXDestructorDecl>(MD)
128     ? CGM.getTypes().getFunctionInfo(cast<CXXDestructorDecl>(MD),
129                                      Dtor_Complete)
130     : CGM.getTypes().getFunctionInfo(MD));
131
132  const FunctionProtoType *FPT = MD->getType()->getAs<FunctionProtoType>();
133  const llvm::Type *Ty
134    = CGM.getTypes().GetFunctionType(FInfo, FPT->isVariadic());
135
136  // C++ [class.virtual]p12:
137  //   Explicit qualification with the scope operator (5.1) suppresses the
138  //   virtual call mechanism.
139  //
140  // We also don't emit a virtual call if the base expression has a record type
141  // because then we know what the type is.
142  bool UseVirtualCall = MD->isVirtual() && !ME->hasQualifier()
143                     && !canDevirtualizeMemberFunctionCalls(ME->getBase());
144
145  llvm::Value *Callee;
146  if (const CXXDestructorDecl *Dtor = dyn_cast<CXXDestructorDecl>(MD)) {
147    if (UseVirtualCall) {
148      Callee = BuildVirtualCall(Dtor, Dtor_Complete, This, Ty);
149    } else {
150      Callee = CGM.GetAddrOfFunction(GlobalDecl(Dtor, Dtor_Complete), Ty);
151    }
152  } else if (UseVirtualCall) {
153    Callee = BuildVirtualCall(MD, This, Ty);
154  } else {
155    Callee = CGM.GetAddrOfFunction(MD, Ty);
156  }
157
158  return EmitCXXMemberCall(MD, Callee, ReturnValue, This, /*VTT=*/0,
159                           CE->arg_begin(), CE->arg_end());
160}
161
162RValue
163CodeGenFunction::EmitCXXMemberPointerCallExpr(const CXXMemberCallExpr *E,
164                                              ReturnValueSlot ReturnValue) {
165  const BinaryOperator *BO =
166      cast<BinaryOperator>(E->getCallee()->IgnoreParens());
167  const Expr *BaseExpr = BO->getLHS();
168  const Expr *MemFnExpr = BO->getRHS();
169
170  const MemberPointerType *MPT =
171    MemFnExpr->getType()->getAs<MemberPointerType>();
172
173  const FunctionProtoType *FPT =
174    MPT->getPointeeType()->getAs<FunctionProtoType>();
175  const CXXRecordDecl *RD =
176    cast<CXXRecordDecl>(MPT->getClass()->getAs<RecordType>()->getDecl());
177
178  // Get the member function pointer.
179  llvm::Value *MemFnPtr = EmitScalarExpr(MemFnExpr);
180
181  // Emit the 'this' pointer.
182  llvm::Value *This;
183
184  if (BO->getOpcode() == BO_PtrMemI)
185    This = EmitScalarExpr(BaseExpr);
186  else
187    This = EmitLValue(BaseExpr).getAddress();
188
189  // Ask the ABI to load the callee.  Note that This is modified.
190  llvm::Value *Callee =
191    CGM.getCXXABI().EmitLoadOfMemberFunctionPointer(CGF, This, MemFnPtr, MPT);
192
193  CallArgList Args;
194
195  QualType ThisType =
196    getContext().getPointerType(getContext().getTagDeclType(RD));
197
198  // Push the this ptr.
199  Args.push_back(std::make_pair(RValue::get(This), ThisType));
200
201  // And the rest of the call args
202  EmitCallArgs(Args, FPT, E->arg_begin(), E->arg_end());
203  const FunctionType *BO_FPT = BO->getType()->getAs<FunctionProtoType>();
204  return EmitCall(CGM.getTypes().getFunctionInfo(Args, BO_FPT), Callee,
205                  ReturnValue, Args);
206}
207
208RValue
209CodeGenFunction::EmitCXXOperatorMemberCallExpr(const CXXOperatorCallExpr *E,
210                                               const CXXMethodDecl *MD,
211                                               ReturnValueSlot ReturnValue) {
212  assert(MD->isInstance() &&
213         "Trying to emit a member call expr on a static method!");
214  if (MD->isCopyAssignment()) {
215    const CXXRecordDecl *ClassDecl = cast<CXXRecordDecl>(MD->getDeclContext());
216    if (ClassDecl->hasTrivialCopyAssignment()) {
217      assert(!ClassDecl->hasUserDeclaredCopyAssignment() &&
218             "EmitCXXOperatorMemberCallExpr - user declared copy assignment");
219      LValue LV = EmitLValue(E->getArg(0));
220      llvm::Value *This;
221      if (LV.isPropertyRef() || LV.isKVCRef()) {
222        llvm::Value *AggLoc  = CreateMemTemp(E->getArg(1)->getType());
223        EmitAggExpr(E->getArg(1), AggLoc, false /*VolatileDest*/);
224        if (LV.isPropertyRef())
225          EmitObjCPropertySet(LV.getPropertyRefExpr(),
226                              RValue::getAggregate(AggLoc,
227                                                   false /*VolatileDest*/));
228        else
229          EmitObjCPropertySet(LV.getKVCRefExpr(),
230                              RValue::getAggregate(AggLoc,
231                                                   false /*VolatileDest*/));
232        return RValue::getAggregate(0, false);
233      }
234      else
235        This = LV.getAddress();
236
237      llvm::Value *Src = EmitLValue(E->getArg(1)).getAddress();
238      QualType Ty = E->getType();
239      EmitAggregateCopy(This, Src, Ty);
240      return RValue::get(This);
241    }
242  }
243
244  const FunctionProtoType *FPT = MD->getType()->getAs<FunctionProtoType>();
245  const llvm::Type *Ty =
246    CGM.getTypes().GetFunctionType(CGM.getTypes().getFunctionInfo(MD),
247                                   FPT->isVariadic());
248  LValue LV = EmitLValue(E->getArg(0));
249  llvm::Value *This;
250  if (LV.isPropertyRef() || LV.isKVCRef()) {
251    QualType QT = E->getArg(0)->getType();
252    RValue RV =
253      LV.isPropertyRef() ? EmitLoadOfPropertyRefLValue(LV, QT)
254                         : EmitLoadOfKVCRefLValue(LV, QT);
255    assert (!RV.isScalar() && "EmitCXXOperatorMemberCallExpr");
256    This = RV.getAggregateAddr();
257  }
258  else
259    This = LV.getAddress();
260
261  llvm::Value *Callee;
262  if (MD->isVirtual() && !canDevirtualizeMemberFunctionCalls(E->getArg(0)))
263    Callee = BuildVirtualCall(MD, This, Ty);
264  else
265    Callee = CGM.GetAddrOfFunction(MD, Ty);
266
267  return EmitCXXMemberCall(MD, Callee, ReturnValue, This, /*VTT=*/0,
268                           E->arg_begin() + 1, E->arg_end());
269}
270
271void
272CodeGenFunction::EmitCXXConstructExpr(llvm::Value *Dest,
273                                      const CXXConstructExpr *E) {
274  assert(Dest && "Must have a destination!");
275  const CXXConstructorDecl *CD = E->getConstructor();
276
277  // If we require zero initialization before (or instead of) calling the
278  // constructor, as can be the case with a non-user-provided default
279  // constructor, emit the zero initialization now.
280  if (E->requiresZeroInitialization())
281    EmitNullInitialization(Dest, E->getType());
282
283
284  // If this is a call to a trivial default constructor, do nothing.
285  if (CD->isTrivial() && CD->isDefaultConstructor())
286    return;
287
288  // Code gen optimization to eliminate copy constructor and return
289  // its first argument instead, if in fact that argument is a temporary
290  // object.
291  if (getContext().getLangOptions().ElideConstructors && E->isElidable()) {
292    if (const Expr *Arg = E->getArg(0)->getTemporaryObject()) {
293      EmitAggExpr(Arg, Dest, false);
294      return;
295    }
296  }
297
298  const ConstantArrayType *Array
299    = getContext().getAsConstantArrayType(E->getType());
300  if (Array) {
301    QualType BaseElementTy = getContext().getBaseElementType(Array);
302    const llvm::Type *BasePtr = ConvertType(BaseElementTy);
303    BasePtr = llvm::PointerType::getUnqual(BasePtr);
304    llvm::Value *BaseAddrPtr =
305      Builder.CreateBitCast(Dest, BasePtr);
306
307    EmitCXXAggrConstructorCall(CD, Array, BaseAddrPtr,
308                               E->arg_begin(), E->arg_end());
309  }
310  else {
311    CXXCtorType Type =
312      (E->getConstructionKind() == CXXConstructExpr::CK_Complete)
313      ? Ctor_Complete : Ctor_Base;
314    bool ForVirtualBase =
315      E->getConstructionKind() == CXXConstructExpr::CK_VirtualBase;
316
317    // Call the constructor.
318    EmitCXXConstructorCall(CD, Type, ForVirtualBase, Dest,
319                           E->arg_begin(), E->arg_end());
320  }
321}
322
323/// Check whether the given operator new[] is the global placement
324/// operator new[].
325static bool IsPlacementOperatorNewArray(ASTContext &Ctx,
326                                        const FunctionDecl *Fn) {
327  // Must be in global scope.  Note that allocation functions can't be
328  // declared in namespaces.
329  if (!Fn->getDeclContext()->getRedeclContext()->isFileContext())
330    return false;
331
332  // Signature must be void *operator new[](size_t, void*).
333  // The size_t is common to all operator new[]s.
334  if (Fn->getNumParams() != 2)
335    return false;
336
337  CanQualType ParamType = Ctx.getCanonicalType(Fn->getParamDecl(1)->getType());
338  return (ParamType == Ctx.VoidPtrTy);
339}
340
341static CharUnits CalculateCookiePadding(CodeGenFunction &CGF,
342                                        const CXXNewExpr *E) {
343  if (!E->isArray())
344    return CharUnits::Zero();
345
346  // No cookie is required if the new operator being used is
347  // ::operator new[](size_t, void*).
348  const FunctionDecl *OperatorNew = E->getOperatorNew();
349  if (IsPlacementOperatorNewArray(CGF.getContext(), OperatorNew))
350    return CharUnits::Zero();
351
352  return CGF.CGM.getCXXABI().GetArrayCookieSize(E->getAllocatedType());
353}
354
355static llvm::Value *EmitCXXNewAllocSize(ASTContext &Context,
356                                        CodeGenFunction &CGF,
357                                        const CXXNewExpr *E,
358                                        llvm::Value *&NumElements,
359                                        llvm::Value *&SizeWithoutCookie) {
360  QualType ElemType = E->getAllocatedType();
361
362  const llvm::IntegerType *SizeTy =
363    cast<llvm::IntegerType>(CGF.ConvertType(CGF.getContext().getSizeType()));
364
365  CharUnits TypeSize = CGF.getContext().getTypeSizeInChars(ElemType);
366
367  if (!E->isArray()) {
368    SizeWithoutCookie = llvm::ConstantInt::get(SizeTy, TypeSize.getQuantity());
369    return SizeWithoutCookie;
370  }
371
372  // Figure out the cookie size.
373  CharUnits CookieSize = CalculateCookiePadding(CGF, E);
374
375  // Emit the array size expression.
376  // We multiply the size of all dimensions for NumElements.
377  // e.g for 'int[2][3]', ElemType is 'int' and NumElements is 6.
378  NumElements = CGF.EmitScalarExpr(E->getArraySize());
379  assert(NumElements->getType() == SizeTy && "element count not a size_t");
380
381  uint64_t ArraySizeMultiplier = 1;
382  while (const ConstantArrayType *CAT
383             = CGF.getContext().getAsConstantArrayType(ElemType)) {
384    ElemType = CAT->getElementType();
385    ArraySizeMultiplier *= CAT->getSize().getZExtValue();
386  }
387
388  llvm::Value *Size;
389
390  // If someone is doing 'new int[42]' there is no need to do a dynamic check.
391  // Don't bloat the -O0 code.
392  if (llvm::ConstantInt *NumElementsC =
393        dyn_cast<llvm::ConstantInt>(NumElements)) {
394    llvm::APInt NEC = NumElementsC->getValue();
395    unsigned SizeWidth = NEC.getBitWidth();
396
397    // Determine if there is an overflow here by doing an extended multiply.
398    NEC.zext(SizeWidth*2);
399    llvm::APInt SC(SizeWidth*2, TypeSize.getQuantity());
400    SC *= NEC;
401
402    if (!CookieSize.isZero()) {
403      // Save the current size without a cookie.  We don't care if an
404      // overflow's already happened because SizeWithoutCookie isn't
405      // used if the allocator returns null or throws, as it should
406      // always do on an overflow.
407      llvm::APInt SWC = SC;
408      SWC.trunc(SizeWidth);
409      SizeWithoutCookie = llvm::ConstantInt::get(SizeTy, SWC);
410
411      // Add the cookie size.
412      SC += llvm::APInt(SizeWidth*2, CookieSize.getQuantity());
413    }
414
415    if (SC.countLeadingZeros() >= SizeWidth) {
416      SC.trunc(SizeWidth);
417      Size = llvm::ConstantInt::get(SizeTy, SC);
418    } else {
419      // On overflow, produce a -1 so operator new throws.
420      Size = llvm::Constant::getAllOnesValue(SizeTy);
421    }
422
423    // Scale NumElements while we're at it.
424    uint64_t N = NEC.getZExtValue() * ArraySizeMultiplier;
425    NumElements = llvm::ConstantInt::get(SizeTy, N);
426
427  // Otherwise, we don't need to do an overflow-checked multiplication if
428  // we're multiplying by one.
429  } else if (TypeSize.isOne()) {
430    assert(ArraySizeMultiplier == 1);
431
432    Size = NumElements;
433
434    // If we need a cookie, add its size in with an overflow check.
435    // This is maybe a little paranoid.
436    if (!CookieSize.isZero()) {
437      SizeWithoutCookie = Size;
438
439      llvm::Value *CookieSizeV
440        = llvm::ConstantInt::get(SizeTy, CookieSize.getQuantity());
441
442      const llvm::Type *Types[] = { SizeTy };
443      llvm::Value *UAddF
444        = CGF.CGM.getIntrinsic(llvm::Intrinsic::uadd_with_overflow, Types, 1);
445      llvm::Value *AddRes
446        = CGF.Builder.CreateCall2(UAddF, Size, CookieSizeV);
447
448      Size = CGF.Builder.CreateExtractValue(AddRes, 0);
449      llvm::Value *DidOverflow = CGF.Builder.CreateExtractValue(AddRes, 1);
450      Size = CGF.Builder.CreateSelect(DidOverflow,
451                                      llvm::ConstantInt::get(SizeTy, -1),
452                                      Size);
453    }
454
455  // Otherwise use the int.umul.with.overflow intrinsic.
456  } else {
457    llvm::Value *OutermostElementSize
458      = llvm::ConstantInt::get(SizeTy, TypeSize.getQuantity());
459
460    llvm::Value *NumOutermostElements = NumElements;
461
462    // Scale NumElements by the array size multiplier.  This might
463    // overflow, but only if the multiplication below also overflows,
464    // in which case this multiplication isn't used.
465    if (ArraySizeMultiplier != 1)
466      NumElements = CGF.Builder.CreateMul(NumElements,
467                         llvm::ConstantInt::get(SizeTy, ArraySizeMultiplier));
468
469    // The requested size of the outermost array is non-constant.
470    // Multiply that by the static size of the elements of that array;
471    // on unsigned overflow, set the size to -1 to trigger an
472    // exception from the allocation routine.  This is sufficient to
473    // prevent buffer overruns from the allocator returning a
474    // seemingly valid pointer to insufficient space.  This idea comes
475    // originally from MSVC, and GCC has an open bug requesting
476    // similar behavior:
477    //   http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19351
478    //
479    // This will not be sufficient for C++0x, which requires a
480    // specific exception class (std::bad_array_new_length).
481    // That will require ABI support that has not yet been specified.
482    const llvm::Type *Types[] = { SizeTy };
483    llvm::Value *UMulF
484      = CGF.CGM.getIntrinsic(llvm::Intrinsic::umul_with_overflow, Types, 1);
485    llvm::Value *MulRes = CGF.Builder.CreateCall2(UMulF, NumOutermostElements,
486                                                  OutermostElementSize);
487
488    // The overflow bit.
489    llvm::Value *DidOverflow = CGF.Builder.CreateExtractValue(MulRes, 1);
490
491    // The result of the multiplication.
492    Size = CGF.Builder.CreateExtractValue(MulRes, 0);
493
494    // If we have a cookie, we need to add that size in, too.
495    if (!CookieSize.isZero()) {
496      SizeWithoutCookie = Size;
497
498      llvm::Value *CookieSizeV
499        = llvm::ConstantInt::get(SizeTy, CookieSize.getQuantity());
500      llvm::Value *UAddF
501        = CGF.CGM.getIntrinsic(llvm::Intrinsic::uadd_with_overflow, Types, 1);
502      llvm::Value *AddRes
503        = CGF.Builder.CreateCall2(UAddF, SizeWithoutCookie, CookieSizeV);
504
505      Size = CGF.Builder.CreateExtractValue(AddRes, 0);
506
507      llvm::Value *AddDidOverflow = CGF.Builder.CreateExtractValue(AddRes, 1);
508      DidOverflow = CGF.Builder.CreateAnd(DidOverflow, AddDidOverflow);
509    }
510
511    Size = CGF.Builder.CreateSelect(DidOverflow,
512                                    llvm::ConstantInt::get(SizeTy, -1),
513                                    Size);
514  }
515
516  if (CookieSize.isZero())
517    SizeWithoutCookie = Size;
518  else
519    assert(SizeWithoutCookie && "didn't set SizeWithoutCookie?");
520
521  return Size;
522}
523
524static void StoreAnyExprIntoOneUnit(CodeGenFunction &CGF, const CXXNewExpr *E,
525                                    llvm::Value *NewPtr) {
526
527  assert(E->getNumConstructorArgs() == 1 &&
528         "Can only have one argument to initializer of POD type.");
529
530  const Expr *Init = E->getConstructorArg(0);
531  QualType AllocType = E->getAllocatedType();
532
533  unsigned Alignment =
534    CGF.getContext().getTypeAlignInChars(AllocType).getQuantity();
535  if (!CGF.hasAggregateLLVMType(AllocType))
536    CGF.EmitStoreOfScalar(CGF.EmitScalarExpr(Init), NewPtr,
537                          AllocType.isVolatileQualified(), Alignment,
538                          AllocType);
539  else if (AllocType->isAnyComplexType())
540    CGF.EmitComplexExprIntoAddr(Init, NewPtr,
541                                AllocType.isVolatileQualified());
542  else
543    CGF.EmitAggExpr(Init, NewPtr, AllocType.isVolatileQualified());
544}
545
546void
547CodeGenFunction::EmitNewArrayInitializer(const CXXNewExpr *E,
548                                         llvm::Value *NewPtr,
549                                         llvm::Value *NumElements) {
550  // We have a POD type.
551  if (E->getNumConstructorArgs() == 0)
552    return;
553
554  const llvm::Type *SizeTy = ConvertType(getContext().getSizeType());
555
556  // Create a temporary for the loop index and initialize it with 0.
557  llvm::Value *IndexPtr = CreateTempAlloca(SizeTy, "loop.index");
558  llvm::Value *Zero = llvm::Constant::getNullValue(SizeTy);
559  Builder.CreateStore(Zero, IndexPtr);
560
561  // Start the loop with a block that tests the condition.
562  llvm::BasicBlock *CondBlock = createBasicBlock("for.cond");
563  llvm::BasicBlock *AfterFor = createBasicBlock("for.end");
564
565  EmitBlock(CondBlock);
566
567  llvm::BasicBlock *ForBody = createBasicBlock("for.body");
568
569  // Generate: if (loop-index < number-of-elements fall to the loop body,
570  // otherwise, go to the block after the for-loop.
571  llvm::Value *Counter = Builder.CreateLoad(IndexPtr);
572  llvm::Value *IsLess = Builder.CreateICmpULT(Counter, NumElements, "isless");
573  // If the condition is true, execute the body.
574  Builder.CreateCondBr(IsLess, ForBody, AfterFor);
575
576  EmitBlock(ForBody);
577
578  llvm::BasicBlock *ContinueBlock = createBasicBlock("for.inc");
579  // Inside the loop body, emit the constructor call on the array element.
580  Counter = Builder.CreateLoad(IndexPtr);
581  llvm::Value *Address = Builder.CreateInBoundsGEP(NewPtr, Counter,
582                                                   "arrayidx");
583  StoreAnyExprIntoOneUnit(*this, E, Address);
584
585  EmitBlock(ContinueBlock);
586
587  // Emit the increment of the loop counter.
588  llvm::Value *NextVal = llvm::ConstantInt::get(SizeTy, 1);
589  Counter = Builder.CreateLoad(IndexPtr);
590  NextVal = Builder.CreateAdd(Counter, NextVal, "inc");
591  Builder.CreateStore(NextVal, IndexPtr);
592
593  // Finally, branch back up to the condition for the next iteration.
594  EmitBranch(CondBlock);
595
596  // Emit the fall-through block.
597  EmitBlock(AfterFor, true);
598}
599
600static void EmitZeroMemSet(CodeGenFunction &CGF, QualType T,
601                           llvm::Value *NewPtr, llvm::Value *Size) {
602  llvm::LLVMContext &VMContext = CGF.CGM.getLLVMContext();
603  const llvm::Type *BP = llvm::Type::getInt8PtrTy(VMContext);
604  if (NewPtr->getType() != BP)
605    NewPtr = CGF.Builder.CreateBitCast(NewPtr, BP, "tmp");
606
607  CGF.Builder.CreateCall5(CGF.CGM.getMemSetFn(BP, CGF.IntPtrTy), NewPtr,
608                llvm::Constant::getNullValue(llvm::Type::getInt8Ty(VMContext)),
609                          Size,
610                    llvm::ConstantInt::get(CGF.Int32Ty,
611                                           CGF.getContext().getTypeAlign(T)/8),
612                          llvm::ConstantInt::get(llvm::Type::getInt1Ty(VMContext),
613                                                 0));
614}
615
616static void EmitNewInitializer(CodeGenFunction &CGF, const CXXNewExpr *E,
617                               llvm::Value *NewPtr,
618                               llvm::Value *NumElements,
619                               llvm::Value *AllocSizeWithoutCookie) {
620  if (E->isArray()) {
621    if (CXXConstructorDecl *Ctor = E->getConstructor()) {
622      bool RequiresZeroInitialization = false;
623      if (Ctor->getParent()->hasTrivialConstructor()) {
624        // If new expression did not specify value-initialization, then there
625        // is no initialization.
626        if (!E->hasInitializer() || Ctor->getParent()->isEmpty())
627          return;
628
629        if (CGF.CGM.getTypes().isZeroInitializable(E->getAllocatedType())) {
630          // Optimization: since zero initialization will just set the memory
631          // to all zeroes, generate a single memset to do it in one shot.
632          EmitZeroMemSet(CGF, E->getAllocatedType(), NewPtr,
633                         AllocSizeWithoutCookie);
634          return;
635        }
636
637        RequiresZeroInitialization = true;
638      }
639
640      CGF.EmitCXXAggrConstructorCall(Ctor, NumElements, NewPtr,
641                                     E->constructor_arg_begin(),
642                                     E->constructor_arg_end(),
643                                     RequiresZeroInitialization);
644      return;
645    } else if (E->getNumConstructorArgs() == 1 &&
646               isa<ImplicitValueInitExpr>(E->getConstructorArg(0))) {
647      // Optimization: since zero initialization will just set the memory
648      // to all zeroes, generate a single memset to do it in one shot.
649      EmitZeroMemSet(CGF, E->getAllocatedType(), NewPtr,
650                     AllocSizeWithoutCookie);
651      return;
652    } else {
653      CGF.EmitNewArrayInitializer(E, NewPtr, NumElements);
654      return;
655    }
656  }
657
658  if (CXXConstructorDecl *Ctor = E->getConstructor()) {
659    // Per C++ [expr.new]p15, if we have an initializer, then we're performing
660    // direct initialization. C++ [dcl.init]p5 requires that we
661    // zero-initialize storage if there are no user-declared constructors.
662    if (E->hasInitializer() &&
663        !Ctor->getParent()->hasUserDeclaredConstructor() &&
664        !Ctor->getParent()->isEmpty())
665      CGF.EmitNullInitialization(NewPtr, E->getAllocatedType());
666
667    CGF.EmitCXXConstructorCall(Ctor, Ctor_Complete, /*ForVirtualBase=*/false,
668                               NewPtr, E->constructor_arg_begin(),
669                               E->constructor_arg_end());
670
671    return;
672  }
673  // We have a POD type.
674  if (E->getNumConstructorArgs() == 0)
675    return;
676
677  StoreAnyExprIntoOneUnit(CGF, E, NewPtr);
678}
679
680llvm::Value *CodeGenFunction::EmitCXXNewExpr(const CXXNewExpr *E) {
681  QualType AllocType = E->getAllocatedType();
682  if (AllocType->isArrayType())
683    while (const ArrayType *AType = getContext().getAsArrayType(AllocType))
684      AllocType = AType->getElementType();
685
686  FunctionDecl *NewFD = E->getOperatorNew();
687  const FunctionProtoType *NewFTy = NewFD->getType()->getAs<FunctionProtoType>();
688
689  CallArgList NewArgs;
690
691  // The allocation size is the first argument.
692  QualType SizeTy = getContext().getSizeType();
693
694  llvm::Value *NumElements = 0;
695  llvm::Value *AllocSizeWithoutCookie = 0;
696  llvm::Value *AllocSize = EmitCXXNewAllocSize(getContext(),
697                                               *this, E, NumElements,
698                                               AllocSizeWithoutCookie);
699
700  NewArgs.push_back(std::make_pair(RValue::get(AllocSize), SizeTy));
701
702  // Emit the rest of the arguments.
703  // FIXME: Ideally, this should just use EmitCallArgs.
704  CXXNewExpr::const_arg_iterator NewArg = E->placement_arg_begin();
705
706  // First, use the types from the function type.
707  // We start at 1 here because the first argument (the allocation size)
708  // has already been emitted.
709  for (unsigned i = 1, e = NewFTy->getNumArgs(); i != e; ++i, ++NewArg) {
710    QualType ArgType = NewFTy->getArgType(i);
711
712    assert(getContext().getCanonicalType(ArgType.getNonReferenceType()).
713           getTypePtr() ==
714           getContext().getCanonicalType(NewArg->getType()).getTypePtr() &&
715           "type mismatch in call argument!");
716
717    NewArgs.push_back(std::make_pair(EmitCallArg(*NewArg, ArgType),
718                                     ArgType));
719
720  }
721
722  // Either we've emitted all the call args, or we have a call to a
723  // variadic function.
724  assert((NewArg == E->placement_arg_end() || NewFTy->isVariadic()) &&
725         "Extra arguments in non-variadic function!");
726
727  // If we still have any arguments, emit them using the type of the argument.
728  for (CXXNewExpr::const_arg_iterator NewArgEnd = E->placement_arg_end();
729       NewArg != NewArgEnd; ++NewArg) {
730    QualType ArgType = NewArg->getType();
731    NewArgs.push_back(std::make_pair(EmitCallArg(*NewArg, ArgType),
732                                     ArgType));
733  }
734
735  // Emit the call to new.
736  RValue RV =
737    EmitCall(CGM.getTypes().getFunctionInfo(NewArgs, NewFTy),
738             CGM.GetAddrOfFunction(NewFD), ReturnValueSlot(), NewArgs, NewFD);
739
740  // If an allocation function is declared with an empty exception specification
741  // it returns null to indicate failure to allocate storage. [expr.new]p13.
742  // (We don't need to check for null when there's no new initializer and
743  // we're allocating a POD type).
744  bool NullCheckResult = NewFTy->hasEmptyExceptionSpec() &&
745    !(AllocType->isPODType() && !E->hasInitializer());
746
747  llvm::BasicBlock *NullCheckSource = 0;
748  llvm::BasicBlock *NewNotNull = 0;
749  llvm::BasicBlock *NewEnd = 0;
750
751  llvm::Value *NewPtr = RV.getScalarVal();
752  unsigned AS = cast<llvm::PointerType>(NewPtr->getType())->getAddressSpace();
753
754  if (NullCheckResult) {
755    NullCheckSource = Builder.GetInsertBlock();
756    NewNotNull = createBasicBlock("new.notnull");
757    NewEnd = createBasicBlock("new.end");
758
759    llvm::Value *IsNull = Builder.CreateIsNull(NewPtr, "new.isnull");
760    Builder.CreateCondBr(IsNull, NewEnd, NewNotNull);
761    EmitBlock(NewNotNull);
762  }
763
764  assert((AllocSize == AllocSizeWithoutCookie) ==
765         CalculateCookiePadding(*this, E).isZero());
766  if (AllocSize != AllocSizeWithoutCookie) {
767    assert(E->isArray());
768    NewPtr = CGM.getCXXABI().InitializeArrayCookie(CGF, NewPtr, NumElements,
769                                                   AllocType);
770  }
771
772  const llvm::Type *ElementPtrTy
773    = ConvertTypeForMem(AllocType)->getPointerTo(AS);
774  NewPtr = Builder.CreateBitCast(NewPtr, ElementPtrTy);
775  if (E->isArray()) {
776    EmitNewInitializer(*this, E, NewPtr, NumElements, AllocSizeWithoutCookie);
777
778    // NewPtr is a pointer to the base element type.  If we're
779    // allocating an array of arrays, we'll need to cast back to the
780    // array pointer type.
781    const llvm::Type *ResultTy = ConvertTypeForMem(E->getType());
782    if (NewPtr->getType() != ResultTy)
783      NewPtr = Builder.CreateBitCast(NewPtr, ResultTy);
784  } else {
785    EmitNewInitializer(*this, E, NewPtr, NumElements, AllocSizeWithoutCookie);
786  }
787
788  if (NullCheckResult) {
789    Builder.CreateBr(NewEnd);
790    llvm::BasicBlock *NotNullSource = Builder.GetInsertBlock();
791    EmitBlock(NewEnd);
792
793    llvm::PHINode *PHI = Builder.CreatePHI(NewPtr->getType());
794    PHI->reserveOperandSpace(2);
795    PHI->addIncoming(NewPtr, NotNullSource);
796    PHI->addIncoming(llvm::Constant::getNullValue(NewPtr->getType()),
797                     NullCheckSource);
798
799    NewPtr = PHI;
800  }
801
802  return NewPtr;
803}
804
805void CodeGenFunction::EmitDeleteCall(const FunctionDecl *DeleteFD,
806                                     llvm::Value *Ptr,
807                                     QualType DeleteTy) {
808  assert(DeleteFD->getOverloadedOperator() == OO_Delete);
809
810  const FunctionProtoType *DeleteFTy =
811    DeleteFD->getType()->getAs<FunctionProtoType>();
812
813  CallArgList DeleteArgs;
814
815  // Check if we need to pass the size to the delete operator.
816  llvm::Value *Size = 0;
817  QualType SizeTy;
818  if (DeleteFTy->getNumArgs() == 2) {
819    SizeTy = DeleteFTy->getArgType(1);
820    CharUnits DeleteTypeSize = getContext().getTypeSizeInChars(DeleteTy);
821    Size = llvm::ConstantInt::get(ConvertType(SizeTy),
822                                  DeleteTypeSize.getQuantity());
823  }
824
825  QualType ArgTy = DeleteFTy->getArgType(0);
826  llvm::Value *DeletePtr = Builder.CreateBitCast(Ptr, ConvertType(ArgTy));
827  DeleteArgs.push_back(std::make_pair(RValue::get(DeletePtr), ArgTy));
828
829  if (Size)
830    DeleteArgs.push_back(std::make_pair(RValue::get(Size), SizeTy));
831
832  // Emit the call to delete.
833  EmitCall(CGM.getTypes().getFunctionInfo(DeleteArgs, DeleteFTy),
834           CGM.GetAddrOfFunction(DeleteFD), ReturnValueSlot(),
835           DeleteArgs, DeleteFD);
836}
837
838namespace {
839  /// Calls the given 'operator delete' on a single object.
840  struct CallObjectDelete : EHScopeStack::Cleanup {
841    llvm::Value *Ptr;
842    const FunctionDecl *OperatorDelete;
843    QualType ElementType;
844
845    CallObjectDelete(llvm::Value *Ptr,
846                     const FunctionDecl *OperatorDelete,
847                     QualType ElementType)
848      : Ptr(Ptr), OperatorDelete(OperatorDelete), ElementType(ElementType) {}
849
850    void Emit(CodeGenFunction &CGF, bool IsForEH) {
851      CGF.EmitDeleteCall(OperatorDelete, Ptr, ElementType);
852    }
853  };
854}
855
856/// Emit the code for deleting a single object.
857static void EmitObjectDelete(CodeGenFunction &CGF,
858                             const FunctionDecl *OperatorDelete,
859                             llvm::Value *Ptr,
860                             QualType ElementType) {
861  // Find the destructor for the type, if applicable.  If the
862  // destructor is virtual, we'll just emit the vcall and return.
863  const CXXDestructorDecl *Dtor = 0;
864  if (const RecordType *RT = ElementType->getAs<RecordType>()) {
865    CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
866    if (!RD->hasTrivialDestructor()) {
867      Dtor = RD->getDestructor();
868
869      if (Dtor->isVirtual()) {
870        const llvm::Type *Ty =
871          CGF.getTypes().GetFunctionType(CGF.getTypes().getFunctionInfo(Dtor,
872                                                               Dtor_Complete),
873                                         /*isVariadic=*/false);
874
875        llvm::Value *Callee
876          = CGF.BuildVirtualCall(Dtor, Dtor_Deleting, Ptr, Ty);
877        CGF.EmitCXXMemberCall(Dtor, Callee, ReturnValueSlot(), Ptr, /*VTT=*/0,
878                              0, 0);
879
880        // The dtor took care of deleting the object.
881        return;
882      }
883    }
884  }
885
886  // Make sure that we call delete even if the dtor throws.
887  CGF.EHStack.pushCleanup<CallObjectDelete>(NormalAndEHCleanup,
888                                            Ptr, OperatorDelete, ElementType);
889
890  if (Dtor)
891    CGF.EmitCXXDestructorCall(Dtor, Dtor_Complete,
892                              /*ForVirtualBase=*/false, Ptr);
893
894  CGF.PopCleanupBlock();
895}
896
897namespace {
898  /// Calls the given 'operator delete' on an array of objects.
899  struct CallArrayDelete : EHScopeStack::Cleanup {
900    llvm::Value *Ptr;
901    const FunctionDecl *OperatorDelete;
902    llvm::Value *NumElements;
903    QualType ElementType;
904    CharUnits CookieSize;
905
906    CallArrayDelete(llvm::Value *Ptr,
907                    const FunctionDecl *OperatorDelete,
908                    llvm::Value *NumElements,
909                    QualType ElementType,
910                    CharUnits CookieSize)
911      : Ptr(Ptr), OperatorDelete(OperatorDelete), NumElements(NumElements),
912        ElementType(ElementType), CookieSize(CookieSize) {}
913
914    void Emit(CodeGenFunction &CGF, bool IsForEH) {
915      const FunctionProtoType *DeleteFTy =
916        OperatorDelete->getType()->getAs<FunctionProtoType>();
917      assert(DeleteFTy->getNumArgs() == 1 || DeleteFTy->getNumArgs() == 2);
918
919      CallArgList Args;
920
921      // Pass the pointer as the first argument.
922      QualType VoidPtrTy = DeleteFTy->getArgType(0);
923      llvm::Value *DeletePtr
924        = CGF.Builder.CreateBitCast(Ptr, CGF.ConvertType(VoidPtrTy));
925      Args.push_back(std::make_pair(RValue::get(DeletePtr), VoidPtrTy));
926
927      // Pass the original requested size as the second argument.
928      if (DeleteFTy->getNumArgs() == 2) {
929        QualType size_t = DeleteFTy->getArgType(1);
930        const llvm::IntegerType *SizeTy
931          = cast<llvm::IntegerType>(CGF.ConvertType(size_t));
932
933        CharUnits ElementTypeSize =
934          CGF.CGM.getContext().getTypeSizeInChars(ElementType);
935
936        // The size of an element, multiplied by the number of elements.
937        llvm::Value *Size
938          = llvm::ConstantInt::get(SizeTy, ElementTypeSize.getQuantity());
939        Size = CGF.Builder.CreateMul(Size, NumElements);
940
941        // Plus the size of the cookie if applicable.
942        if (!CookieSize.isZero()) {
943          llvm::Value *CookieSizeV
944            = llvm::ConstantInt::get(SizeTy, CookieSize.getQuantity());
945          Size = CGF.Builder.CreateAdd(Size, CookieSizeV);
946        }
947
948        Args.push_back(std::make_pair(RValue::get(Size), size_t));
949      }
950
951      // Emit the call to delete.
952      CGF.EmitCall(CGF.getTypes().getFunctionInfo(Args, DeleteFTy),
953                   CGF.CGM.GetAddrOfFunction(OperatorDelete),
954                   ReturnValueSlot(), Args, OperatorDelete);
955    }
956  };
957}
958
959/// Emit the code for deleting an array of objects.
960static void EmitArrayDelete(CodeGenFunction &CGF,
961                            const FunctionDecl *OperatorDelete,
962                            llvm::Value *Ptr,
963                            QualType ElementType) {
964  llvm::Value *NumElements = 0;
965  llvm::Value *AllocatedPtr = 0;
966  CharUnits CookieSize;
967  CGF.CGM.getCXXABI().ReadArrayCookie(CGF, Ptr, ElementType,
968                                      NumElements, AllocatedPtr, CookieSize);
969
970  assert(AllocatedPtr && "ReadArrayCookie didn't set AllocatedPtr");
971
972  // Make sure that we call delete even if one of the dtors throws.
973  CGF.EHStack.pushCleanup<CallArrayDelete>(NormalAndEHCleanup,
974                                           AllocatedPtr, OperatorDelete,
975                                           NumElements, ElementType,
976                                           CookieSize);
977
978  if (const CXXRecordDecl *RD = ElementType->getAsCXXRecordDecl()) {
979    if (!RD->hasTrivialDestructor()) {
980      assert(NumElements && "ReadArrayCookie didn't find element count"
981                            " for a class with destructor");
982      CGF.EmitCXXAggrDestructorCall(RD->getDestructor(), NumElements, Ptr);
983    }
984  }
985
986  CGF.PopCleanupBlock();
987}
988
989void CodeGenFunction::EmitCXXDeleteExpr(const CXXDeleteExpr *E) {
990
991  // Get at the argument before we performed the implicit conversion
992  // to void*.
993  const Expr *Arg = E->getArgument();
994  while (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Arg)) {
995    if (ICE->getCastKind() != CK_UserDefinedConversion &&
996        ICE->getType()->isVoidPointerType())
997      Arg = ICE->getSubExpr();
998    else
999      break;
1000  }
1001
1002  llvm::Value *Ptr = EmitScalarExpr(Arg);
1003
1004  // Null check the pointer.
1005  llvm::BasicBlock *DeleteNotNull = createBasicBlock("delete.notnull");
1006  llvm::BasicBlock *DeleteEnd = createBasicBlock("delete.end");
1007
1008  llvm::Value *IsNull =
1009    Builder.CreateICmpEQ(Ptr, llvm::Constant::getNullValue(Ptr->getType()),
1010                         "isnull");
1011
1012  Builder.CreateCondBr(IsNull, DeleteEnd, DeleteNotNull);
1013  EmitBlock(DeleteNotNull);
1014
1015  // We might be deleting a pointer to array.  If so, GEP down to the
1016  // first non-array element.
1017  // (this assumes that A(*)[3][7] is converted to [3 x [7 x %A]]*)
1018  QualType DeleteTy = Arg->getType()->getAs<PointerType>()->getPointeeType();
1019  if (DeleteTy->isConstantArrayType()) {
1020    llvm::Value *Zero = Builder.getInt32(0);
1021    llvm::SmallVector<llvm::Value*,8> GEP;
1022
1023    GEP.push_back(Zero); // point at the outermost array
1024
1025    // For each layer of array type we're pointing at:
1026    while (const ConstantArrayType *Arr
1027             = getContext().getAsConstantArrayType(DeleteTy)) {
1028      // 1. Unpeel the array type.
1029      DeleteTy = Arr->getElementType();
1030
1031      // 2. GEP to the first element of the array.
1032      GEP.push_back(Zero);
1033    }
1034
1035    Ptr = Builder.CreateInBoundsGEP(Ptr, GEP.begin(), GEP.end(), "del.first");
1036  }
1037
1038  assert(ConvertTypeForMem(DeleteTy) ==
1039         cast<llvm::PointerType>(Ptr->getType())->getElementType());
1040
1041  if (E->isArrayForm()) {
1042    EmitArrayDelete(*this, E->getOperatorDelete(), Ptr, DeleteTy);
1043  } else {
1044    EmitObjectDelete(*this, E->getOperatorDelete(), Ptr, DeleteTy);
1045  }
1046
1047  EmitBlock(DeleteEnd);
1048}
1049
1050llvm::Value * CodeGenFunction::EmitCXXTypeidExpr(const CXXTypeidExpr *E) {
1051  QualType Ty = E->getType();
1052  const llvm::Type *LTy = ConvertType(Ty)->getPointerTo();
1053
1054  if (E->isTypeOperand()) {
1055    llvm::Constant *TypeInfo =
1056      CGM.GetAddrOfRTTIDescriptor(E->getTypeOperand());
1057    return Builder.CreateBitCast(TypeInfo, LTy);
1058  }
1059
1060  Expr *subE = E->getExprOperand();
1061  Ty = subE->getType();
1062  CanQualType CanTy = CGM.getContext().getCanonicalType(Ty);
1063  Ty = CanTy.getUnqualifiedType().getNonReferenceType();
1064  if (const RecordType *RT = Ty->getAs<RecordType>()) {
1065    const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
1066    if (RD->isPolymorphic()) {
1067      // FIXME: if subE is an lvalue do
1068      LValue Obj = EmitLValue(subE);
1069      llvm::Value *This = Obj.getAddress();
1070      LTy = LTy->getPointerTo()->getPointerTo();
1071      llvm::Value *V = Builder.CreateBitCast(This, LTy);
1072      // We need to do a zero check for *p, unless it has NonNullAttr.
1073      // FIXME: PointerType->hasAttr<NonNullAttr>()
1074      bool CanBeZero = false;
1075      if (UnaryOperator *UO = dyn_cast<UnaryOperator>(subE->IgnoreParens()))
1076        if (UO->getOpcode() == UO_Deref)
1077          CanBeZero = true;
1078      if (CanBeZero) {
1079        llvm::BasicBlock *NonZeroBlock = createBasicBlock();
1080        llvm::BasicBlock *ZeroBlock = createBasicBlock();
1081
1082        llvm::Value *Zero = llvm::Constant::getNullValue(LTy);
1083        Builder.CreateCondBr(Builder.CreateICmpNE(V, Zero),
1084                             NonZeroBlock, ZeroBlock);
1085        EmitBlock(ZeroBlock);
1086        /// Call __cxa_bad_typeid
1087        const llvm::Type *ResultType = llvm::Type::getVoidTy(VMContext);
1088        const llvm::FunctionType *FTy;
1089        FTy = llvm::FunctionType::get(ResultType, false);
1090        llvm::Value *F = CGM.CreateRuntimeFunction(FTy, "__cxa_bad_typeid");
1091        Builder.CreateCall(F)->setDoesNotReturn();
1092        Builder.CreateUnreachable();
1093        EmitBlock(NonZeroBlock);
1094      }
1095      V = Builder.CreateLoad(V, "vtable");
1096      V = Builder.CreateConstInBoundsGEP1_64(V, -1ULL);
1097      V = Builder.CreateLoad(V);
1098      return V;
1099    }
1100  }
1101  return Builder.CreateBitCast(CGM.GetAddrOfRTTIDescriptor(Ty), LTy);
1102}
1103
1104llvm::Value *CodeGenFunction::EmitDynamicCast(llvm::Value *V,
1105                                              const CXXDynamicCastExpr *DCE) {
1106  QualType SrcTy = DCE->getSubExpr()->getType();
1107  QualType DestTy = DCE->getTypeAsWritten();
1108  QualType InnerType = DestTy->getPointeeType();
1109
1110  const llvm::Type *LTy = ConvertType(DCE->getType());
1111
1112  bool CanBeZero = false;
1113  bool ToVoid = false;
1114  bool ThrowOnBad = false;
1115  if (DestTy->isPointerType()) {
1116    // FIXME: if PointerType->hasAttr<NonNullAttr>(), we don't set this
1117    CanBeZero = true;
1118    if (InnerType->isVoidType())
1119      ToVoid = true;
1120  } else {
1121    LTy = LTy->getPointerTo();
1122
1123    // FIXME: What if exceptions are disabled?
1124    ThrowOnBad = true;
1125  }
1126
1127  if (SrcTy->isPointerType() || SrcTy->isReferenceType())
1128    SrcTy = SrcTy->getPointeeType();
1129  SrcTy = SrcTy.getUnqualifiedType();
1130
1131  if (DestTy->isPointerType() || DestTy->isReferenceType())
1132    DestTy = DestTy->getPointeeType();
1133  DestTy = DestTy.getUnqualifiedType();
1134
1135  llvm::BasicBlock *ContBlock = createBasicBlock();
1136  llvm::BasicBlock *NullBlock = 0;
1137  llvm::BasicBlock *NonZeroBlock = 0;
1138  if (CanBeZero) {
1139    NonZeroBlock = createBasicBlock();
1140    NullBlock = createBasicBlock();
1141    Builder.CreateCondBr(Builder.CreateIsNotNull(V), NonZeroBlock, NullBlock);
1142    EmitBlock(NonZeroBlock);
1143  }
1144
1145  llvm::BasicBlock *BadCastBlock = 0;
1146
1147  const llvm::Type *PtrDiffTy = ConvertType(getContext().getPointerDiffType());
1148
1149  // See if this is a dynamic_cast(void*)
1150  if (ToVoid) {
1151    llvm::Value *This = V;
1152    V = Builder.CreateBitCast(This, PtrDiffTy->getPointerTo()->getPointerTo());
1153    V = Builder.CreateLoad(V, "vtable");
1154    V = Builder.CreateConstInBoundsGEP1_64(V, -2ULL);
1155    V = Builder.CreateLoad(V, "offset to top");
1156    This = Builder.CreateBitCast(This, llvm::Type::getInt8PtrTy(VMContext));
1157    V = Builder.CreateInBoundsGEP(This, V);
1158    V = Builder.CreateBitCast(V, LTy);
1159  } else {
1160    /// Call __dynamic_cast
1161    const llvm::Type *ResultType = llvm::Type::getInt8PtrTy(VMContext);
1162    const llvm::FunctionType *FTy;
1163    std::vector<const llvm::Type*> ArgTys;
1164    const llvm::Type *PtrToInt8Ty
1165      = llvm::Type::getInt8Ty(VMContext)->getPointerTo();
1166    ArgTys.push_back(PtrToInt8Ty);
1167    ArgTys.push_back(PtrToInt8Ty);
1168    ArgTys.push_back(PtrToInt8Ty);
1169    ArgTys.push_back(PtrDiffTy);
1170    FTy = llvm::FunctionType::get(ResultType, ArgTys, false);
1171
1172    // FIXME: Calculate better hint.
1173    llvm::Value *hint = llvm::ConstantInt::get(PtrDiffTy, -1ULL);
1174
1175    assert(SrcTy->isRecordType() && "Src type must be record type!");
1176    assert(DestTy->isRecordType() && "Dest type must be record type!");
1177
1178    llvm::Value *SrcArg
1179      = CGM.GetAddrOfRTTIDescriptor(SrcTy.getUnqualifiedType());
1180    llvm::Value *DestArg
1181      = CGM.GetAddrOfRTTIDescriptor(DestTy.getUnqualifiedType());
1182
1183    V = Builder.CreateBitCast(V, PtrToInt8Ty);
1184    V = Builder.CreateCall4(CGM.CreateRuntimeFunction(FTy, "__dynamic_cast"),
1185                            V, SrcArg, DestArg, hint);
1186    V = Builder.CreateBitCast(V, LTy);
1187
1188    if (ThrowOnBad) {
1189      BadCastBlock = createBasicBlock();
1190      Builder.CreateCondBr(Builder.CreateIsNotNull(V), ContBlock, BadCastBlock);
1191      EmitBlock(BadCastBlock);
1192      /// Invoke __cxa_bad_cast
1193      ResultType = llvm::Type::getVoidTy(VMContext);
1194      const llvm::FunctionType *FBadTy;
1195      FBadTy = llvm::FunctionType::get(ResultType, false);
1196      llvm::Value *F = CGM.CreateRuntimeFunction(FBadTy, "__cxa_bad_cast");
1197      if (llvm::BasicBlock *InvokeDest = getInvokeDest()) {
1198        llvm::BasicBlock *Cont = createBasicBlock("invoke.cont");
1199        Builder.CreateInvoke(F, Cont, InvokeDest)->setDoesNotReturn();
1200        EmitBlock(Cont);
1201      } else {
1202        // FIXME: Does this ever make sense?
1203        Builder.CreateCall(F)->setDoesNotReturn();
1204      }
1205      Builder.CreateUnreachable();
1206    }
1207  }
1208
1209  if (CanBeZero) {
1210    Builder.CreateBr(ContBlock);
1211    EmitBlock(NullBlock);
1212    Builder.CreateBr(ContBlock);
1213  }
1214  EmitBlock(ContBlock);
1215  if (CanBeZero) {
1216    llvm::PHINode *PHI = Builder.CreatePHI(LTy);
1217    PHI->reserveOperandSpace(2);
1218    PHI->addIncoming(V, NonZeroBlock);
1219    PHI->addIncoming(llvm::Constant::getNullValue(LTy), NullBlock);
1220    V = PHI;
1221  }
1222
1223  return V;
1224}
1225