[WPD] Avoid noalias assumptions in unique return value optimization

[inglorion]

Summary

Changes the type of the @__typeid_.*_unique_member imports we generate
for unique return value optimization from i8 to [0 x i8]. This
prevents assuming that these imports do not alias, such as when
two unique return values occur in the same vtable.

Fixes PR45393.

[dblaikie]

Naive question, but I thought LLVM IR didn't have type based alias analysis based on LLVM IR pointer types (given the intention to remove pointee types - and any cases of pointee types being significant to optimizations are bugs, so far as I know). Is that's what's going on here? Because perhaps the right fix is to fix the optimization that's making assumptions based on pointee types instead of this change?

My understanding was any type based alias analysis used the TBAA metadata to describe which pointers could/couldn't point to the same things.

[inglorion]

@dblaikie: My understanding is that LLVM reserves the right to assume that distinct globals never alias and optimize based on that (e.g. as mentioned under https://releases.llvm.org/10.0.0/docs/AliasAnalysis.html#the-basicaa-pass), and that declaring globals as zero-sized is the accepted way to avoid that (e.g. as mentioned in https://bugs.llvm.org/show_bug.cgi?id=31675#c5).

So it's not so much improperly applied TBAA as it is an assumption that LLVM allows itself to make regardless of type, with a special exception for zero-sized types.

[inglorion]

Added a comment to (hopefully) better explain what the test does.

[dblaikie]

In D77421#1960852, @inglorion wrote:

@dblaikie: My understanding is that LLVM reserves the right to assume that distinct globals never alias and optimize based on that (e.g. as mentioned under https://releases.llvm.org/10.0.0/docs/AliasAnalysis.html#the-basicaa-pass), and that declaring globals as zero-sized is the accepted way to avoid that (e.g. as mentioned in https://bugs.llvm.org/show_bug.cgi?id=31675#c5).

So it's not so much improperly applied TBAA as it is an assumption that LLVM allows itself to make regardless of type, with a special exception for zero-sized types.

Ah - thanks! This is probably sufficiently out of my purview then, but little curious if you've time to explain it further: How does this feature work? Why could these two globals end up aliasing in practice before? Are these globals never actually defined?

[rnk]

This looks good to me, given LLVM's existing behavior, but I'd like to hear from the reviewers.

I'm increasingly skeptical of the problematic optimization here, but I'm not inclined to open up discussion at the moment.

[tejohnson]

@pcc is probably the best reviewer here. I've touched WPD but only the single impl devirt part (we can't do the uniq ret value in ThinLTO index-only mode). But the changes look pretty straightforward to me, assuming this is the best solution. Looking at the associated bug, what do the defs of those symbols look like? Is one an alias of the other?

[inglorion]

@tejohnson: The defs look like

@__typeid__ZTS4Base_16_unique_member = hidden alias i8, getelementptr (i8, i8* bitcast ({ [6 x i8*] }* @_ZTV7Derived to i8*), i64 16)
@__typeid__ZTS4Base_24_unique_member = hidden alias i8, getelementptr (i8, i8* bitcast ({ [6 x i8*] }* @_ZTV7Derived to i8*), i64 16)

So they are both aliases to the same vtable.

These are code generated into the split LTO object that is linked in in the final link step, where they show up as hidden global object, with the same value for each.

[inglorion]

@pcc, do you have time to take a look?

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

506

Elsewhere I've called this Int8Arr0Ty but I'm not too picky about the name.

1404

Is this change necessary? As far as I know we aren't passing the result of importGlobal here and it would be nice to avoid introducing a call to PointerType::getElementType() given that we hope to eliminate it one day.

1437

The type doesn't matter in this case (in fact it may be slightly more beneficial to use [0 x i8] here in order to allow the absolute symbols to "alias" when their values are the same), so could we just use it everywhere?

[inglorion]

Thanks, Peter! I've implemented your suggestions.

[inglorion]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

506

I've changed it to Int8Arr0Ty for consistency, and reworded the comment somewhat.

1404

No, we can keep this as i8. I've removed this change.

[inglorion]

@pcc, do you have time for another look?

[pcc]

LGTM

[inglorion]

Thanks!

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

 //===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
struct DevirtModule {
   ModuleSummaryIndex *ExportSummary;
   const ModuleSummaryIndex *ImportSummary;
 
   IntegerType *Int8Ty;
   PointerType *Int8PtrTy;
   IntegerType *Int32Ty;
   IntegerType *Int64Ty;
   IntegerType *IntPtrTy;
+  /// Type for imported vtables. Because we can use multiple names to refer
+  /// to the same vtable, we use a sizeless array type to prevent optimizers
+  /// from assuming different names refer to different addresses.
+  ArrayType *VtableTy;
 
   bool RemarksEnabled;
   function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter;
 
   MapVector<VTableSlot, VTableSlotInfo> CallSlots;
 
   // This map keeps track of the number of "unsafe" uses of a loaded function
   // pointer. The key is the associated llvm.type.test intrinsic call generated
DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
                const ModuleSummaryIndex *ImportSummary)
       : M(M), AARGetter(AARGetter), LookupDomTree(LookupDomTree),
         ExportSummary(ExportSummary), ImportSummary(ImportSummary),
         Int8Ty(Type::getInt8Ty(M.getContext())),
         Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
         Int32Ty(Type::getInt32Ty(M.getContext())),
         Int64Ty(Type::getInt64Ty(M.getContext())),
         IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
+        VtableTy(ArrayType::get(Type::getInt8Ty(M.getContext()), 0)),
         RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
     assert(!(ExportSummary && ImportSummary));
     FunctionsToSkip.init(SkipFunctionNames);
   }
 
   bool areRemarksEnabled();
 
   void scanTypeTestUsers(Function *TypeTestFunc);
struct DevirtModule {
   void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
                     Constant *C);
   void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
                       uint32_t Const, uint32_t &Storage);
 
   // This function is called during the import phase to create a reference to
   // the symbol definition created during the export phase.
   Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
-                         StringRef Name);
+                         StringRef Name, Type *Ty);
   Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
                            StringRef Name, IntegerType *IntTy,
                            uint32_t Storage);
 
   Constant *getMemberAddr(const TypeMemberInfo *M);
 
   void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
                             Constant *UniqueMemberAddr);

 
 bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
   Triple T(M.getTargetTriple());
   return T.isX86() && T.getObjectFormat() == Triple::ELF;
 }
 
 void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
                                 StringRef Name, Constant *C) {
-  GlobalAlias *GA = GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
-                                        getGlobalName(Slot, Args, Name), C, &M);
+  GlobalAlias *GA = GlobalAlias::create(
+      cast<PointerType>(C->getType())->getElementType(), 0,
+      GlobalValue::ExternalLinkage, getGlobalName(Slot, Args, Name), C, &M);
   GA->setVisibility(GlobalValue::HiddenVisibility);
 }
 
 void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
                                   StringRef Name, uint32_t Const,
                                   uint32_t &Storage) {
   if (shouldExportConstantsAsAbsoluteSymbols()) {
     exportGlobal(
         Slot, Args, Name,
         ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy));
     return;
   }
 
   Storage = Const;
 }
 
 Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
-                                     StringRef Name) {
-  Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
+                                     StringRef Name, Type *Ty) {
+  Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Ty);
   auto *GV = dyn_cast<GlobalVariable>(C);
   if (GV)
     GV->setVisibility(GlobalValue::HiddenVisibility);
   return C;
 }
 
 Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
                                        StringRef Name, IntegerType *IntTy,
                                        uint32_t Storage) {
   if (!shouldExportConstantsAsAbsoluteSymbols())
     return ConstantInt::get(IntTy, Storage);
 
-  Constant *C = importGlobal(Slot, Args, Name);
+  Constant *C = importGlobal(Slot, Args, Name, Int8Ty);
   auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
   C = ConstantExpr::getPtrToInt(C, IntTy);
 
   // We only need to set metadata if the global is newly created, in which
   // case it would not have hidden visibility.
   if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
     return C;
 

 }
 
 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
                                         bool IsOne,
                                         Constant *UniqueMemberAddr) {
   for (auto &&Call : CSInfo.CallSites) {
     IRBuilder<> B(Call.CS.getInstruction());
     Value *Cmp =
-        B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
-                     B.CreateBitCast(Call.VTable, Int8PtrTy), UniqueMemberAddr);
+        B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, Call.VTable,
+                     B.CreateBitCast(UniqueMemberAddr, Call.VTable->getType()));
     Cmp = B.CreateZExt(Cmp, Call.CS->getType());
     Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
                          Cmp);
   }
   CSInfo.markDevirt();
 }
 
 Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
     // importing phase. For now we just pass the empty string. This does not
     // impact correctness because the function names are just used for remarks.
     switch (ResByArg.TheKind) {
     case WholeProgramDevirtResolution::ByArg::UniformRetVal:
       applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
       break;
     case WholeProgramDevirtResolution::ByArg::UniqueRetVal: {
       Constant *UniqueMemberAddr =
-          importGlobal(Slot, CSByConstantArg.first, "unique_member");
+          importGlobal(Slot, CSByConstantArg.first, "unique_member", VtableTy);
       applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
                            UniqueMemberAddr);
       break;
     }
     case WholeProgramDevirtResolution::ByArg::VirtualConstProp: {
       Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
                                       Int32Ty, ResByArg.Byte);
       Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,

llvm/test/Transforms/WholeProgramDevirt/Inputs/unique-retval-same-vtable.yaml

+---
+TypeIdMap:
+  _ZTS1C:
+    WPDRes:
+      16:
+        Kind:            Indir
+        ResByArg:
+          '':
+            Kind:            UniqueRetVal
+            Info:            1
+      24:
+        Kind:            Indir
+        ResByArg:
+          '':
+            Kind:            UniqueRetVal
+            Info:            1
+...

llvm/test/Transforms/WholeProgramDevirt/import.ll

define i1 @call3(i8* %obj) #0 {
   %pair = call {i8*, i1} @llvm.type.checked.load(i8* %vtablei8, i32 8, metadata !"typeid2")
   %fptr = extractvalue {i8*, i1} %pair, 0
   %p = extractvalue {i8*, i1} %pair, 1
   br i1 %p, label %cont, label %trap
 
 cont:
   %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)*
   %result = call i1 %fptr_casted(i8* %obj, i32 3)
-  ; UNIQUE-RET-VAL0: icmp ne i8* %vtablei8, @__typeid_typeid2_8_3_unique_member
-  ; UNIQUE-RET-VAL1: icmp eq i8* %vtablei8, @__typeid_typeid2_8_3_unique_member
+  ; UNIQUE-RET-VAL0: icmp ne i8* %vtablei8, getelementptr inbounds ([0 x i8], [0 x i8]* @__typeid_typeid2_8_3_unique_member, i32 0, i32 0)
+  ; UNIQUE-RET-VAL1: icmp eq i8* %vtablei8, getelementptr inbounds ([0 x i8], [0 x i8]* @__typeid_typeid2_8_3_unique_member, i32 0, i32 0)
   ; VCP: [[VT2:%.*]] = bitcast {{.*}} to i8*
   ; VCP-X86: [[GEP2:%.*]] = getelementptr i8, i8* [[VT2]], i32 ptrtoint (i8* @__typeid_typeid2_8_3_byte to i32)
   ; VCP-ARM: [[GEP2:%.*]] = getelementptr i8, i8* [[VT2]], i32 43
   ; VCP: [[LOAD2:%.*]] = load i8, i8* [[GEP2]]
   ; VCP-X86: [[AND2:%.*]] = and i8 [[LOAD2]], ptrtoint (i8* @__typeid_typeid2_8_3_bit to i8)
   ; VCP-ARM: [[AND2:%.*]] = and i8 [[LOAD2]], -128
   ; VCP: [[ICMP2:%.*]] = icmp ne i8 [[AND2]], 0
   ; VCP: ret i1 [[ICMP2]]

llvm/test/Transforms/WholeProgramDevirt/unique-retval-same-vtable.ll

+; Test for PR45393: Two virtual functions that return unique i1 values
+; in the same vtable. Both calls are optimized to a comparison of
+; this's vptr against the address of the vtable. When nesting these
+; checks, LLVM would previously assume the nested check always fails,
+; but that assumption does not hold if both checks refer to the same vtable.
+; This tests checks that this case is handled correctly.
+;
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import \
+; RUN:   -wholeprogramdevirt-read-summary=%p/Inputs/unique-retval-same-vtable.yaml \
+; RUN:   -O2 -o - %s | FileCheck %s
+;
+; Check that C::f() contains both possible return values.
+; CHECK-LABEL: define {{.*}} @_ZNK1C1fEv
+; CHECK-NOT: }
+; CHECK: 20074028
+; CHECK-NOT: }
+; CHECK: 1008434
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%class.C = type { i32 (...)** }
+
+define hidden i32 @_ZNK1C1fEv(%class.C* %this) {
+entry:
+  %0 = bitcast %class.C* %this to i1 (%class.C*)***
+  %vtable = load i1 (%class.C*)**, i1 (%class.C*)*** %0
+  %1 = bitcast i1 (%class.C*)** %vtable to i8*
+  %2 = tail call i1 @llvm.type.test(i8* %1, metadata !"_ZTS1C")
+  tail call void @llvm.assume(i1 %2)
+  %vfn = getelementptr inbounds i1 (%class.C*)*, i1 (%class.C*)** %vtable, i64 2
+  %3 = load i1 (%class.C*)*, i1 (%class.C*)** %vfn
+  %call = tail call zeroext i1 %3(%class.C* %this)
+  br i1 %call, label %if.then, label %return
+
+if.then:
+  %vtable2 = load i1 (%class.C*)**, i1 (%class.C*)*** %0
+  %4 = bitcast i1 (%class.C*)** %vtable2 to i8*
+  %5 = tail call i1 @llvm.type.test(i8* %4, metadata !"_ZTS1C")
+  tail call void @llvm.assume(i1 %5)
+  %vfn3 = getelementptr inbounds i1 (%class.C*)*, i1 (%class.C*)** %vtable2, i64 3
+  %6 = load i1 (%class.C*)*, i1 (%class.C*)** %vfn3
+  ; The method being called here and the method being called before
+  ; the branch above both return true in the same vtable and only that
+  ; vtable. Therefore, if this call is reached, we must select
+  ; 20074028. Earlier versions of LLVM mistakenly concluded that
+  ; this code *never* selects 200744028.
+  %call4 = tail call zeroext i1 %6(%class.C* nonnull %this)
+  %. = select i1 %call4, i32 20074028, i32 3007762
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %., %if.then ], [ 1008434, %entry ]
+  ret i32 %retval.0
+}
+
+declare i1 @llvm.type.test(i8*, metadata)
+
+declare void @llvm.assume(i1)

llvm/test/Transforms/WholeProgramDevirt/unique-retval.ll

 define i1 @vf1(i8* %this) readnone {
   ret i1 1
 }
 
 ; CHECK: define i1 @call1
 define i1 @call1(i8* %obj) {
   %vtableptr = bitcast i8* %obj to [1 x i8*]**
   %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
-  ; CHECK: {{.*}} = bitcast [1 x i8*]* {{.*}} to i8*
-  ; CHECK: [[VT1:%[^ ]*]] = bitcast [1 x i8*]* {{.*}} to i8*
   %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
   %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid1")
   call void @llvm.assume(i1 %p)
   %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
   %fptr = load i8*, i8** %fptrptr
   %fptr_casted = bitcast i8* %fptr to i1 (i8*)*
-  ; CHECK: [[RES1:%[^ ]*]] = icmp eq i8* [[VT1]], bitcast ([1 x i8*]* @vt3 to i8*)
+  ; CHECK: [[RES1:%[^ ]*]] = icmp eq [1 x i8*]* %vtable, @vt3
   %result = call i1 %fptr_casted(i8* %obj)
   ; CHECK: ret i1 [[RES1]]
   ret i1 %result
 }
 
 ; CHECK: define i32 @call2
 define i32 @call2(i8* %obj) {
   %vtableptr = bitcast i8* %obj to [1 x i8*]**
   %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
-  ; CHECK: [[VT2:%[^ ]*]] = bitcast [1 x i8*]* {{.*}} to i8*
   %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
   %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid2")
   call void @llvm.assume(i1 %p)
   %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
   %fptr = load i8*, i8** %fptrptr
   ; Intentional type mismatch to test zero extend.
   %fptr_casted = bitcast i8* %fptr to i32 (i8*)*
-  ; CHECK: [[RES2:%[^ ]*]] = icmp ne i8* [[VT1]], bitcast ([1 x i8*]* @vt2 to i8*)
+  ; CHECK: [[RES2:%[^ ]*]] = icmp ne [1 x i8*]* %vtable, @vt2
   %result = call i32 %fptr_casted(i8* %obj)
   ; CHECK: [[ZEXT2:%[^ ]*]] = zext i1 [[RES2]] to i32
   ; CHECK: ret i32 [[ZEXT2:%[^ ]*]]
   ret i32 %result
 }
 
 declare i1 @llvm.type.test(i8*, metadata)
 declare void @llvm.assume(i1)
 
 !0 = !{i32 0, !"typeid1"}
 !1 = !{i32 0, !"typeid2"}