[InstCombine] Remove invariant group intrinsincs when comparing against null

[aeubanks]

Summary

We cannot leak any equivalency information by comparing against null
since null never has virtual metadata associated with it (when null is
not a valid dereferenceable pointer).

Instcombine seems to make sure that a null will be on the RHS, so we
don't have to check both operands.

This fixes a missed optimization in llvm-test-suite's MultiSource lambda
benchmark under -fstrict-vtable-pointers.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5705–5724

In-place replacements aren't nice.
How about:

llvm/test/Transforms/InstCombine/invariant.group.ll

2

I'm not sure what this is testing, but pass tests that involve more than a single pass are frowned upon.

[aeubanks]

cleanup code

[lebedev.ri]

Code-wise this seems fine, but i'm not sure i'm sufficiently familiar with the semantics.

[aeubanks]

hmm, if two pointers are equal in an icmp, will GVN RAUW one with the other based on that info? maybe I'm completely missing something

[aeubanks]

nvm I think this patch is wrong

[Prazek]

Lets talk offline about the specific case to get it right. The model is pretty brittle in those areas, so we have to be sure the transformations are legal

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5705–5717

If I understand this correctly, this essentially strips launders/strips from cmp operands.

I think this is incorrect. From the perspective of devirtualization we can have code like:

%vtable_a = load i8* %a, !invariant.group !{}
;;;
; %a == %b
%addr_a = call i8* @llvm.strip.invariant.group(i8* %a)
%addr_b = call i8* @llvm.strip.invariant.group(i8* %b)
%bool = icmp %addr_a, %addr_b
br %bool, %if, %after
if:
; This will not be able to change %b to %a
%vtable_b = load i8* %b, !invariant.group !{}

As you see, the two loads operate on %a and %b (where %b is a result of launder). As comparisons can leak the idea that %a and %b are essentially the same addresses (thus enabling GVN to RAUW %b with %a), we need to strip it before cmp.

In this case, we would replace the cmp with icmp %a %b, which would essentially tell GVN %a and %b can be used interchanganbly in this branch.

[Prazek]

Just for the record (discussed offline): if the problem is comparisons of launder/strip(%p) with null, then for this specific case we could I think replace it with comparison of %p and null, as null does does not have any "virtual" information (similarly how we already optimzie launder/strip(null) to null

[aeubanks]

only optimize null comparisons

[Prazek]

LGTM! Great work with looking for regressions like that.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5715

I wonder if the fact that usually there are bitcasts around strip/launder could be problematic.
I think this does not handle case like:

%b1 = bitcast i32* %p to i8*
%b2 = strip(%b1)
%b3 = bitcast i8* %b2 to i32*

icmp %b3, null

But it might be not a problem, if this code gets cannonicalized to:

%b1 = bitcast i32* %p to i8*
%b2 = strip(%b1)

icmp %b2, null

Could you double check if this would be optimized by InstCombine allone, or that there is any pass that would cannonicalize it?

[lebedev.ri]

Seems fine to me with nits

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5709–5711

5714–5715

Could flatten the if's

5719

Could do early-return, but not sure how better that would be here

[Prazek]

Could you also update the description and title?

[aeubanks]

update

[aeubanks]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5709–5711

it's hard to read with a multi-line if condition IMO

5715

added a test to verify that instcombine takes care of this

[Prazek]

LGTM!

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

else if (match(Op1, UAddOvResultPat) &&
     // A > extract(uadd.with.overflow(A, B), 0)
     UAddOv = cast<ExtractValueInst>(Op1)->getAggregateOperand();
   else
     return nullptr;
 
   return ExtractValueInst::Create(UAddOv, 1);
 }
 
+static Instruction *foldICmpInvariantGroup(ICmpInst &I) {
+  if (!I.getOperand(0)->getType()->isPointerTy() ||
+      NullPointerIsDefined(
+          I.getParent()->getParent(),
+          I.getOperand(0)->getType()->getPointerAddressSpace())) {
+    return nullptr;
+  }
+  Instruction *Op;
+  if (match(I.getOperand(0), m_Instruction(Op)) &&
+      match(I.getOperand(1), m_Zero()) &&
+      Op->isLaunderOrStripInvariantGroup()) {
+    return ICmpInst::Create(Instruction::ICmp, I.getPredicate(),
+                            Op->getOperand(0), I.getOperand(1));
+  }
+  return nullptr;
+}
+
 Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
   bool Changed = false;
   const SimplifyQuery Q = SQ.getWithInstruction(&I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   unsigned Op0Cplxity = getComplexity(Op0);
   unsigned Op1Cplxity = getComplexity(Op1);
 
   /// Orders the operands of the compare so that they are listed from most
   /// complex to least complex.  This puts constants before unary operators,
   /// before binary operators.
   if (Op0Cplxity < Op1Cplxity ||
Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
 
   if (Instruction *Res = foldICmpWithHighBitMask(I, Builder))
     return Res;
 
   if (I.getType()->isVectorTy())
     if (Instruction *Res = foldVectorCmp(I, Builder))
       return Res;
 
+  if (Instruction *Res = foldICmpInvariantGroup(I))
+    return Res;
+
   return Changed ? &I : nullptr;
 }
 
 /// Fold fcmp ([us]itofp x, cst) if possible.
 Instruction *InstCombinerImpl::foldFCmpIntToFPConst(FCmpInst &I,
                                                     Instruction *LHSI,
                                                     Constant *RHSC) {
   if (!isa<ConstantFP>(RHSC)) return nullptr;

llvm/test/Transforms/InstCombine/invariant.group.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -early-cse -earlycse-debug-hash -S < %s | FileCheck %s
 
 define i8* @simplifyNullLaunder() {
 ; CHECK-LABEL: @simplifyNullLaunder(
 ; CHECK-NEXT:    ret i8* null
 ;
   %b2 = call i8* @llvm.launder.invariant.group.p0i8(i8* null)
   ret i8* %b2
 }
;
   %c1 = bitcast i8 addrspace(42)* %a2 to i16 addrspace(42)*
 
   %a3 = call i16 addrspace(42)* @llvm.strip.invariant.group.p42i16(i16 addrspace(42)* %c1)
   ret i16 addrspace(42)* %a3
 }
 
 define i1 @icmp_null_launder(i8* %a) {
 ; CHECK-LABEL: @icmp_null_launder(
-; CHECK-NEXT:    [[A2:%.*]] = call i8* @llvm.launder.invariant.group.p0i8(i8* [[A:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8* [[A2]], null
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8* [[A:%.*]], null
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %a2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %a)
   %r = icmp eq i8* %a2, null
   ret i1 %r
 }
 
 define i1 @icmp_null_strip(i8* %a) {
 ; CHECK-LABEL: @icmp_null_strip(
-; CHECK-NEXT:    [[A2:%.*]] = call i8* @llvm.strip.invariant.group.p0i8(i8* [[A:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8* [[A2]], null
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8* [[A:%.*]], null
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %a2 = call i8* @llvm.strip.invariant.group.p0i8(i8* %a)
   %r = icmp eq i8* %a2, null
   ret i1 %r
 }
 
 define i1 @icmp_null_launder_valid_null(i8* %a) #0 {
;
   %a2 = call i8* @llvm.strip.invariant.group.p0i8(i8* %a)
   %r = icmp eq i8* %a2, null
   ret i1 %r
 }
 
 ; Check that null always becomes the RHS
 define i1 @icmp_null_launder_lhs(i8* %a) {
 ; CHECK-LABEL: @icmp_null_launder_lhs(
-; CHECK-NEXT:    [[A2:%.*]] = call i8* @llvm.launder.invariant.group.p0i8(i8* [[A:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8* [[A2]], null
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8* [[A:%.*]], null
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %a2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %a)
   %r = icmp eq i8* null, %a2
   ret i1 %r
 }
 
 define i1 @icmp_null_launder_bitcasts(i32* %a) {
 ; CHECK-LABEL: @icmp_null_launder_bitcasts(
-; CHECK-NEXT:    [[A2:%.*]] = bitcast i32* [[A:%.*]] to i8*
-; CHECK-NEXT:    [[A3:%.*]] = call i8* @llvm.launder.invariant.group.p0i8(i8* [[A2]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8* [[A3]], null
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i32* [[A:%.*]], null
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %a2 = bitcast i32* %a to i8*
   %a3 = call i8* @llvm.launder.invariant.group.p0i8(i8* %a2)
   %a4 = bitcast i8* %a3 to i32*
   %r = icmp eq i32* %a4, null
   ret i1 %r
 }