[instsimplify] Assume storage for byval args doesn't overlap allocas, globals, or other byval args

[reames]

Summary

This allows us to discharge many pointer comparisons based on byval arguments.

[fhahn]

llvm/lib/Analysis/InstructionSimplify.cpp

2674–2679

Could this lead to a regression where CtxI is nullptr but LHS is an instruction?

llvm/test/Transforms/InstSimplify/compare.ll

2740

TODO can be dropped now.

2761

TODO can be dropped now.

[reames]

llvm/lib/Analysis/InstructionSimplify.cpp

2674–2679

In theory, yes. I'll rewrite to assume either alloca or argument for now.

[reames]

Address review comments

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

2571

Can't this function be simplified to isByValArgOrAllocaOrGlobalVar(V1) && isByValArgOrAllocaOrGlobalVar(V2)? Is there some reason your implementation is going out of the way to not handle the GlobalVariable + GlobalVariable case? (Note that GlobalVariable != GlobalObject, so this does not included aliases).

[reames]

llvm/lib/Analysis/InstructionSimplify.cpp

2571

The bit of code your commenting on was the original structure - I moved it, but didn't change it.

When I posted this, I hadn't dug into the global piece in detail. I have now. Global are slightly tricky because not all them are guaranteed disjoint - or at least that's what the code in constant folding seems to imply? We don't actually get here with globals - they're constantexprs - but I didn't want to risk adding rarely executed potentially divergent behavior.

I think that your suggestion probably is okay, but I'd strongly prefer to go with the current structure for now, and restructure in a separate change for risk isolation. My hope is to eventually pull this out in a way where we can reuse it in constant folding as well.

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

2571

Hm yeah, I guess the two global case is not legal for unnamed_addr globals, which may be merged.

I think it may still be worthwhile to write this in a way that explicitly excludes that case, rather than listing different permutations of possible combinations. Something like this, maybe?

auto IsDisjointObject = [](Value *V) {
  auto *Arg = dyn_cast<Argument>(V);
  return isa<AllocaInst>(V) || isa<GlobalVariable>(V) || (Arg && Arg->hasByValAttr());
};
if (!IsDisjointObject(V1) || !IsDisjointObject(V2))
  return false;

// Two globals may have the same address.
// TODO: Make this specific to unnamed_addr globals.
return !isa<GlobalVariable>(V1) || !isa<GlobalVariable>(V2);

[nikic]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

2571

But I think it's also okay as-is...

[efriedma]

Since you're in the area, have you seen https://github.com/llvm/llvm-project/issues/45725 ?

[fhahn]

LGTM, thanks!

[reames]

In D120133#3332474, @efriedma wrote:

Since you're in the area, have you seen https://github.com/llvm/llvm-project/issues/45725 ?

I had not. Skimmed it, doesn't seem directly related. I'm not even sure there's a bug there, much less one immediately relevant here.

llvm/lib/Analysis/InstructionSimplify.cpp

2571

I will play with some options here and try posting something in another review.

[reames]

llvm/lib/Analysis/InstructionSimplify.cpp

2571

I ended up landing basically exactly your suggestion with a comment explaining the assumption we make about globals here, and we expect not to see the two globals case. See 3a6be12.

[uabelho]

I wrote
https://github.com/llvm/llvm-project/issues/54615
about a crash that started happening with this patch.

llvm/lib/Analysis/InstructionSimplify.cpp

static bool HaveNonOverlappingStorage(const Value *V1, const Value *V2) {
   // instruction kind specifically for static allocas. Such a new instruction
   // could be required to be at the top of the entry block, thus preventing it
   // from being subject to a @llvm.stackrestore. Instcombine could even
   // convert regular allocas into these special allocas. It'd be nifty.
   // However, until then, this problem remains open.
   //
   // So, we'll assume that two non-empty allocas have different addresses
   // for now.
-  return isa<AllocaInst>(V1) &&
+  auto isByValArg = [](const Value *V) {
+    const Argument *A = dyn_cast<Argument>(V);
+    return A && A->hasByValAttr();
+  };
+
+  // Byval args are backed by store which does not overlap with each other,
+  // allocas, or globals.
+  if (isByValArg(V1))
+    return isa<AllocaInst>(V2) || isa<GlobalVariable>(V2) || isByValArg(V2);
+  if (isByValArg(V2))
+    return isa<AllocaInst>(V1) || isa<GlobalVariable>(V1) || isByValArg(V1);
+
     (isa<AllocaInst>(V2) || isa<GlobalVariable>(V2));
 }
 
 // A significant optimization not implemented here is assuming that alloca
 // addresses are not equal to incoming argument values. They don't *alias*,
 // as we say, but that doesn't mean they aren't equal, so we take a
 // conservative approach.
 //
 // This is inspired in part by C++11 5.10p1:
if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
     // different addresses (if the program can tell). If the offsets are
     // within the bounds of their allocations (and not one-past-the-end!
     // so we can't use inbounds!), and their allocations aren't the same,
     // the pointers are not equal.
     if (HaveNonOverlappingStorage(LHS, RHS)) {
       uint64_t LHSSize, RHSSize;
       ObjectSizeOpts Opts;
       Opts.EvalMode = ObjectSizeOpts::Mode::Min;
-      Opts.NullIsUnknownSize =
-          NullPointerIsDefined(cast<AllocaInst>(LHS)->getFunction());
+      auto *F = [](Value *V) {
+        if (auto *I = dyn_cast<Instruction>(V))
+          return I->getFunction();
+        return cast<Argument>(V)->getParent();
+      }(LHS);
+      Opts.NullIsUnknownSize = NullPointerIsDefined(F);
       if (getObjectSize(LHS, LHSSize, DL, TLI, Opts) &&
           getObjectSize(RHS, RHSSize, DL, TLI, Opts) &&
           !LHSOffset.isNegative() && !RHSOffset.isNegative() &&
           LHSOffset.ult(LHSSize) && RHSOffset.ult(RHSSize)) {
         return ConstantInt::get(GetCompareTy(LHS),
                                 !CmpInst::isTrueWhenEqual(Pred));
       }
     }

llvm/test/Transforms/InstSimplify/compare.ll

 ; CHECK-NEXT:    ret i1 true
 ;
   %a = alloca <vscale x 2 x i32>
   %b = alloca <vscale x 2 x i32>
   %res = icmp ne <vscale x 2 x i32>* %a, %b
   ret i1 %res
 }
 
-; TODO: Never equal
+; Never equal
 define i1 @byval_args_inequal(i32* byval(i32) %a, i32* byval(i32) %b) {
 ; CHECK-LABEL: @byval_args_inequal(
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32* [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %res = icmp ne i32* %a, %b
   ret i1 %res
 }
 
 ; Arguments can be adjacent on the stack
 define i1 @neg_args_adjacent(i32* byval(i32) %a, i32* byval(i32) %b) {
 ; CHECK-LABEL: @neg_args_adjacent(
 ; CHECK-NEXT:    [[A_OFF:%.*]] = getelementptr i32, i32* [[A:%.*]], i32 1
 ; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32* [[A_OFF]], [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a.off = getelementptr i32, i32* %a, i32 1
   %res = icmp ne i32* %a.off, %b
   ret i1 %res
 }
 
-; TODO: Never equal
+; Never equal
 define i1 @test_byval_alloca_inequal(i32* byval(i32) %a) {
 ; CHECK-LABEL: @test_byval_alloca_inequal(
-; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32* [[A:%.*]], [[B]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = alloca i32
   %res = icmp ne i32* %a, %b
   ret i1 %res
 }
 
 ; Byval argument can be immediately before alloca, and crossing
 ; over is allowed.
;
   %a.off = getelementptr i8, i8* %a.cast, i32 1
   %b.cast = bitcast i32* @B to i8*
   %b.off = getelementptr i8, i8* %b.cast, i32 1
   %res = icmp ne i8* %a.off, %b.off
   ret i1 %res
 }
 
 
-; TODO: Never equal
+; Never equal
 define i1 @test_byval_global_inequal(i32* byval(i32) %a) {
 ; CHECK-LABEL: @test_byval_global_inequal(
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32* [[A:%.*]], @B
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %b = alloca i32
   %res = icmp ne i32* %a, @B
   ret i1 %res
 }
 
 
 define i1 @neg_global_alias() {