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

1560

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

204

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/include/clang/Basic/CodeGenOptions.def

 ENUM_CODEGENOPT(CompressDebugSections, llvm::DebugCompressionType, 2,
                 llvm::DebugCompressionType::None)
 CODEGENOPT(RelaxELFRelocations, 1, 1) ///< -Wa,-mrelax-relocations={yes,no}
 CODEGENOPT(AsmVerbose        , 1, 0) ///< -dA, -fverbose-asm.
 CODEGENOPT(Dwarf64           , 1, 0) ///< -gdwarf64.
 CODEGENOPT(Dwarf32           , 1, 1) ///< -gdwarf32.
 CODEGENOPT(PreserveAsmComments, 1, 1) ///< -dA, -fno-preserve-as-comments.
 CODEGENOPT(AssumeSaneOperatorNew , 1, 1) ///< implicit __attribute__((malloc)) operator new
+CODEGENOPT(AssumeUniqueVTables , 1, 1) ///< Assume a class has only one vtable.
 CODEGENOPT(Autolink          , 1, 1) ///< -fno-autolink
 CODEGENOPT(ObjCAutoRefCountExceptions , 1, 0) ///< Whether ARC should be EH-safe.
 CODEGENOPT(Backchain         , 1, 0) ///< -mbackchain
 CODEGENOPT(ControlFlowGuardNoChecks  , 1, 0) ///< -cfguard-no-checks
 CODEGENOPT(ControlFlowGuard  , 1, 0) ///< -cfguard
 CODEGENOPT(EHContGuard       , 1, 0) ///< -ehcontguard
 CODEGENOPT(CXAAtExit         , 1, 1) ///< Use __cxa_atexit for calling destructors.
 CODEGENOPT(RegisterGlobalDtorsWithAtExit, 1, 1) ///< Use atexit or __cxa_atexit to register global destructors.

clang/include/clang/Driver/Options.td

defm xl_pragma_pack : BoolFOption<"xl-pragma-pack",
   NegFlag<SetFalse>>;
 def shared_libsan : Flag<["-"], "shared-libsan">,
   HelpText<"Dynamically link the sanitizer runtime">;
 def static_libsan : Flag<["-"], "static-libsan">,
   HelpText<"Statically link the sanitizer runtime (Not supported for ASan, TSan or UBSan on darwin)">;
 def : Flag<["-"], "shared-libasan">, Alias<shared_libsan>;
 def fasm : Flag<["-"], "fasm">, Group<f_Group>;
 
+defm assume_unique_vtables : BoolFOption<"assume-unique-vtables",
+  CodeGenOpts<"AssumeUniqueVTables">, DefaultTrue,
+  PosFlag<SetTrue>,
+  NegFlag<SetFalse, [CC1Option],
+          "Disable optimizations based on vtable pointer identity">,
+  BothFlags<[CoreOption]>>;
+
 def fassume_sane_operator_new : Flag<["-"], "fassume-sane-operator-new">, Group<f_Group>;
 def fastcp : Flag<["-"], "fastcp">, Group<f_Group>;
 def fastf : Flag<["-"], "fastf">, Group<f_Group>;
 def fast : Flag<["-"], "fast">, Group<f_Group>;
 def fasynchronous_unwind_tables : Flag<["-"], "fasynchronous-unwind-tables">, Group<f_Group>;
 
 defm double_square_bracket_attributes : BoolFOption<"double-square-bracket-attributes",
   LangOpts<"DoubleSquareBracketAttributes">, Default<!strconcat(cpp11.KeyPath, "||", c2x.KeyPath)>,

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(QualType DestRecordTy) = 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) = 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 *CastSuccess,
+                                            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);
+  CGF.Builder.ClearInsertionPoint();
+  return llvm::PoisonValue::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(DestRecordTy);
+
   // 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);
+  } 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, CastEnd, 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);
+    CastNull = Builder.GetInsertBlock();
+
     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/CodeGenModule.h

llvm::Constant *GetAddrOfFunction(GlobalDecl GD, llvm::Type *Ty = nullptr,
                                     bool ForVTable = false,
                                     bool DontDefer = false,
                                     ForDefinition_t IsForDefinition
                                       = NotForDefinition);
 
   // Return the function body address of the given function.
   llvm::Constant *GetFunctionStart(const ValueDecl *Decl);
 
+  // Return whether RTTI information should be emitted for this target.
+  bool shouldEmitRTTI(bool ForEH = false) {
+    return (ForEH || getLangOpts().RTTI) && !getLangOpts().CUDAIsDevice &&
+           !(getLangOpts().OpenMP && getLangOpts().OpenMPIsTargetDevice &&
+             getTriple().isNVPTX());
+  }
+
   /// Get the address of the RTTI descriptor for the given type.
   llvm::Constant *GetAddrOfRTTIDescriptor(QualType Ty, bool ForEH = false);
 
   /// Get the address of a GUID.
   ConstantAddress GetAddrOfMSGuidDecl(const MSGuidDecl *GD);
 
   /// Get the address of a UnnamedGlobalConstant
   ConstantAddress

clang/lib/CodeGen/CodeGenModule.cpp

void CodeGenModule::EmitCoverageFile() {
   }
 }
 
 llvm::Constant *CodeGenModule::GetAddrOfRTTIDescriptor(QualType Ty,
                                                        bool ForEH) {
   // Return a bogus pointer if RTTI is disabled, unless it's for EH.
   // FIXME: should we even be calling this method if RTTI is disabled
   // and it's not for EH?
-  if ((!ForEH && !getLangOpts().RTTI) || getLangOpts().CUDAIsDevice ||
-      (getLangOpts().OpenMP && getLangOpts().OpenMPIsTargetDevice &&
-       getTriple().isNVPTX()))
+  if (!shouldEmitRTTI(ForEH))
     return llvm::Constant::getNullValue(GlobalsInt8PtrTy);
 
   if (ForEH && Ty->isObjCObjectPointerType() &&
       LangOpts.ObjCRuntime.isGNUFamily())
     return ObjCRuntime->GetEHType(Ty);
 
   return getCXXABI().getAddrOfRTTIDescriptor(Ty);
 }

clang/lib/CodeGen/ItaniumCXXABI.cpp

 #include "clang/CodeGen/ConstantInitBuilder.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/ScopedPrinter.h"
 
+#include <optional>
+
 using namespace clang;
 using namespace CodeGen;
 
 namespace {
 class ItaniumCXXABI : public CodeGen::CGCXXABI {
   /// VTables - All the vtables which have been defined.
   llvm::DenseMap<const CXXRecordDecl *, llvm::GlobalVariable *> VTables;
 
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;
 
+  /// Determine whether we know that all instances of type RecordTy will have
+  /// the same vtable pointer values, that is distinct from all other vtable
+  /// pointers. While this is required by the Itanium ABI, it doesn't happen in
+  /// practice in some cases due to language extensions.
+  bool hasUniqueVTablePointer(QualType RecordTy) {
+    const CXXRecordDecl *RD = RecordTy->getAsCXXRecordDecl();
+
+    // Under -fapple-kext, multiple definitions of the same vtable may be
+    // emitted.
+    if (!CGM.getCodeGenOpts().AssumeUniqueVTables ||
+        getContext().getLangOpts().AppleKext)
+      return false;
+
+    // If the type_info* would be null, the vtable might be merged with that of
+    // another type.
+    if (!CGM.shouldEmitRTTI())
+      return false;
+
+    // If there's only one definition of the vtable in the program, it has a
+    // unique address.
+    if (!llvm::GlobalValue::isWeakForLinker(CGM.getVTableLinkage(RD)))
+      return true;
+
+    // Even if there are multiple definitions of the vtable, they are required
+    // by the ABI to use the same symbol name, so should be merged at load
+    // time. However, if the class has hidden visibility, there can be
+    // different versions of the class in different modules, and the ABI
+    // library might treat them as being the same.
+    if (CGM.GetLLVMVisibility(RD->getVisibility()) !=
+        llvm::GlobalValue::DefaultVisibility)
+      return false;
+
+    return true;
+  }
+
+  bool shouldEmitExactDynamicCast(QualType DestRecordTy) override {
+    return hasUniqueVTablePointer(DestRecordTy);
+  }
+
   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 *CastSuccess,
+                                    llvm::BasicBlock *CastFail) override;
+
   llvm::Value *emitDynamicCastToVoid(CodeGenFunction &CGF, Address Value,
                                      QualType SrcRecordTy) override;
 
   bool EmitBadCastCall(CodeGenFunction &CGF) override;
 
   llvm::Value *
     GetVirtualBaseClassOffset(CodeGenFunction &CGF, Address This,
                               const CXXRecordDecl *ClassDecl,
if (UseGlobalDelete) {
     auto *ClassDecl =
         cast<CXXRecordDecl>(ElementType->castAs<RecordType>()->getDecl());
     llvm::Value *VTable = CGF.GetVTablePtr(
         Ptr, llvm::PointerType::getUnqual(CGF.getLLVMContext()), ClassDecl);
 
     // Track back to entry -2 and pull out the offset there.
     llvm::Value *OffsetPtr = CGF.Builder.CreateConstInBoundsGEP1_64(
         CGF.IntPtrTy, VTable, -2, "complete-offset.ptr");
-    llvm::Value *Offset = CGF.Builder.CreateAlignedLoad(CGF.IntPtrTy, OffsetPtr,                                                        CGF.getPointerAlign());
+    llvm::Value *Offset = CGF.Builder.CreateAlignedLoad(CGF.IntPtrTy, OffsetPtr,
+                                                        CGF.getPointerAlign());
 
     // Apply the offset.
     llvm::Value *CompletePtr =
       CGF.Builder.CreateBitCast(Ptr.getPointer(), CGF.Int8PtrTy);
     CompletePtr =
         CGF.Builder.CreateInBoundsGEP(CGF.Int8Ty, CompletePtr, Offset);
 
     // If we're supposed to call the global delete, make sure we do so
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 *CastSuccess,
+    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 an offset within `DestDecl` where a `SrcDecl` instance and its vptr
+  // might appear.
+  std::optional<CharUnits> Offset;
+  for (const CXXBasePath &Path : Paths) {
+    // dynamic_cast only finds public inheritance paths.
+    if (Path.Access != AS_public)
+      continue;
+
+    CharUnits PathOffset;
+    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);
+        PathOffset = L.getVBaseClassOffset(Base);
+      } else {
+        const ASTRecordLayout &L =
+            Context.getASTRecordLayout(PathElement.Class);
+        PathOffset += L.getBaseClassOffset(Base);
+      }
+    }
+
+    if (!Offset)
+      Offset = PathOffset;
+    else if (Offset != PathOffset) {
+      // Base appears in at least two different places. Find the most-derived
+      // object and see if it's a DestDecl. Note that the most-derived object
+      // must be at least as aligned as this base class subobject, and must
+      // have a vptr at offset 0.
+      ThisAddr = Address(emitDynamicCastToVoid(CGF, ThisAddr, SrcRecordTy),
+                         CGF.VoidPtrTy, ThisAddr.getAlignment());
+      SrcDecl = DestDecl;
+      Offset = CharUnits::Zero();
+      break;
+    }
+  }
+
+  if (!Offset) {
+    // If there are no public inheritance paths, the cast always fails.
+    CGF.EmitBranch(CastFail);
+    return llvm::PoisonValue::get(CGF.VoidPtrTy);
+  }
+
+  // Compare the vptr against the expected vptr for the destination type at
+  // this offset. Note that we do not know what type ThisAddr points to in
+  // the case where the derived class multiply inherits from the base class
+  // so we can't use GetVTablePtr, so we load the vptr directly instead.
+  llvm::Instruction *VPtr = CGF.Builder.CreateLoad(
+      ThisAddr.withElementType(CGF.VoidPtrPtrTy), "vtable");
+  CGM.DecorateInstructionWithTBAA(
+      VPtr, CGM.getTBAAVTablePtrAccessInfo(CGF.VoidPtrPtrTy));
+  llvm::Value *Success = CGF.Builder.CreateICmpEQ(
+      VPtr, getVTableAddressPoint(BaseSubobject(SrcDecl, *Offset), DestDecl));
+  llvm::Value *Result = ThisAddr.getPointer();
+  if (!Offset->isZero())
+    Result = CGF.Builder.CreateInBoundsGEP(
+        CGF.CharTy, Result,
+        {llvm::ConstantInt::get(CGF.PtrDiffTy, -Offset->getQuantity())});
+  CGF.Builder.CreateCondBr(Success, CastSuccess, CastFail);
+  return Result;
+}
+
 llvm::Value *ItaniumCXXABI::emitDynamicCastToVoid(CodeGenFunction &CGF,
                                                   Address ThisAddr,
                                                   QualType SrcRecordTy) {
   auto *ClassDecl =
       cast<CXXRecordDecl>(SrcRecordTy->castAs<RecordType>()->getDecl());
   llvm::Value *OffsetToTop;
   if (CGM.getItaniumVTableContext().isRelativeLayout()) {
     // Get the vtable pointer.

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(QualType DestRecordTy) 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 *CastSuccess,
+                                    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) override;
 

clang/lib/Driver/ToolChains/Clang.cpp

case llvm::ExceptionHandling::WinEH:
       break;
     }
   }
 
   // C++ "sane" operator new.
   Args.addOptOutFlag(CmdArgs, options::OPT_fassume_sane_operator_new,
                      options::OPT_fno_assume_sane_operator_new);
 
+  // -fassume-unique-vtables is on by default.
+  Args.addOptOutFlag(CmdArgs, options::OPT_fassume_unique_vtables,
+                     options::OPT_fno_assume_unique_vtables);
+
   // -frelaxed-template-template-args is off by default, as it is a severe
   // breaking change until a corresponding change to template partial ordering
   // is provided.
   Args.addOptInFlag(CmdArgs, options::OPT_frelaxed_template_template_args,
                     options::OPT_fno_relaxed_template_template_args);
 
   // -fsized-deallocation is off by default, as it is an ABI-breaking change for
   // most platforms.

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
+  // CHECK: unreachable
+  //
+  // CHECK: ret ptr poison
   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: unreachable
+  //
+  // CHECK: ret ptr poison
+  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-disabled.cpp

+// RUN: %clang_cc1 -I%S %s -triple x86_64-apple-darwin10 -emit-llvm -std=c++11 -o - | FileCheck %s --check-prefixes=CHECK,EXACT
+// RUN: %clang_cc1 -I%S %s -triple x86_64-apple-darwin10 -fvisibility=hidden -emit-llvm -std=c++11 -o - | FileCheck %s --check-prefixes=CHECK,INEXACT
+// RUN: %clang_cc1 -I%S %s -triple x86_64-apple-darwin10 -fapple-kext -emit-llvm -std=c++11 -o - | FileCheck %s --check-prefixes=CHECK,INEXACT
+// RUN: %clang_cc1 -I%S %s -triple x86_64-apple-darwin10 -fno-assume-unique-vtables -emit-llvm -std=c++11 -o - | FileCheck %s --check-prefixes=CHECK,INEXACT
+
+struct A { virtual ~A(); };
+struct B final : A { };
+
+// CHECK-LABEL: @_Z5exactP1A
+B *exact(A *a) {
+  // INEXACT: call {{.*}} @__dynamic_cast
+  // EXACT-NOT: call {{.*}} @__dynamic_cast
+  return dynamic_cast<B*>(a);
+}

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 Offset { virtual ~Offset(); };
+struct A { virtual ~A(); };
+struct B final : Offset, 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_FAILED:.*]], label %[[LABEL_NOTNULL:.*]]
+
+  // CHECK: [[LABEL_NOTNULL]]:
+  // CHECK: %[[VPTR:.*]] = load ptr, ptr %[[PTR]]
+  // CHECK: %[[MATCH:.*]] = icmp eq ptr %[[VPTR]], getelementptr inbounds ({ [4 x ptr], [4 x ptr] }, ptr @_ZTV1B, i32 0, inrange i32 1, i32 2)
+  // CHECK: %[[RESULT:.*]] = getelementptr inbounds i8, ptr %[[PTR]], i64 -8
+  // CHECK: br i1 %[[MATCH]], label %[[LABEL_END:.*]], label %[[LABEL_FAILED]]
+
+  // CHECK: [[LABEL_FAILED]]:
+  // CHECK: br label %[[LABEL_END]]
+
+  // CHECK: [[LABEL_END]]:
+  // CHECK: phi ptr [ %[[RESULT]], %[[LABEL_NOTNULL]] ], [ null, %[[LABEL_FAILED]] ]
+  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_FAILED:.*]], label %[[LABEL_NOTNULL:.*]]
+
+  // CHECK: [[LABEL_NOTNULL]]:
+  // CHECK: %[[VPTR:.*]] = load ptr, ptr %[[PTR]]
+  // CHECK: %[[MATCH:.*]] = icmp eq ptr %[[VPTR]], getelementptr inbounds ({ [4 x ptr], [4 x ptr] }, ptr @_ZTV1B, i32 0, inrange i32 1, i32 2)
+  // CHECK: %[[RESULT:.*]] = getelementptr inbounds i8, ptr %[[PTR]], i64 -8
+  // CHECK: br i1 %[[MATCH]], label %[[LABEL_END:.*]], label %[[LABEL_FAILED]]
+
+  // CHECK: [[LABEL_FAILED]]:
+  // CHECK: call {{.*}} @__cxa_bad_cast
+  // CHECK: unreachable
+
+  // CHECK: [[LABEL_END]]:
+  // CHECK: ret ptr %[[RESULT]]
+  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_FAILED:.*]], label %[[LABEL_NOTNULL:.*]]
+
+  // CHECK: [[LABEL_NOTNULL]]:
+  // CHECK: %[[VPTR:.*]] = load ptr, ptr %[[PTR]]
+  // CHECK: %[[OFFSET_TO_TOP_SLOT:.*]] = getelementptr inbounds i64, ptr %[[VPTR]], i64 -2
+  // CHECK: %[[OFFSET_TO_TOP:.*]] = load i64, ptr %[[OFFSET_TO_TOP_SLOT]]
+  // CHECK: %[[RESULT:.*]] = getelementptr inbounds i8, ptr %[[PTR]], i64 %[[OFFSET_TO_TOP]]
+  // CHECK: %[[DERIVED_VPTR:.*]] = load ptr, ptr %[[RESULT]]
+  // CHECK: %[[MATCH:.*]] = icmp eq ptr %[[DERIVED_VPTR]], getelementptr inbounds ({ [5 x ptr], [4 x ptr], [4 x ptr], [6 x ptr], [6 x ptr] }, ptr @_ZTV1H, i32 0, inrange i32 0, i32 3)
+  // CHECK: br i1 %[[MATCH]], label %[[LABEL_END:.*]], label %[[LABEL_FAILED]]
+
+  // CHECK: [[LABEL_FAILED]]:
+  // CHECK: br label %[[LABEL_END]]
+
+  // CHECK: [[LABEL_END]]:
+  // CHECK: phi ptr [ %[[RESULT]], %[[LABEL_NOTNULL]] ], [ null, %[[LABEL_FAILED]] ]
+  return dynamic_cast<H*>(a);
+}

clang/test/Driver/fassume-unique-vtables.cpp

+// RUN: %clang -### -fno-assume-unique-vtables %s -S 2>&1 | FileCheck -check-prefix=CHECK-OPT %s
+// RUN: %clang -### -fno-assume-unique-vtables -fassume-unique-vtables %s -S 2>&1 | FileCheck -check-prefix=CHECK-NOOPT %s
+// CHECK-OPT: "-fno-assume-unique-vtables"
+// CHECK-NOOPT-NOT: "-fno-assume-unique-vtables"