Optimize emission of `dynamic_cast` to final classes.

[rsmith]

Summary

• When the destination is a final class type that does not derive from the source type, the cast always fails and is now emitted as a null pointer or call to __cxa_bad_cast.

• When the destination is a final class type that does derive from the source type, emit a direct comparison against the corresponding base class vptr value(s). There may be more than one such value in the case of multiple inheritance; check them all.

For now, this is supported only for the Itanium ABI. I expect the same thing is
possible for the MS ABI too, but I don't know what guarantees are made about
vfptr uniqueness.

[nlopes]

clang/lib/CodeGen/ItaniumCXXABI.cpp

1541

Please use PoisonValue as a placeholder whenever possible. We are trying to get rid of undef.
Thank you!

[rjmccall]

I don't think it's an intended guarantee of the Itanium ABI that the v-table will be unique, and v-tables are frequently not unique in the presence of shared libraries. They should be unique for classes with internal linkage, but of course that's a vastly reduced domain for the optimization. We could do an RTTI comparison in the general case, either by hardcoding the algorithm inline or by synthesizing a helper expression in Sema to compare two std::type_infos with ==. Or you could have a flag to tell you to make stronger uniqueness assumptions.

If there are multiple subobjects of the source type in the destination type, consider just casting to void* first instead of doing multiple comparisons.

[rsmith]

In D154658#4479170, @rjmccall wrote:

I don't think it's an intended guarantee of the Itanium ABI that the v-table will be unique, and v-tables are frequently not unique in the presence of shared libraries.

https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general explicitly guarantees this: "[...] However, the virtual table pointers within all the objects (instances) of a particular most-derived class point to the same set of virtual tables."

They should be unique for classes with internal linkage, but of course that's a vastly reduced domain for the optimization.

I think (hope?) we should be able to apply this to a much larger set of cases. Would it be correct to do this optimization unless the vtable might be emitted with vague linkage and non-default visibility (that is, unless we're in the odd case where people expect non-default visibility classes to be the same type across DSOs)? Or are there cases where we might be using a vtable that (eg) doesn't even have the right symbol?

If there are multiple subobjects of the source type in the destination type, consider just casting to void* first instead of doing multiple comparisons.

Ha, that seems obvious in retrospect :) Will do.

[rjmccall]

In D154658#4479213, @rsmith wrote:

In D154658#4479170, @rjmccall wrote:

I don't think it's an intended guarantee of the Itanium ABI that the v-table will be unique, and v-tables are frequently not unique in the presence of shared libraries.

https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general explicitly guarantees this: "[...] However, the virtual table pointers within all the objects (instances) of a particular most-derived class point to the same set of virtual tables."

Huh, I've never noticed that before. I still don't think it's satisfied in practice, at least in the presence of shared libraries. This is notably the exact same setup that eventually forced (or "forced") GCC to start using string comparison for RTTI instead of the ABI-prescribed algorithm that relies on _ZTS pointer equality.

They should be unique for classes with internal linkage, but of course that's a vastly reduced domain for the optimization.

I think (hope?) we should be able to apply this to a much larger set of cases. Would it be correct to do this optimization unless the vtable might be emitted with vague linkage and non-default visibility (that is, unless we're in the odd case where people expect non-default visibility classes to be the same type across DSOs)? Or are there cases where we might be using a vtable that (eg) doesn't even have the right symbol?

I don't know of any problems other than the total failure of vague linkage across DSO boundaries, so if we just treat that as an implicit exception to the vtable uniqueness guarantee in the ABI, I think you've got the condition exactly right: we could do this for any class where either the v-table doesn't have vague linkage or the class's formal visibility is not default. Our experience at Apple with enforcing type visibility is that it's usually good for one or two bug reports a year, but it's pretty easy to explain to users what they did wrong, and Clang's visibility attributes are pretty simple to use. (type_visibility helps a lot with managing tradeoffs.)

[rsmith]

• Address review comments.

[rsmith]

In D154658#4481225, @rjmccall wrote:

In D154658#4479213, @rsmith wrote:

I think (hope?) we should be able to apply this to a much larger set of cases. Would it be correct to do this optimization unless the vtable might be emitted with vague linkage and non-default visibility (that is, unless we're in the odd case where people expect non-default visibility classes to be the same type across DSOs)? Or are there cases where we might be using a vtable that (eg) doesn't even have the right symbol?

I don't know of any problems other than the total failure of vague linkage across DSO boundaries, so if we just treat that as an implicit exception to the vtable uniqueness guarantee in the ABI, I think you've got the condition exactly right: we could do this for any class where either the v-table doesn't have vague linkage or the class's formal visibility is not default. Our experience at Apple with enforcing type visibility is that it's usually good for one or two bug reports a year, but it's pretty easy to explain to users what they did wrong, and Clang's visibility attributes are pretty simple to use. (type_visibility helps a lot with managing tradeoffs.)

I did some checking through the Clang implementation and found another two cases:

• under -fapple-kext, vague-linkage vtables get emitted in each translation unit that references them
• under -fno-rtti, identical vtables for distinct types could get merged because we emit vtables as unnamed_addr (this doesn't affect dynamic_cast, because -fno-rtti also disables dynamic_cast entirely)

The good news seems to be that if you don't use any language extensions (type visibility, -fno-rtti, -fapple-kext), then we do actually provide the guarantee that the ABI describes. :)

In D154658#4479170, @rjmccall wrote:

If there are multiple subobjects of the source type in the destination type, consider just casting to void* first instead of doing multiple comparisons.

This turned out to be a little subtle: the vptr comparison we do after the cast requires loading a vptr of an object of entirely-unknown type. This is the first time we're doing that in IR generation, and GetVTablePtr expected to be told which class it's loading the vtable for (presumably, so that it can load from the right offset within the class). However, the implementation of GetVTablePtr didn't use the class for anything; it's always at the start for all of our supported ABIs. But this patch would make it harder to support an ABI that didn't put the vptr at the start of the most-derived object.

[rsmith]

• Mark gep as inbounds.

[rjmccall]

In D154658#4482202, @rsmith wrote:

In D154658#4481225, @rjmccall wrote:

In D154658#4479213, @rsmith wrote:

I think (hope?) we should be able to apply this to a much larger set of cases. Would it be correct to do this optimization unless the vtable might be emitted with vague linkage and non-default visibility (that is, unless we're in the odd case where people expect non-default visibility classes to be the same type across DSOs)? Or are there cases where we might be using a vtable that (eg) doesn't even have the right symbol?

I don't know of any problems other than the total failure of vague linkage across DSO boundaries, so if we just treat that as an implicit exception to the vtable uniqueness guarantee in the ABI, I think you've got the condition exactly right: we could do this for any class where either the v-table doesn't have vague linkage or the class's formal visibility is not default. Our experience at Apple with enforcing type visibility is that it's usually good for one or two bug reports a year, but it's pretty easy to explain to users what they did wrong, and Clang's visibility attributes are pretty simple to use. (type_visibility helps a lot with managing tradeoffs.)

I did some checking through the Clang implementation and found another two cases:

• under -fapple-kext, vague-linkage vtables get emitted in each translation unit that references them
• under -fno-rtti, identical vtables for distinct types could get merged because we emit vtables as unnamed_addr (this doesn't affect dynamic_cast, because -fno-rtti also disables dynamic_cast entirely)

The good news seems to be that if you don't use any language extensions (type visibility, -fno-rtti, -fapple-kext), then we do actually provide the guarantee that the ABI describes. :)

In D154658#4479170, @rjmccall wrote:

If there are multiple subobjects of the source type in the destination type, consider just casting to void* first instead of doing multiple comparisons.

This turned out to be a little subtle: the vptr comparison we do after the cast requires loading a vptr of an object of entirely-unknown type. This is the first time we're doing that in IR generation, and GetVTablePtr expected to be told which class it's loading the vtable for (presumably, so that it can load from the right offset within the class). However, the implementation of GetVTablePtr didn't use the class for anything; it's always at the start for all of our supported ABIs. But this patch would make it harder to support an ABI that didn't put the vptr at the start of the most-derived object.

Oh, this does matter on platforms using pointer authentication, because each vptr field is signed with a constant discriminator derived from the name of the class that introduced it.

clang/lib/CodeGen/ItaniumCXXABI.cpp

203

Is there no reasonable way of checking this without actually triggering the emission of RTTI?

[rsmith]

• Avoid emitting the type_info when detecting whether it would be null.
• Bring back class type in GetVTablePtr and instead don't use it here.

[rsmith]

In D154658#4490468, @rjmccall wrote:

Oh, this does matter on platforms using pointer authentication, because each vptr field is signed with a constant discriminator derived from the name of the class that introduced it.

Oh, hm. I guess you have an out-of-tree patch for that? I've switched back to passing types into GetVTablePtr, and stopped using that from emitExactDynamicCast in favor of directly loading the vtpr after the dynamic_cast<void*>. You would need to disable the exact dynamic_cast optimization when pointer authentication is enabled for vptrs, but that should be a small patch.

[rsmith]

Ping.

[rjmccall]

LGTM, except, should we have a way to turn this optimization off specifically?

[rsmith]

• Add option to disable vptr-based dynamic_cast optimization.

[rsmith]

In D154658#4516554, @rjmccall wrote:

LGTM, except, should we have a way to turn this optimization off specifically?

Sure. I suppose even for an internal linkage vtable there could be a reason to want to turn this off (eg, if someone constructs a custom vtable at runtime). I've added -fno-assume-unique-vtables to disable the optimization.

[rjmccall]

Thanks, LGTM

[thakis]

This caused https://github.com/llvm/llvm-project/issues/64088

[MatzeB]

This change results in some of our builds (distributed Thin-LTO in case that matters) to fail with missing symbols. At a first glance this seems to emit VTables in some files where it didn't do this before and then fails to resolve some members of that vtable. I'm in the process of analyzing this further and making a small reproducer.

[rsmith]

In D154658#4533476, @MatzeB wrote:

This change results in some of our builds (distributed Thin-LTO in case that matters) to fail with missing symbols. At a first glance this seems to emit VTables in some files where it didn't do this before and then fails to resolve some members of that vtable. I'm in the process of analyzing this further and making a small reproducer.

Please try again after rGb6847edfc235829b37dd6d734ef5bbfa0a58b6fc and see if you're still having issues.

[MatzeB]

In D154658#4533476, @MatzeB wrote:

This change results in some of our builds (distributed Thin-LTO in case that matters) to fail with missing symbols. At a first glance this seems to emit VTables in some files where it didn't do this before and then fails to resolve some members of that vtable. I'm in the process of analyzing this further and making a small reproducer.

I just noticed b6847edfc235829b37dd6d734ef5bbfa0a58b6fc mentioned in the task above which isn't part of our builds yet. I see even more symbols emitted with that change and suspect it may resolves the undefined symbols problems then. Will know for sure in a day or two (and if you hear nothing all is working well).

clang/lib/AST/ExprCXX.cpp

 /// isAlwaysNull - Return whether the result of the dynamic_cast is proven
 /// to always be null. For example:
 ///
 /// struct A { };
 /// struct B final : A { };
 /// struct C { };
 ///
 /// C *f(B* b) { return dynamic_cast<C*>(b); }
-bool CXXDynamicCastExpr::isAlwaysNull() const
-{
+bool CXXDynamicCastExpr::isAlwaysNull() const {
+  if (isValueDependent() || getCastKind() != CK_Dynamic)
+    return false;
+
   QualType SrcType = getSubExpr()->getType();
   QualType DestType = getType();
 
-  if (const auto *SrcPTy = SrcType->getAs<PointerType>()) {
-    SrcType = SrcPTy->getPointeeType();
-    DestType = DestType->castAs<PointerType>()->getPointeeType();
-  }
-
-  if (DestType->isVoidType())
+  if (DestType->isVoidPointerType())
     return false;
 
-  const auto *SrcRD =
-      cast<CXXRecordDecl>(SrcType->castAs<RecordType>()->getDecl());
+  if (DestType->isPointerType()) {
+    SrcType = SrcType->getPointeeType();
+    DestType = DestType->getPointeeType();
+  }
 
-  if (!SrcRD->hasAttr<FinalAttr>())
-    return false;
+  const auto *SrcRD = SrcType->getAsCXXRecordDecl();
+  const auto *DestRD = DestType->getAsCXXRecordDecl();
+  assert(SrcRD && DestRD);
+
+  if (SrcRD->isEffectivelyFinal()) {
+    assert(!SrcRD->isDerivedFrom(DestRD) &&
+           "upcasts should not use CK_Dynamic");
+    return true;
+  }
 
-  const auto *DestRD =
-      cast<CXXRecordDecl>(DestType->castAs<RecordType>()->getDecl());
+  if (DestRD->isEffectivelyFinal() && !DestRD->isDerivedFrom(SrcRD))
+    return true;
 
-  return !DestRD->isDerivedFrom(SrcRD);
+  return false;
 }
 
 CXXReinterpretCastExpr *
 CXXReinterpretCastExpr::Create(const ASTContext &C, QualType T,
                                ExprValueKind VK, CastKind K, Expr *Op,
                                const CXXCastPath *BasePath,
                                TypeSourceInfo *WrittenTy, SourceLocation L,
                                SourceLocation RParenLoc,

clang/lib/CodeGen/CGCXXABI.h

virtual bool shouldTypeidBeNullChecked(bool IsDeref,
                                          QualType SrcRecordTy) = 0;
   virtual void EmitBadTypeidCall(CodeGenFunction &CGF) = 0;
   virtual llvm::Value *EmitTypeid(CodeGenFunction &CGF, QualType SrcRecordTy,
                                   Address ThisPtr,
                                   llvm::Type *StdTypeInfoPtrTy) = 0;
 
   virtual bool shouldDynamicCastCallBeNullChecked(bool SrcIsPtr,
                                                   QualType SrcRecordTy) = 0;
+  virtual bool shouldEmitExactDynamicCast() = 0;
 
   virtual llvm::Value *
   EmitDynamicCastCall(CodeGenFunction &CGF, Address Value,
                       QualType SrcRecordTy, QualType DestTy,
                       QualType DestRecordTy, llvm::BasicBlock *CastEnd) = 0;
 
   virtual llvm::Value *EmitDynamicCastToVoid(CodeGenFunction &CGF,
                                              Address Value,
                                              QualType SrcRecordTy,
                                              QualType DestTy) = 0;
 
+  /// Emit a dynamic_cast from SrcRecordTy to DestRecordTy. The cast fails if
+  /// the dynamic type of Value is not exactly DestRecordTy.
+  virtual llvm::Value *EmitExactDynamicCast(CodeGenFunction &CGF, Address Value,
+                                            QualType SrcRecordTy,
+                                            QualType DestTy,
+                                            QualType DestRecordTy,
+                                            llvm::BasicBlock *CastFail) = 0;
+
   virtual bool EmitBadCastCall(CodeGenFunction &CGF) = 0;
 
   virtual llvm::Value *GetVirtualBaseClassOffset(CodeGenFunction &CGF,
                                                  Address This,
                                                  const CXXRecordDecl *ClassDecl,
                                         const CXXRecordDecl *BaseClassDecl) = 0;
 
   virtual llvm::BasicBlock *EmitCtorCompleteObjectHandler(CodeGenFunction &CGF,

clang/lib/CodeGen/CGExprCXX.cpp

static llvm::Value *EmitDynamicCastToNull(CodeGenFunction &CGF,
   if (DestTy->isPointerType())
     return llvm::Constant::getNullValue(DestLTy);
 
   /// C++ [expr.dynamic.cast]p9:
   ///   A failed cast to reference type throws std::bad_cast
   if (!CGF.CGM.getCXXABI().EmitBadCastCall(CGF))
     return nullptr;
 
-  CGF.EmitBlock(CGF.createBasicBlock("dynamic_cast.end"));
   return llvm::UndefValue::get(DestLTy);
 }
 
 llvm::Value *CodeGenFunction::EmitDynamicCast(Address ThisAddr,
                                               const CXXDynamicCastExpr *DCE) {
   CGM.EmitExplicitCastExprType(DCE, this);
   QualType DestTy = DCE->getTypeAsWritten();
 
   QualType SrcTy = DCE->getSubExpr()->getType();
 
   // C++ [expr.dynamic.cast]p7:
   //   If T is "pointer to cv void," then the result is a pointer to the most
   //   derived object pointed to by v.
-  const PointerType *DestPTy = DestTy->getAs<PointerType>();
-
-  bool isDynamicCastToVoid;
+  bool IsDynamicCastToVoid = DestTy->isVoidPointerType();
   QualType SrcRecordTy;
   QualType DestRecordTy;
-  if (DestPTy) {
-    isDynamicCastToVoid = DestPTy->getPointeeType()->isVoidType();
+  if (IsDynamicCastToVoid) {
+    SrcRecordTy = SrcTy->getPointeeType();
+    // No DestRecordTy.
+  } else if (const PointerType *DestPTy = DestTy->getAs<PointerType>()) {
     SrcRecordTy = SrcTy->castAs<PointerType>()->getPointeeType();
     DestRecordTy = DestPTy->getPointeeType();
   } else {
-    isDynamicCastToVoid = false;
     SrcRecordTy = SrcTy;
     DestRecordTy = DestTy->castAs<ReferenceType>()->getPointeeType();
   }
 
   // C++ [class.cdtor]p5:
   //   If the operand of the dynamic_cast refers to the object under
   //   construction or destruction and the static type of the operand is not a
   //   pointer to or object of the constructor or destructor’s own class or one
   //   of its bases, the dynamic_cast results in undefined behavior.
   EmitTypeCheck(TCK_DynamicOperation, DCE->getExprLoc(), ThisAddr.getPointer(),
                 SrcRecordTy);
 
-  if (DCE->isAlwaysNull())
-    if (llvm::Value *T = EmitDynamicCastToNull(*this, DestTy))
+  if (DCE->isAlwaysNull()) {
+    if (llvm::Value *T = EmitDynamicCastToNull(*this, DestTy)) {
+      // Expression emission is expected to retain a valid insertion point.
+      if (!Builder.GetInsertBlock())
+        EmitBlock(createBasicBlock("dynamic_cast.unreachable"));
       return T;
+    }
+  }
 
   assert(SrcRecordTy->isRecordType() && "source type must be a record type!");
 
+  // If the destination is effectively final, the cast succeeds if and only
+  // if the dynamic type of the pointer is exactly the destination type.
+  bool IsExact = !IsDynamicCastToVoid &&
+                 DestRecordTy->getAsCXXRecordDecl()->isEffectivelyFinal() &&
+                 CGM.getCXXABI().shouldEmitExactDynamicCast();
+
   // C++ [expr.dynamic.cast]p4:
   //   If the value of v is a null pointer value in the pointer case, the result
   //   is the null pointer value of type T.
   bool ShouldNullCheckSrcValue =
-      CGM.getCXXABI().shouldDynamicCastCallBeNullChecked(SrcTy->isPointerType(),
-                                                         SrcRecordTy);
+      IsExact || CGM.getCXXABI().shouldDynamicCastCallBeNullChecked(
+                     SrcTy->isPointerType(), SrcRecordTy);
 
   llvm::BasicBlock *CastNull = nullptr;
   llvm::BasicBlock *CastNotNull = nullptr;
   llvm::BasicBlock *CastEnd = createBasicBlock("dynamic_cast.end");
 
   if (ShouldNullCheckSrcValue) {
     CastNull = createBasicBlock("dynamic_cast.null");
     CastNotNull = createBasicBlock("dynamic_cast.notnull");
 
     llvm::Value *IsNull = Builder.CreateIsNull(ThisAddr.getPointer());
     Builder.CreateCondBr(IsNull, CastNull, CastNotNull);
     EmitBlock(CastNotNull);
   }
 
   llvm::Value *Value;
-  if (isDynamicCastToVoid) {
+  if (IsDynamicCastToVoid) {
     Value = CGM.getCXXABI().EmitDynamicCastToVoid(*this, ThisAddr, SrcRecordTy,
                                                   DestTy);
+  } else if (IsExact) {
+    // If the destination type is effectively final, this pointer points to the
+    // right type if and only if its vptr has the right value.
+    Value = CGM.getCXXABI().EmitExactDynamicCast(
+        *this, ThisAddr, SrcRecordTy, DestTy, DestRecordTy, CastNull);
   } else {
     assert(DestRecordTy->isRecordType() &&
            "destination type must be a record type!");
     Value = CGM.getCXXABI().EmitDynamicCastCall(*this, ThisAddr, SrcRecordTy,
                                                 DestTy, DestRecordTy, CastEnd);
-    CastNotNull = Builder.GetInsertBlock();
   }
+  CastNotNull = Builder.GetInsertBlock();
 
+  llvm::Value *NullValue = nullptr;
   if (ShouldNullCheckSrcValue) {
     EmitBranch(CastEnd);
 
     EmitBlock(CastNull);
+    NullValue = EmitDynamicCastToNull(*this, DestTy);
+
+    auto *Block = Builder.GetInsertBlock();
+    if (Block && !Block->getTerminator())
+      CastNull = Block;
+    else
+      CastNull = nullptr;
+
     EmitBranch(CastEnd);
   }
 
   EmitBlock(CastEnd);
 
-  if (ShouldNullCheckSrcValue) {
+  if (CastNull) {
     llvm::PHINode *PHI = Builder.CreatePHI(Value->getType(), 2);
     PHI->addIncoming(Value, CastNotNull);
-    PHI->addIncoming(llvm::Constant::getNullValue(Value->getType()), CastNull);
+    PHI->addIncoming(NullValue, CastNull);
 
     Value = PHI;
   }
 
   return Value;
 }

clang/lib/CodeGen/ItaniumCXXABI.cpp

public:
   bool shouldTypeidBeNullChecked(bool IsDeref, QualType SrcRecordTy) override;
   void EmitBadTypeidCall(CodeGenFunction &CGF) override;
   llvm::Value *EmitTypeid(CodeGenFunction &CGF, QualType SrcRecordTy,
                           Address ThisPtr,
                           llvm::Type *StdTypeInfoPtrTy) override;
 
   bool shouldDynamicCastCallBeNullChecked(bool SrcIsPtr,
                                           QualType SrcRecordTy) override;
+  bool shouldEmitExactDynamicCast() override { return true; }
 
   llvm::Value *EmitDynamicCastCall(CodeGenFunction &CGF, Address Value,
                                    QualType SrcRecordTy, QualType DestTy,
                                    QualType DestRecordTy,
                                    llvm::BasicBlock *CastEnd) override;
 
+  llvm::Value *EmitExactDynamicCast(CodeGenFunction &CGF, Address ThisAddr,
+                                    QualType SrcRecordTy, QualType DestTy,
+                                    QualType DestRecordTy,
+                                    llvm::BasicBlock *CastFail) override;
+
   llvm::Value *EmitDynamicCastToVoid(CodeGenFunction &CGF, Address Value,
                                      QualType SrcRecordTy,
                                      QualType DestTy) override;
 
   bool EmitBadCastCall(CodeGenFunction &CGF) override;
 
   llvm::Value *
     GetVirtualBaseClassOffset(CodeGenFunction &CGF, Address This,
                               const CXXRecordDecl *ClassDecl,
                               const CXXRecordDecl *BaseClassDecl) override;
 
   void EmitCXXConstructors(const CXXConstructorDecl *D) override;
 
if (DestTy->isReferenceType()) {
 
     CGF.EmitBlock(BadCastBlock);
     EmitBadCastCall(CGF);
   }
 
   return Value;
 }
 
+llvm::Value *ItaniumCXXABI::EmitExactDynamicCast(
+    CodeGenFunction &CGF, Address ThisAddr, QualType SrcRecordTy,
+    QualType DestTy, QualType DestRecordTy, llvm::BasicBlock *CastFail) {
+  ASTContext &Context = getContext();
+
+  // Find all the inheritance paths.
+  const CXXRecordDecl *SrcDecl = SrcRecordTy->getAsCXXRecordDecl();
+  const CXXRecordDecl *DestDecl = DestRecordTy->getAsCXXRecordDecl();
+  CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
+                     /*DetectVirtual=*/false);
+  (void)DestDecl->isDerivedFrom(SrcDecl, Paths);
+
+  // Find all offsets within `DestDecl` where a `SrcDecl` instance and its vptr
+  // might appear.
+  llvm::SmallVector<CharUnits> Offsets;
+  for (const CXXBasePath &Path : Paths) {
+    // dynamic_cast only finds public inheritance paths.
+    if (Path.Access != AS_public)
+      continue;
+
+    CharUnits Offset;
+    for (const CXXBasePathElement &PathElement : Path) {
+      // Find the offset along this inheritance step.
+      const CXXRecordDecl *Base =
+          PathElement.Base->getType()->getAsCXXRecordDecl();
+      if (PathElement.Base->isVirtual()) {
+        // For a virtual base class, we know that the derived class is exactly
+        // DestDecl, so we can use the vbase offset from its layout.
+        const ASTRecordLayout &L = Context.getASTRecordLayout(DestDecl);
+        Offset = L.getVBaseClassOffset(Base);
+      } else {
+        const ASTRecordLayout &L =
+            Context.getASTRecordLayout(PathElement.Class);
+        Offset += L.getBaseClassOffset(Base);
+      }
+    }
+    Offsets.push_back(Offset);
+  }
+
+  // We might have found multiple paths to a virtual base. Deduplicate them.
+  llvm::sort(Offsets);
+  Offsets.erase(std::unique(Offsets.begin(), Offsets.end()), Offsets.end());
+
+  if (Offsets.empty()) {
+    // If there are no inheritance paths, the cast always fails.
+    CGF.Builder.CreateBr(CastFail);
+    return llvm::UndefValue::get(CGF.VoidPtrTy);
+  }
+
+  llvm::BasicBlock *SuccessBlock = CGF.createBasicBlock("dynamic_cast.success");
+  llvm::PHINode *OffsetPhi = nullptr;
+  if (Offsets.size() > 1)
+    OffsetPhi = llvm::PHINode::Create(CGF.PtrDiffTy, Offsets.size(),
+                                      "dynamic_cast.offset", SuccessBlock);
+  llvm::Value *OffsetValue = OffsetPhi;
+
+  // Compare the vptr against each vptr for DestDecl.
+  llvm::Value *VPtr = CGF.GetVTablePtr(ThisAddr, CGF.VoidPtrPtrTy, SrcDecl);
+  for (auto [I, Offset] : llvm::enumerate(Offsets)) {
+    llvm::BasicBlock *NextBlock;
+    if (I == Offsets.size() - 1)
+      NextBlock = CastFail;
+    else
+      NextBlock = CGF.createBasicBlock("dynamic_cast.cont");
+
+    llvm::Value *Success = CGF.Builder.CreateICmpEQ(
+        VPtr, getVTableAddressPoint(BaseSubobject(SrcDecl, Offset), DestDecl));
+    CGF.Builder.CreateCondBr(Success, SuccessBlock, NextBlock);
+
+    llvm::Value *SrcToDestAdjustment =
+        llvm::ConstantInt::get(CGF.PtrDiffTy, -Offset.getQuantity());
+    if (OffsetPhi)
+      OffsetPhi->addIncoming(SrcToDestAdjustment, CGF.Builder.GetInsertBlock());
+    else
+      OffsetValue = SrcToDestAdjustment;
+
+    if (I != Offsets.size() - 1)
+      CGF.EmitBlock(NextBlock);
+  }
+
+  CGF.EmitBlock(SuccessBlock);
+
+  // FIXME: Should IRBuilder fold this for us?
+  if (Offsets.size() == 1 && Offsets[0].isZero())
+    return ThisAddr.getPointer();
+
+  return CGF.Builder.CreateInBoundsGEP(CGF.CharTy, ThisAddr.getPointer(),
+                                       {OffsetValue});
+}
+
 llvm::Value *ItaniumCXXABI::EmitDynamicCastToVoid(CodeGenFunction &CGF,
                                                   Address ThisAddr,
                                                   QualType SrcRecordTy,
                                                   QualType DestTy) {
   llvm::Type *DestLTy = CGF.ConvertType(DestTy);
   auto *ClassDecl =
       cast<CXXRecordDecl>(SrcRecordTy->castAs<RecordType>()->getDecl());
   llvm::Value *OffsetToTop;

clang/lib/CodeGen/MicrosoftCXXABI.cpp

public:
   void EmitBadTypeidCall(CodeGenFunction &CGF) override;
   llvm::Value *EmitTypeid(CodeGenFunction &CGF, QualType SrcRecordTy,
                           Address ThisPtr,
                           llvm::Type *StdTypeInfoPtrTy) override;
 
   bool shouldDynamicCastCallBeNullChecked(bool SrcIsPtr,
                                           QualType SrcRecordTy) override;
 
+  bool shouldEmitExactDynamicCast() override {
+    // TODO: Add support for exact dynamic_casts.
+    return false;
+  }
+  llvm::Value *EmitExactDynamicCast(CodeGenFunction &CGF, Address Value,
+                                    QualType SrcRecordTy, QualType DestTy,
+                                    QualType DestRecordTy,
+                                    llvm::BasicBlock *CastFail) override {
+    llvm_unreachable("unsupported");
+  }
+
   llvm::Value *EmitDynamicCastCall(CodeGenFunction &CGF, Address Value,
                                    QualType SrcRecordTy, QualType DestTy,
                                    QualType DestRecordTy,
                                    llvm::BasicBlock *CastEnd) override;
 
   llvm::Value *EmitDynamicCastToVoid(CodeGenFunction &CGF, Address Value,
                                      QualType SrcRecordTy,
                                      QualType DestTy) override;

clang/test/CodeGenCXX/dynamic-cast-always-null.cpp

 // RUN: %clang_cc1 -I%S %s -triple x86_64-apple-darwin10 -emit-llvm -fcxx-exceptions -fexceptions -std=c++11 -o - | FileCheck %s
 struct A { virtual ~A(); };
 struct B final : A { };
 struct C { virtual ~C(); int c; };
 
+// CHECK: @_Z8nonnull1P1C
+A *nonnull1(C* c) {
+  // CHECK: call {{.*}} @__dynamic_cast
+  return dynamic_cast<A*>(c);
+}
+
+// CHECK: @_Z8nonnull2P1A
+C *nonnull2(A* a) {
+  // CHECK: call {{.*}} @__dynamic_cast
+  return dynamic_cast<C*>(a);
+}
+
 // CHECK: @_Z1fP1B
 C *f(B* b) {
-  // CHECK-NOT: call ptr @__dynamic_cast
+  // CHECK-NOT: call {{.*}} @__dynamic_cast
   // CHECK: ret ptr null
   return dynamic_cast<C*>(b);
 }
 
 // CHECK: @_Z1fR1B
 C &f(B& b) {
-  // CHECK-NOT: call ptr @__dynamic_cast
+  // CHECK-NOT: call {{.*}} @__dynamic_cast
   // CHECK: call void @__cxa_bad_cast() [[NR:#[0-9]+]]
   // CHECK: ret ptr undef
   return dynamic_cast<C&>(b);
 }
 
+// CHECK: @_Z1gP1C
+B *g(C* c) {
+  // CHECK-NOT: call {{.*}} @__dynamic_cast
+  // CHECK: ret ptr null
+  return dynamic_cast<B*>(c);
+}
+
+// CHECK: @_Z1gR1C
+B &g(C& c) {
+  // CHECK-NOT: call {{.*}} @__dynamic_cast
+  // CHECK: call void @__cxa_bad_cast() [[NR:#[0-9]+]]
+  // CHECK: ret ptr undef
+  return dynamic_cast<B&>(c);
+}
+
 void dont_crash() {
   (void) dynamic_cast<void*>((A*)0);
   (void) dynamic_cast<void*>((B*)0);
 }
 
 // CHECK: attributes [[NR]] = { noreturn }

clang/test/CodeGenCXX/dynamic-cast-exact.cpp

+// RUN: %clang_cc1 -I%S %s -triple x86_64-apple-darwin10 -emit-llvm -fcxx-exceptions -fexceptions -std=c++11 -o - | FileCheck %s --implicit-check-not='call {{.*}} @__dynamic_cast'
+struct A { virtual ~A(); };
+struct B final : A { };
+
+struct C { virtual ~C(); int c; };
+struct D : A { int d; };
+struct E : A { int e; };
+struct F : virtual A { int f; };
+struct G : virtual A { int g; };
+struct H final : C, D, E, F, G { int h; };
+
+// CHECK-LABEL: @_Z7inexactP1A
+C *inexact(A *a) {
+  // CHECK: call {{.*}} @__dynamic_cast
+  return dynamic_cast<C*>(a);
+}
+
+// CHECK-LABEL: @_Z12exact_singleP1A
+B *exact_single(A *a) {
+  // CHECK: %[[PTR_NULL:.*]] = icmp eq ptr %[[PTR:.*]], null
+  // CHECK: br i1 %[[PTR_NULL]], label %[[LABEL_NULL:.*]], label %[[LABEL_NOTNULL:.*]]
+
+  // CHECK: [[LABEL_NOTNULL]]:
+  // CHECK: %[[VPTR:.*]] = load ptr, ptr %[[PTR]]
+  // CHECK: %[[MATCH:.*]] = icmp eq ptr %[[VPTR]], getelementptr inbounds ({ [4 x ptr] }, ptr @_ZTV1B, i32 0, inrange i32 0, i32 2)
+  // CHECK: br i1 %[[MATCH]], label %[[LABEL_SUCCESS:.*]], label %[[LABEL_NULL]]
+
+  // CHECK: [[LABEL_SUCCESS]]:
+  // CHECK: br label %[[LABEL_END:.*]]
+
+  // CHECK: [[LABEL_NULL]]:
+  // CHECK: br label %[[LABEL_END]]
+
+  // CHECK: [[LABEL_END]]:
+  // CHECK: phi ptr [ %[[PTR]], %[[LABEL_SUCCESS]] ], [ null, %[[LABEL_NULL]] ]
+  return dynamic_cast<B*>(a);
+}
+
+// CHECK-LABEL: @_Z9exact_refR1A
+B &exact_ref(A &a) {
+  // CHECK: %[[PTR_NULL:.*]] = icmp eq ptr %[[PTR:.*]], null
+  // CHECK: br i1 %[[PTR_NULL]], label %[[LABEL_NULL:.*]], label %[[LABEL_NOTNULL:.*]]
+
+  // CHECK: [[LABEL_NOTNULL]]:
+  // CHECK: %[[VPTR:.*]] = load ptr, ptr %[[PTR]]
+  // CHECK: %[[MATCH:.*]] = icmp eq ptr %[[VPTR]], getelementptr inbounds ({ [4 x ptr] }, ptr @_ZTV1B, i32 0, inrange i32 0, i32 2)
+  // CHECK: br i1 %[[MATCH]], label %[[LABEL_SUCCESS:.*]], label %[[LABEL_NULL]]
+
+  // CHECK: [[LABEL_SUCCESS]]:
+  // CHECK: br label %[[LABEL_END:.*]]
+
+  // CHECK: [[LABEL_NULL]]:
+  // CHECK: call {{.*}} @__cxa_bad_cast
+  // CHECK: unreachable
+
+  // CHECK: [[LABEL_END]]:
+  // CHECK: ret ptr %[[PTR]]
+  return dynamic_cast<B&>(a);
+}
+
+// CHECK-LABEL: @_Z11exact_multiP1A
+H *exact_multi(A *a) {
+  // CHECK: %[[PTR_NULL:.*]] = icmp eq ptr %[[PTR:.*]], null
+  // CHECK: br i1 %[[PTR_NULL]], label %[[LABEL_NULL:.*]], label %[[LABEL_NOTNULL:.*]]
+
+  // CHECK: [[LABEL_NOTNULL]]:
+  // CHECK: %[[VPTR:.*]] = load ptr, ptr %[[PTR]]
+  // CHECK: %[[MATCH_1:.*]] = icmp eq ptr %[[VPTR]], getelementptr inbounds ({ [5 x ptr], [4 x ptr], [4 x ptr], [6 x ptr], [6 x ptr] }, ptr @_ZTV1H, i32 0, inrange i32 1, i32 2)
+  // CHECK: br i1 %[[MATCH_1]], label %[[LABEL_SUCCESS:.*]], label %[[LABEL_CONT_1:.*]]
+
+  // CHECK: [[LABEL_CONT_1]]:
+  // CHECK: %[[MATCH_2:.*]] = icmp eq ptr %[[VPTR]], getelementptr inbounds ({ [5 x ptr], [4 x ptr], [4 x ptr], [6 x ptr], [6 x ptr] }, ptr @_ZTV1H, i32 0, inrange i32 2, i32 2)
+  // CHECK: br i1 %[[MATCH_2]], label %[[LABEL_SUCCESS:.*]], label %[[LABEL_CONT_2:.*]]
+
+  // CHECK: [[LABEL_CONT_2]]:
+  // CHECK: %[[MATCH_3:.*]] = icmp eq ptr %[[VPTR]], getelementptr inbounds ({ [5 x ptr], [4 x ptr], [4 x ptr], [6 x ptr], [6 x ptr] }, ptr @_ZTV1H, i32 0, inrange i32 3, i32 4)
+  // CHECK: br i1 %[[MATCH_3]], label %[[LABEL_SUCCESS:.*]], label %[[LABEL_NULL]]
+
+  // CHECK: [[LABEL_SUCCESS]]:
+  // CHECK: %[[SUCCESS_OFFSET:.*]] = phi i64 [ -16, %[[LABEL_NOTNULL]] ], [ -32, %[[LABEL_CONT_1]] ], [ -48, %[[LABEL_CONT_2]] ]
+  // CHECK: %[[SUCCESS_VALUE:.*]] = getelementptr inbounds i8, ptr %[[PTR]], i64 %[[SUCCESS_OFFSET]]
+  // CHECK: br label %[[LABEL_END:.*]]
+
+  // CHECK: [[LABEL_NULL]]:
+  // CHECK: br label %[[LABEL_END]]
+
+  // CHECK: [[LABEL_END]]:
+  // CHECK: phi ptr [ %[[SUCCESS_VALUE]], %[[LABEL_SUCCESS]] ], [ null, %[[LABEL_NULL]] ]
+  return dynamic_cast<H*>(a);
+}