[GMR] isNonEscapingGlobalNoAlias() should look through Bitcasts/GEPs when looking at loads.

[mkuper]

Summary

Yet another case that shows up in eembc, see PR24288.

[hfinkel]

lib/Analysis/IPA/GlobalsModRef.cpp

654 ↗

(On Diff #32240)

It seems like we could make this more general is two ways:

1. Call GetUnderlyingObjects, and checking that all of the results are GlobalValues
2. Also checking that the underlying objects are not arguments or call/invoke return values.

If I'm reading this code correctly, one possible way of handling this, is just to do this:

push.Inputs(LI->getPointerOperand());
continue;

which seems to accomplish both things, and keeps an integrated Depth constraint.

[chandlerc]

lib/Analysis/IPA/GlobalsModRef.cpp

654 ↗

(On Diff #32240)

You're saying a pointer loaded from an escaping pointer is itself escaping?

I think I agree, but it makes this surprisingly more powerful. This will chase a chain of loads until it hits control flow or a known underlying object. Nifty, but maybe surprising.

However, unless I'm mistaken, we still need to call GetUnderlyingObject? The worklist doesn't do that.

I'm a bit scared about using GetUnderlyingObjects making this significantly more slow...

[hfinkel]

lib/Analysis/IPA/GlobalsModRef.cpp

654 ↗

(On Diff #32240)

Responses below, but actually, it seems that we can do even better than this:

A non-addr-taken global does not have its address stored anywhere, ever. Thus, if we get a pointer from a load, it cannot be a non-addr-taken global (except for those in AllocsForIndirectGlobals). No?

You're saying a pointer loaded from an escaping pointer is itself escaping?

Yes, I think that's correct.

I think I agree, but it makes this surprisingly more powerful. This will chase a chain of loads until it hits control flow or a known underlying object. Nifty, but maybe surprising.

With a depth limit of 4, it is not going to do very *much* chasing ;) - but, yes, that's the idea.

However, unless I'm mistaken, we still need to call GetUnderlyingObject? The worklist doesn't do that.

Ah, yes, correct. The existing worklist does not look though GEPs. Should it?

I'm a bit scared about using GetUnderlyingObjects making this significantly more slow...

Indeed; this was my motivation for suggesting using the existing worklist (to get the unified depth limit).

[mkuper]

Thanks for the idea, Hal.
But, unless I'm missing something, this doesn't quite work, because the base condition is different.

Let's say you have:
%v = load i32, i32* @g1

isNonEscapingGlobalNoAlias(@g1, @g1) should return false, but isNonEscapingGlobalNoAlias(@g1, %v) should return true.
So we can't just push @g1 onto the worklist.

[chandlerc]

Let's start with the patch as-is. I'm sure that this at least is correct and unlikely to be problematic for compile time, while it is sufficient to solve real world performance problems.

We can revisit other designs as follow-up patches.

Michael, feel free to submit, and we can keep poking at what the exact right model here is.

[hfinkel]

In D12064#225516, @mkuper wrote:

Thanks for the idea, Hal.
But, unless I'm missing something, this doesn't quite work, because the base condition is different.

Let's say you have:
%v = load i32, i32* @g1

isNonEscapingGlobalNoAlias(@g1, @g1) should return false, but isNonEscapingGlobalNoAlias(@g1, %v) should return true.
So we can't just push @g1 onto the worklist.

Good point.

llvm/trunk/lib/Analysis/IPA/GlobalsModRef.cpp

if (isa<Argument>(Input) || isa<CallInst>(Input) ||
       // Arguments to functions or returns from functions are inherently
       // escaping, so we can immediately classify those as not aliasing any
       // non-addr-taken globals.
       continue;
     }
     if (auto *LI = dyn_cast<LoadInst>(Input)) {
       // A pointer loaded from a global would have been captured, and we know
       // that the global is non-escaping, so no alias.
-      if (isa<GlobalValue>(LI->getPointerOperand()))
+      if (isa<GlobalValue>(GetUnderlyingObject(LI->getPointerOperand(), *DL)))
         continue;
 
       // Otherwise, a load could come from anywhere, so bail.
       return false;
     }
 
     // Recurse through a limited number of selects and PHIs. This is an
     // arbitrary depth of 4, lower numbers could be used to fix compile time

llvm/trunk/test/Analysis/GlobalsModRef/nonescaping-noalias.ll

entry:
   store i32 42, i32* @g1
   %ptr1 = load i32*, i32** @g2
   store i32 7, i32* %ptr1
   %v = load i32, i32* @g1
   ret i32 %v
 }
 
 @g3 = internal global i32 1
+@g4 = internal global [10 x i32*] zeroinitializer
 
 define i32 @test4(i32* %param, i32 %n, i1 %c1, i1 %c2, i1 %c3) {
 ; Ensure that we can fold a store to a load of a global across a store to
 ; the pointer loaded from that global even when the load is behind PHIs and
 ; selects, and there is a mixture of a load and another global or argument.
 ; Note that we can't eliminate the load here because it is used in a PHI and
 ; GVN doesn't try to do real DCE. The store is still forwarded by GVN though.
 ;
 ; CHECK-LABEL: @test4(
 ; CHECK: store i32 42, i32* @g1
 ; CHECK: store i32 7, i32*
 ; CHECK: ret i32 42
 entry:
   %call = call i32* @f()
   store i32 42, i32* @g1
   %ptr1 = load i32*, i32** @g2
   %ptr2 = select i1 %c1, i32* %ptr1, i32* %param
   %ptr3 = select i1 %c3, i32* %ptr2, i32* @g3
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %inc, %loop ]
   %ptr = phi i32* [ %ptr3, %entry ], [ %ptr5, %loop ]
   store i32 7, i32* %ptr
-  %ptr4 = load i32*, i32** @g2
+  %ptr4 = load i32*, i32** getelementptr ([10 x i32*], [10 x i32*]* @g4, i32 0, i32 1)
   %ptr5 = select i1 %c2, i32* %ptr4, i32* %call
   %inc = add i32 %iv, 1
   %test = icmp slt i32 %inc, %n
   br i1 %test, label %loop, label %exit
 
 exit:
   %v = load i32, i32* @g1
   ret i32 %v
 }